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