给定网格的填字游戏算法

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于互联网的全局受众。如需帮助使这个问题更广泛适用，visit the help center .




8年前关闭。




在我写一些关于这个问题的东西之前，我需要让你知道:

这个问题是我的作业(我有大约 1 周的时间返回工作计划)

我每天都在解决这个问题大约一个星期，试图找出我自己的解决方案

我不是要求完整的程序；我需要对算法有一个大致的了解

问题:

给定:一个词表和一个“网格”，例如:

网格(X 表示任何字母):

X X 
XXXX
X X
XXXX

词汇表:

ccaa
baca
baaa
bbbb

您必须找到示例“解决方案” - 是否可以将单词列表中的单词放入给定的网格中？如果至少有一个解决方案，请打印一个(以正确者为准)。如果没有 - 打印消息，则表示没有可能的解决方案。对于给定的示例，有一个解决方案:

b c 
baca
b a 
baaa

我很难写出我已经尝试过的所有内容(因为英语不是我的母语，而且我也有很多想法错误的论文)。

我的天真算法是这样工作的:

第一个词只需要合适的长度，所以找到任何(第一个？)长度合适的词(我将使用给定的示例网格和词表来演示我的想法):

c X 
cXXX
a X
aXXX

对于第一个常用字母(在 2 个单词的交叉处)，找到适合网格的任何(第一个)单词(因此，在适当的位置有适当的长度和常用字母)。如果没有这样的词，回到(1)并取另一个第一个词。在原始示例中，没有以“c”开头的单词，因此我们返回到 (1) 并选择下一个单词(此步骤重复几次，直到第一个单词为“bbbb”)。现在我们有:

b X 
bXXX
b X
bXXX

我们正在寻找以“b”开头的单词，例如:

b X 
baca
b X
bXXX

一般过程:尝试找到适合给定网格的单词对。如果没有这样的话，回到上一步并使用另一个组合 - 如果没有这样的话 - 没有解决方案。

以上都是乱七八糟的，希望你至少看懂了问题描述。我写了一个算法的草稿，但我不确定它是否有效以及如何正确编码(在我的例子中:c++)。此外，在某些情况下(即使在上面的示例中)我们需要找到依赖于 2 个或更多其他单词的单词。

也许我只是看不到明显的东西，也许我太笨了，也许……嗯，我真的很想解决这个问题。我不太懂英语，无法准确描述我对这个问题的看法，所以我不能把我所有的笔记都放在这里(我试图描述一个想法，但很难)。信不信由你，我花了很多时间试图找出解决方案，但我几乎什么都没有......

如果你能描述一个解决方案，或者给出一个如何解决这个问题的提示，我将非常感激。

Answer 1

corsword问题是NP-Complete ，所以你最好的尝试是蛮力:尝试所有的可能性，当一个可能性是有效的时停止。当您用尽所有可能的解决方案时返回失败。

证明这个问题是 NP-Complete 的减少可以在 this article 中找到第 3.3 节

使用 backtracking 的蛮力解决方案可能是:[伪代码]:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words\{word},possibleSol)
       if (ret != None):
          return ret
   return None

在这里我们假设 fillFirst()是一个函数，它填充第一个尚未填充的空间 [first 实际上可以是任何一致的空格顺序，但它应该是一致的!] 和 isValid()返回一个 bool 值，指示给定的网格是否是有效的解决方案。