Я уже писал программу кроссвордов (загадочно, но теория, лежащая в основе конструкции, идентична).
У меня была база данных слов и их подсказок, которые можно было отсортировать по времени (чтобы я не получал повторяющиеся кроссворды при последующих запусках).
Первое, что вы должны сделать, это создать свои шаблоны (черные, где вы не можете поместить буквы и белые, где можете). Попытка поместить слова в сетку при создании шаблона на лету очень трудоемка и подвержена ошибкам. Если вы посмотрите на большинство кроссвордов, они, как правило, следуют определенным правилам, чтобы облегчить их. Такие вещи, как симметричность вокруг одной из диагоналей и запрет квадрата из четырех белых клеток (чтобы упростить задачу выбора подходящих слов).
Когда у вас есть шаблон, , затем вы начинаете находить слова для размещения в нем. Таким образом, вы будете знать, что «приложение» является началом слова и сможете ограничить поиск тем, которые начинаются с «приложения», а не каждым словом, в котором есть «приложение». Аналогично для слов, где вы знаете буквы на любых позициях. Гораздо проще найти слова с буквами в известных позициях, чем оценивать эти буквы в любой начальной позиции в слове.
Мой закончил тем, что был написан в сценарии оболочки (хотите верьте, хотите нет) и использовал словарь, полученный из Linux, в качестве инструмента поиска слов. Если вы знаете, что у вас есть 5-буквенное слово, начинающееся с «app», его довольно просто использовать:
grep '^app..$' words.txt
, чтобы получить список всех допустимых возможностей.
И, поскольку каждое слово было найдено, оно было скопировано в файл clues.txt, который содержал как слово, так и несколько возможных подсказок. Фактическим форматом было использование {count, word, clue}, где одно и то же слово может существовать в нескольких строках с разным ключом - это позволило использовать конвейер от grep до sort, так что менее употребляемые слова / подсказки всплыли наверх ( всякий раз, когда использовалось слово / подсказка, его счет увеличивался, что уменьшало вероятность его использования в следующий раз).
Как только этот файл имел приличный размер, программа сначала использовала бы его для поиска слов, и, только если он не был найден, он вернется к файлу слов (без подсказок), где потребуется ручное вмешательство.
Это на самом деле оказалось довольно хорошим делом. Это было не слишком быстро, но мне не нужно было генерировать его каждые три секунды - это было для рассылки сообщества, рассылаемой раз в неделю.
Теперь, когда вы изменили вопрос на вариант Scrabble, на самом деле это намного сложнее.
Вы должны принять во внимание буквы, которые у вас есть, буквы на доске и тот факт, что есть гораздо больше мест, которые вы должны оценить. Это делает метод грубой силы намного сложнее.
То, что я хотел бы сделать в качестве начального среза, - это выбрать случайно выбранные возможности (начальная позиция и направление на доске), а затем использовать тот же алгоритм, что и для варианта кроссворда выше, чтобы найти все слова, которые могут поместиться там. Затем, если у вас есть буквы, соответствующие этому слову, сохраните его (вместе с его счетом) в списке.
Имейте в виду, что вам нужно остерегаться других слов на доске.
Я бы продолжал изучать возможности до тех пор, пока:
- Ваш список достаточно велик, чтобы выбрать.
- у вас закончилось время.
- вы изучили достаточно возможностей, чтобы удовлетворить свой уровень компетенции.
Это последнее важно - если вы играете новичка, вы не хотите исчерпывающе исследовать миллионы возможностей.
Затем выберите лучший ход из своего списка (или, возможно, не самый лучший, если играете на уровне новичка - все зависит от того, насколько хорошим вы хотите, чтобы компьютер был).