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

Question

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

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

Answer 1

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

https://stackoverflow.com/a/23435654/3591273

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

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

1. Произвольно выберите первый пустой словосочетание, которое будет заполнено из сетки, и заполните его подходящим словом

2. Найдите все пустые словосочетания, которые имеют пересечения суже заполненные слова

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

4. Цикл по пустым слотам предыдущегошаг и попробуйте количество слов-кандидатов (из доступных слов)

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

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

7. При желании можно сбросить любые слоты слов, которые могут нуждаться в сбросе после возврата (то есть пометить их как пустые снова), и перейти кшаг 2

8. Если откат не найден, то эта конфигурация не имеет решения

9. Если все пустые слоты заполнены, у вас есть одно решение