python - Python 中的空填字游戏求解器

Question

我得到了一个矩阵，其中包含填字游戏的蓝图 - 当然是空的。目标是填满整个谜题 - 这是 Checkio 的一项任务，我已经为此苦苦挣扎了一段时间。

据我对复杂性的理解，这个问题没有完美的算法。不过，必须有最好的方法来做到这一点，对吗？我尝试了一些不同的方法，随着填字游戏和/或词典中单词数量的增加，结果并不是很好。

所以，我尝试过的一些事情:

• 简单的暴力破解。根本没有用，因为它一直被忽略并覆盖交叉路口。
• 在保留所有相关数据的同时进行暴力破解 - 使用特定字典按预期工作，使用适度大的，即使有字长优化。数字。
• 盲交叉填充 - 我认为最好不要打扰交叉单词，而是专注于在字母上。就像从 As 开始并检查您是否可以填写具有这些限制的整个填字游戏。如果它对某些人不起作用word，增加其中一个字母，然后再试一次。如您所料，结果很糟糕。
• 递归探索 - 在更简单的蓝图上工作得很好，但在更复杂的蓝图上表现平平。简单有问题很简单地解决了循环，但我没有找到路径 fork 再 fork 情况的合理解决方案稍后重新加入几个进一步的 split (所以没有什么可以解决第二个分支，但它不知道)。
• 最小化交叉路口 - 尚未对此进行测试，但看起来很有希望。这个想法是我找到最短的单词列表包含所有交叉点......也不与每个交叉点相交其他。然后我可以为每个单词使用一个生成器，并且然后检查是否存在具有这些交集的依赖词。如果他们没有，我只是从生成器中获取下一个词。

这就是我目前所在的位置。我决定在这里问这个问题，因为它已经到了我认为花费了比应该的时间更多的时间，即使那样我的最新想法甚至可能不是正确的方法。

那么，什么才是正确的做法？

编辑:输入是表示填字游戏的字符串列表和表示字典的字符串列表。输出是表示填充填字游戏的字符串列表。

填字游戏的例子:

['...XXXXXX', 
 '.XXX.X...', 
 '.....X.XX', 
 'XXXX.X...', 
 'XX...X.XX', 
 'XX.XXX.X.', 
 'X......X.', 
 'XX.X.XXX.', 
 'XXXX.....']

输出将是一个类似的列表，其中填充的是字母而不是点。

请注意，“词典”只是一个小型英语词典，而不是适合作为此谜题答案的单词列表。

Answer 1

So, what is the proper way to do it?

我不知道它是否是最优的，但我会使用 Floodfill 的原则.

数据结构:

填字游戏及其交集。根据字典中相应单词长度的单词数对它们进行排序。这很可能意味着您将从最长的单词之一开始。

可按字长访问的词典。

如果字典很大，那么能够快速找到具有特定 n:th 字母的特定长度的单词将是有益的，其中 n 对应于一个交点位置。

请注意，对于每个填字游戏单词，任何两个在所有交集处都匹配且具有相同字母的单词是等价的。因此，可以为每个填字游戏单词从字典中选择一个子集。子集是等价类的集合。因此，对于每个填字游戏单词，您可以创建一个字典子集，该子集最多包含 [字母表中的字母数] 的 [交叉点数] 次方。该子集将构成可能适合特定纵横字谜的等价类。

算法:

• 取第一个/下一个 Unresolved 填字游戏单词。分配给第一个/下一个合适的词。

• 走第一个/下一个十字路口。将第一个适合的单词分配给另一个填字游戏。

• 如果没有更多的路口可以继续前进，请返回您来自的路口并继续下一个路口。
• 如果字典中没有合适的单词，则回溯一个路口并搜索下一个合适的单词。