我有一个填字游戏网格，例如
+-----+
| * |
| |
+-----+
和单词列表
a
ababa
bb
cc
ba
bb
ca
cb
每个单词都必须使用。目标是找到如何解决这个填字游戏的所有变体，在这种情况下有两种变体-
bb*cc
ababa
和
cc*bb
ababa
一些更复杂的填字游戏看起来是这样的，例如：
+-----+
| * |
| |
| *|
| * |
| * *|
| * |
| |
+-----+
带有20个单词的列表等
我试图创建算法来解决这类问题，但没有成功。有人能帮我吗？
首先要注意的是，即使使用给定的字典来确定填字游戏是否"可解"也是NP难的1，因此即使确定是否有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节