Быстрый алгоритм для создания головоломки

Я нашел головоломку в http://www.puzzles.ca/wordsearch/transportation.html, где нужно найти слово в сетке и он может читать слова из 8 направлений, На мой взгляд поднялся следующий вопрос:

Нам дали набор слов. Найдите алгоритм, который помещает эти слова в сетку n x m, где даны n и m. Есть ли у кого-нибудь предложения по созданию алгоритма для создания подходящей сетки, поскольку проблема кажется сложной, если размер сетки достаточно, чтобы соответствовать алфавиту сетке, а слова накладываются друг на друга?

Ответ 1

Алгоритм описан в этом вопросе SO также

fooobar.com/info/60647/...

Надеюсь, что это поможет

UPDATE: краткое изложение алгоритма (как указано в предыдущей ссылке)

Случайно выберите первый пустой слот для заполнения из сетки и заполните его подходящим словом
Найти все пустые словарные строки, которые имеют пересечения, уже заполненными слотами слов
Сортируйте их по коэффициенту ограничения (например, количество доступных решений для каждого)
Прокрутите пустые слоты предыдущего шага и попробуйте количество слов-кандидатов (из доступных слов)
Выберите словослот и слово для заполнения, которое сохраняет согласованность сетки (т.е. сетка имеет решение после заполнения этого слота слова этим словом), а также количество решений на следующем шаге максимально (это сводит к минимуму бактраксы в следующие шаги) и перейдите к шагу 2
Если на предыдущем шаге не найдено ни одного слова, попробуйте вернуться к предыдущему слову и используйте альтернативного кандидата (если только доступные кандидаты не исчерпаны)
Необязательно reset любые слоты слова, которые могут потребоваться reset после обратного отсчета (т.е. пометьте их как пустые снова) и перейдите к шагу 2
Если никакого возврата нет, то эта конфигурация не имеет решения
Если все пустые слоты заполнены, у вас есть одно решение