Кроссворд с заданной сеткой и словами

У меня есть сетка кроссвордов, например

+-----+
|  *  |
|     |
+-----+

и список слов

a
ababa
bb
cc
ba
bb
ca
cb

Каждое слово должно быть использовано. Цель состоит в том, чтобы найти все варианты, как этот кроссворд может быть решен, в этом случае есть два варианта —

bb*cc
ababa

а также

cc*bb
ababa

Вот несколько более сложных кроссвордов, например:

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

со списком из 20 слов и т. д.

Я пытался создать алгоритм для решения этой проблемы, но безуспешно. Кто-нибудь может мне помочь?

-1

Решение

Прежде всего обратите внимание, что даже определение того, является ли кроссворд «разрешимым» с использованием данного словаря, является 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

0

Другие решения

Других решений пока нет …