帮助填字游戏算法

Question

这样的问题在我的大学给了我，也许有人会有一个有趣的算法如何解决这个问题。在stackoverflow上有几种解决方案，但没有一个是可以的（因为他们正在循环所有可能性）。

问题：查找所有可能的组合给给定的表格，网格（矩形，见下面的输入）给定的单词。应该没有空闲单元，单词可以从左到右或从上到下。单词不能位于连续（列）字中。

输入：矩形区域，例如：

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

或

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

不同字被输入随后后（下一个输入数据）来填充该网格如：

cdi 
zobxzst 
tdxic 
r 
sc 
zro 
and etc ... 

数字最初是未知的，但输入直到标准输入 - 活动EOF结束。

输出：如果存在一个解决方案，则在填充的网格内输出该可能的解决方案。 如果没有解决方案或解决方案的数量，则输出0或确切的数字。

实施例：

（表输入）

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

然后词语cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

（每个作为输入，但在这里，由空格分开的）（仅1种溶液）

输出：

+-----+ 
|zro*h| 
|ogish| 
|bfkh*| 
|xvf*r| 
|za*c*| 
|sc*df| 
|tdxic| 
+-----+ 

重要提示：输入的网格仅受16（！）个单元限制，单词数量少于60个。我编写了一个算法，搜索所有可能的组合，但由于执行时间有限，到10秒我猜），这个问题不能用粗略的算法解决（例如， 15格15格，约60！可能或更多可能的排列，可以处理大约1天？在普通的2GHz PC上）。

也许还有另一种独特的解决方案。也许这个问题在编程时更具数学意义，也许可以使用一些左上角的组合，而不是上下？或者也许加权单元格？

P.S.我有3周的时间来解决这个问题，如果没有，我可以在3周后发布解决方案（好消息）;）

Answer 1

在stackoverflow上有几种解决方案，但没有一个是好的他们正在循环所有可能性）。

我的想法可能是错误的，那么：但这里有一个想法，我的头顶。

我写了通过所有可能的组合

如果有太多的搜索算法，那么问题可能是，你也搜索/通过是不可能的组合以及可能的组合循环。

例如，当您在左上角放置一个词像“的ZrO”，还有可以放置在垂直的话它下面很少有“可能”的组合：

1. 第一垂直字必须以“Z”开始
2. 第二垂直字必须带“R”
3. 第三垂直字开头必须以“O”
4. 的第二行字母（从放置垂直得到的组合开始字）本身必须是一个有效的字
5. 等

因此：

1. 挑选任何单词，并将其放置在左上角
2. 找到满足上述
3. 约束现有词如果你发现一个或多个这样的话，然后继续这样看看你是否能解决整件事情;或者，如果你失败了，然后再次尝试使用不同的初始字

摘要：

• 不生成每一个完整的网格，然后进行测试，看看它是否满足所有约束
• 相反使用限制为您打造的电网，以减少你测试

---

我建议个的可能性的数量在你解决网格问题时，从最初的单词开始。

而是在左上角测试每个字，一个更好的（例如，因为它教育部很快消除了不可能的事）的方式产生的起始位置[s]是：

• 查找最长的单词（如rgfvacd）
• 查找其交叉/加入吧
• 尝试把每个那些有效组合对电网

Answer 2

我sugges词所有可能的组合牛逼，你首先应该看你有没有填写的话是什么长度，在你的榜样：

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

你有两个7字母的单词，三个1个字母的单词，等等。

您应该根据计数对这个列表进行排序，并且首先尝试用最低计数的长度，在下一次迭代中，您应该列出您需要查找的单词列表 - 三个4个字母的单词开始用'a' - 你应该计算你在单词列表中留下了多少这些单词，然后选择一个单词中包含最少单词的单词 - 如果它是0，则返回。

希望它是有道理的。