Исходник программы, показывающей пример создания головоломки «Акростик», которая раскрывает 13-й (неуказанный) вид транспорта в серых областях кроссворда, когда он решен.
Проблема была смоделирована введением «правила пересечения» записей для каждой пары слов, которые пересекаются друг с другом. Позиции слов пронумерованы от H1 до H6 и от V1 до V6 слева направо и сверху вниз. Таким образом, H1 (2), V1 (2) указывает, что горизонтальное слово H1 и вертикальное слово V1 пересекаются во второй букве каждого слова. Программа присоединяет строковый список пар слов «Кандидат», которые могут соответствовать требованиям правила.
Запись TRulerec разбивает текст каждого правила на отдельные поля и добавляет список строк Candidates для хранения пар слов, которые имеют совпадающие буквы в указанных положениях пересечения. Процедура SearchBtn сначала создает массив Rules из TRuleRec на основе отображаемых правил пересечения и строит список кандидатов для каждого правила. После создания этого массива Rules мы вызываем функцию CheckCandidates для каждого правила, чтобы рекурсивно обработать пары слов-кандидатов. AssignedList - это строковый список типа Name = Value с «Word = Assigned location» для всех слов с указанием того, какой позиции слова было присвоено это слово со специальным индикатором (буква «N»), устанавливается, если это слово доступно. CheckCandidates обрабатывает список кандидатов в поисках пары доступных слов, которые он может назначить. Если он находит пару, он назначает их и вызывает себя со следующим номером правила. Если для текущего правила не могут быть назначены никакие кандидаты, функция возвращает «False» вызывающему (предыдущее правило), которое затем отменяет присвоение своих последних назначений и пробует следующую пару кандидатов и т.д. Процесс продолжается до тех пор, пока все правила не будут выполнены. Если у нас есть решение, или все правила исчерпали всех своих кандидатов, и в этом случае решения не существует. Это классический «поиск в глубину с рекурсией», который до сих пор кажется мне волшебством)
Я добавил функцию сортировки массива Rules перед решением, чтобы уменьшить длину пути поиска. Первоначальный порядок - по номеру слова по горизонтали, но я добавил параметры для сортировки, увеличив длину списка слов кандидатов (выполняется намного быстрее) или по убыванию числа пересечений для горизонтального слова (умеренно быстрее). Идея сортировки по размеру списка кандидатов заключалась в том, что меньшее количество кандидатов будет быстрее размещать нужные слова, и похоже, что это так. Для убывающего числа пересечений идея заключалась в том, чтобы сначала поставить слова с наибольшим количеством пересечений, но, похоже, это еще не все. Остается открытым вопрос, существуют ли более эффективные способы предварительного выбора порядка правил для повышения эффективности. Обработка правил со словами, пересекающими последние помещенные слова, может быть более «похожей на человека» и быть даже более эффективной.
Базы данных
