给定网格的填字游戏算法

Question

在我写一些关于这个问题的文章之前,我需要告诉你:

1. 这个问题是我的功课(我有大约1个星期的时间返回工作程序)
2. 我每天都在研究这个问题大约一个星期,试图弄清楚我自己的解决方案
3. 我不是要求完整的程序; 我需要一个关于算法的一般概念

问题:

给定:单词列表和"网格",例如:

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

X X 
XXXX
X X
XXXX

词汇表:

ccaa
baca
baaa
bbbb

你必须找到示例"解决方案" - 是否可以将wordlist中的单词装入给定的网格？如果至少有一个解决方案,请打印一个(无论哪个正确).如果没有 - 打印消息,那就没有可能的解决方案.举个例子,有一个解决方案:

b c 
baca
b a 
baaa

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

我的天真算法的工作原理如下:

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

   c X 
   cXXX
   a X
   aXXX
   

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

   b X 
   bXXX
   b X
   bXXX
   

   我们正在寻找一个以"b"开头的单词,例如:

   b X 
   baca
   b X
   bXXX
   

3. 一般过程:尝试找到适合给定网格的单词对.如果没有这样的话,请回到上一步并使用另一种组合 - 如果没有这样的话 - 没有解决办法.

上面的一切都是混乱的,我希望你至少能理解问题的描述.我写了一个算法草案,但我不确定它是否有效以及如何正确编码(在我的例子中:c ++).此外,有些情况(即使在上面的例子中)我们需要找到一个依赖于2个或更多其他单词的单词.

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

如果你能描述一个解决方案,或者提示如何解决这个问题,我会非常感激.

Answer 1

corssword问题是NP-Complete,所以你的最佳镜头是蛮力:只是尝试所有可能性,并在可能性有效时停止.当您用尽所有可能的解决方案时返回失败.

可以在本文第3.3节中找到证明此问题是NP-Complete的减少

使用回溯的暴力解决方案可能是:[伪代码]:

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()是一个函数,它填充了第一个尚未填充的空间[首先实际上可以是空格的任何一致排序,但它应该是一致的!],并isValid()返回一个布尔值,表明给定的网格是否是有效解决方案