Python中的空填字游戏解算器

Question

我给了一个包含填字游戏蓝图的矩阵 - 当然没有填充.目标是填补整个难题 - 这是Checkio的任务,而且我已经在这方面苦苦挣扎了很长一段时间.

根据我对复杂性的理解,对于这个问题没有完美的算法.不过,必须有最好的方法来做到这一点,对吧？我尝试了一些不同的东西,并且随着填字游戏和/或字典中单词数量的增加,结果并不那么好.

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

• 简单的暴力迫使.完全没有工作,因为它一直忽略和覆盖交叉点.
• 在保留所有相关数据的同时强制执行 - 按照特定字典的预期工作,即使使用字长优化,也会变成一个中等大小的地狱.数据.
• 盲目交叉填充 - 这个想法,我认为最好不要打扰交叉的单词,而是专注于字母.就像从As开始一样,检查你是否可以用这些限制来填充整个填字游戏.如果它对某些单词不起作用,请递增其中一个字母并再次尝试整个单词.如你所料,结果非常糟糕.
• 递归探索 - 在更简单的蓝图上完美地工作,但与更复杂的蓝图相比变得平淡无奇.有一个简单循环的问题已经解决得足够简单了,但我没有找到一个合理的解决方案,因为路径分裂然后再重新加入几个进一步的分裂(所以没有什么可以解决第二个分支,但它没有我不知道.
• 最小化交叉点 - 尚未对此进行测试,但看起来很有希望.我的想法是找到包含所有交叉点的最短的单词列表......它们也不相互交叉.然后我可以为每个单词使用生成器,然后检查是否存在具有这些交叉点的​​依赖单词.如果他们不这样做,我只是抓住发电机的下一个字.

这就是我目前所处的位置.我决定在这里询问这个问题,因为我已经知道它需要花费更多的时间,而且我的最新想法甚至可能不是正确的方法.

那么,做到这一点的正确方法是什么？

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

填字游戏的例子:

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

输出将是一个类似的列表,填充字母而不是点.

请注意,'词典'就是这样,一个小的英语词典,而不是作为这个难题的答案的单词列表.

Answer 1

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

我不知道这是否是最佳的，但我会使用Floodfill的原则。

数据结构：

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

字典可按字长访问。

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

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

算法：

• 取第一个/下一个未解决的填字游戏单词。为其指定第一个/下一个合适的单词。

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

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