c++ - 给定网格和单词的填字游戏

Question

例如，我有一个填字游戏网格

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

和单词列表

a
ababa
bb
cc
ba
bb
ca
cb

每个词都必须使用。目标是找到如何解决这个填字游戏的所有变体，在这种情况下有两个变体 -

bb*cc
ababa

和

cc*bb
ababa

一些更复杂的填字游戏看起来像这样，例如：

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

带有20个单词等的列表

我试图创建算法来解决这类问题，但没有成功。有人能帮我吗？

Answer 1

首先请注意，即使使用给定字典确定填字游戏是否“可解”也是NP-Hard ¹，因此即使确定是否有 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节