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

我得到了一个包含填字游戏的蓝图的矩阵-当然没有填充。目标是填补整个难题-这是Checkio的任务，而我一直为此苦苦挣扎了很长时间。

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

因此，我尝试了一些方法:

简单的暴力破解。根本没有用，因为它一直在忽略
和覆盖路口。

保留所有相关数据的同时进行

暴力破解-在使用特定字典时按预期方式工作，并通过
即使采用字长优化，也可以算是中等大小。数字。

盲区交叉填充-我认为最好不要打扰相交的单词，而应集中精力
在信件上。像以As开头，然后检查是否可以填写
带有这些限制的整个填字游戏。如果对某些人不起作用
单词，增加字母之一，然后再尝试整个操作。
如您所料，结果令人震惊。

递归探索-可以在更简单的蓝图上完美运行，但在更复杂的蓝图上却表现平平。有一个简单的问题
循环已经足够简单地解决了，但是我没有找到一个
合理的解决方案，以解决路径 split 的情况，然后
稍后再加入其他几个分割区(因此没有任何剩余内容可用于
解决第二个分支，但它不知道)。

最小化交叉点-尚未对此进行测试，但看起来很有希望。我的想法是找到最短的单词列表
包含所有交叉点...也不会与每个交叉点相交
其他。然后我可以为每个单词使用一个生成器，然后
然后检查是否存在带有这些交点的从属词。如果
他们没有，我只是从生成器中获取下一个单词。

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

那么，什么是正确的方法呢？

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

填字游戏的示例:

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

输出将是带有填充字母而不是点的类似列表。

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

最佳答案

我不知道它是否是最佳选择，但我会使用Floodfill的原理。

数据结构:

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

字典可按字长访问。

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

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

算法:

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

取第一个/下一个交点。将另一个填字游戏单词分配为合适的第一个单词。

如果没有其他可继续的交叉路口，请返回您来自的交叉路口，然后继续下一个交叉路口。

如果词典中没有适合的单词，请回溯一个交集并搜索适合的下一个单词。