Кроссворд с заданной сеткой и словами
У меня есть сетка кроссвордов, например
+-----+
| * |
| |
+-----+
и список слов
a
ababa
bb
cc
ba
bb
ca
cb
Каждое слово должно быть использовано. Цель состоит в том, чтобы найти все варианты, как этот кроссворд может быть решен, в этом случае есть два варианта —
bb*cc
ababa
а также
cc*bb
ababa
Вот несколько более сложных кроссвордов, например:
+-----+
| * |
| |
| *|
| * |
| * *|
| * |
| |
+-----+
со списком из 20 слов и т. д.
Я пытался создать алгоритм для решения этой проблемы, но безуспешно. Кто-нибудь может мне помочь?
Решение
Прежде всего обратите внимание, что даже определение того, является ли кроссворд «разрешимым» с использованием данного словаря, является NP-Hard1, поэтому даже определение, существует ли 0 или более, решение не может быть сделано полиномиально (если P = NP).
Таким образом, альтернативой является использование исчерпывающий поиск Решение — просто попробуйте все возможности «разместить» слова, а затем убедитесь, что это решение действительно.
Псевдокод:
solve(words,grid):
if words is empty:
if grid.isValidSolution():
print grid as a possible solution
return
for each word in words:
candidate<- grid.fillFirstSpace(word)
solve(words\{word},candidate)
(1) Ссылка: P равно NP раздел 3.3
Другие решения
Других решений пока нет …