小编Lai*_*ius的帖子

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

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

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

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

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

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

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

填字游戏的例子:

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

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

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