Генератор кроссвордов (шведский кроссворд) - Java

Question

Я пытаюсь создать простой кроссворд генератора Java (шведский кроссворд) - просто для удовольствия. Я скачал словарный запас слов из Интернета (около 300000 слов). Эти слова я сохранил в HashMap (отсортировано по длине слова). Вход генератора - это размер X и Y и головоломка. Головоломку я вставил случайно в матрицу

Но я не могу выяснить работающий алгоритм, чтобы заполнить остальную часть матрицы.

Например:

X X X X
X D O G
X X X X

У кого-нибудь есть совет? Или какая-нибудь полезная статья в интернете? благодарю вас.

Answer 1

Алгоритм составления кроссвордов (например, шведский, скандинавский и т. Д.) Описан здесь (среди прочего, конечно,:))

/questions/42487024/algoritm-generatsii-krossvorda/42487051#42487051

ОБНОВЛЕНИЕ: размещение основных шагов алгоритма, описанного в приведенной ссылке SO (согласно комментарию)

1. Первым шагом алгоритма является случайное выделение пустого словосочетания (сеточного слова) и заполнение его словом-кандидатом из связанного с ним словарного списка (рандомизация позволяет создавать различные солютоны в последовательных выполнениях алгоритма) (сложность O (1) или O(N))

2. Для каждого еще пустого слота слов (у которого есть пересечения с уже заполненными слотами слов), вычислите отношение ограничений (это может варьироваться, просто число доступных решений на этом шаге) и отсортируйте пустые слоты слов по этому соотношению (сложность O (NlogN)) или O(N))

3. Переберите пустые слова, вычисленные на предыдущем шаге, и для каждого попробуйте несколько решений cancdidate (убедившись, что "согласованность дуги сохраняется", то есть у сетки есть решение после этого шага, если используется это слово), и отсортируйте их в соответствии с максимальная доступность для следующего шага (т.е. следующий шаг имеет максимально возможные решения, если это слово используется в то время в этом месте и т. д.) (сложность O(N*MaxCandidatesUsed))

4. Заполните это слово (пометьте его как заполненное и перейдите к шагу 2)

5. Если не найдено ни одного слова, удовлетворяющего критериям шага.3, попробуйте вернуться к другому подходящему решению некоторого предыдущего шага (критерии могут варьироваться здесь) (сложность O(N))

6. Если откат найден, используйте альтернативу и при необходимости сбросьте все уже заполненные слова, которые могут нуждаться в сбросе (пометьте их как незаполненные снова) (сложность O(N))

7. Если возврат не найден, решение не может быть найдено (по крайней мере, с этой конфигурацией, начальным начальным числом и т. Д.)

8. Иначе, когда все слова заполнены, у вас есть одно решение

Этот алгоритм выполняет случайное последовательное блуждание дерева решений задачи. Если в какой-то момент существует тупик, он выполняет возврат к предыдущему узлу и следует по другому маршруту. До тех пор, пока не будет найдено решение или количество кандидатов на различные узлы исчерпаны.

Часть согласованности гарантирует, что найденное решение действительно является решением, а случайная часть позволяет создавать разные решения в разных исполнениях, а также в среднем иметь лучшую производительность.

PS пытался избежать копирования-вставки туда-сюда между различными SO-ответами, но хорошо, может быть, какое-то резюме может быть полезным