Python中的空填字游戏求解器 [英] Empty crossword solver in Python

问题描述

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

I'm given a matrix containing a blueprint of a crossword puzzle - unfilled, of course. The goal is to fill the whole puzzle - it's a task from Checkio, and I've been struggling with this for quite some time now.

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

From what I understand of complexity, there's no perfect algorithm for this problem. Still, there has to be the best way to do this, right? I've tried some different things, and results were not that good with increasing number of words in the crossword and/or dictionary.

所以， ve尝试过：

• 简单的暴力破解。根本不起作用，因为它一直忽略
  并覆盖交集。


• 强行强制执行，同时保留所有相关数据-在特定字典中按预期运行，变成了地狱即使是经过字长优化，也有一个
  中等大小的广告。数字。


• 盲点交叉填充-我认为最好不要打扰相交的单词，而应将
  放在字母上，这是一个更好的主意。像以As开头，检查是否可以用这些限制来填充
  整个填字游戏。如果它对于某些
  单词不起作用，请递增其中一个字母，然后再次尝试整个操作。
  结果令人惊讶，就像您期望的那样。


• 递归探索-在更简单的蓝图上可以很好地工作，而在更复杂的蓝图上却无法实现。存在一个简单的
  循环的问题，该问题已经足够简单地解决了，但我没有找到
  的合理解决方案，以解决路径拆分的问题，然后
  之后又加入了几个其他拆分（因此，
  没有剩下的用于解决第二个分支的方法，但是它不知道。）


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

• simple brute forcing. Did not work at all, as it has been ignoring and overwriting intersections.
• brute forcing while keeping all the relevant data - worked as expected with a specific dictionary, turned to hell with a moderately big one even with word-length optimization. Figures.
• blind intersection filling - the idea where I thought it would be better not to bother with the intersecting words, instead focusing on the letters. Like start with As and check if you can fill the whole crossword with these restrictions. If it did not work for some word, increment one of the letters and try the whole thing again. Results were abysmal as you can expect.
• recursive exploring - worked perfectly on more simple blueprints, but fell flat with more complex ones. There was an issue with simple loops which was resolved simply enough, but I did not find a reasonable solution for the situation where the path splits and then rejoins several further splits later (so there's nothing left to solve for the second branch, but it doesn't know that).
• minimizing intersections - haven't tested this yet, but it looks promising. The idea is that I find the shortest list of words containing all intersections... that also don't intersect with each other. Then I can just use a generator for each of those words, and then check if the depending words with those intersections exist. If they don't, I just grab the next word from a generator.

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

And this is where I'm currently at. I decided to ask about this here as it's already at that point where I think it took more time than it should have, and even then my latest idea may not even be the proper way to do it.

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

So, what is the proper way to do it?

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

Input is a list of strings representing the crossword and a list of strings representing the dictionary. Output is a list of strings representing the filled crossword.

填字游戏的示例：

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

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

The output would be a similar list with filled letters instead of dots.

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

Note that the 'dictionary' is just that, a small English dictionary and not a list of words fitted as answers for this puzzle.

推荐答案

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

So, what is the proper way to do it?

我不知道它是否最佳，但是我会使用填充。

I don't know if it is optimal, but I would be using the principles of Floodfill.

数据结构：

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

Crossword words and their intersections. Sort them by the number of words in the dictionary for the corresponding word length. This will most likely mean that you will start with one of the longest words.

按单词长度可访问的词典。

Dictionary accessible by word length.

如果词典很大，能够快速找到具有特定 n ：th个字母，其中 n 对应于交点位置。

If the dictionary is large it would be beneficial to be able to quickly find words of a certain length with a specific n:th letter, where n corresponds to an intersection position.

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

Note that for each crossword word, any two words that fit and have the same letters in all intersections are equivalent. Thus, it is possible to select a subset from the dictionary for each crossword word. The subset is the set of equivalence classes. So for each crossword word you can create a subset of the dictionary that contains at most [the number of letters in the alphabet] to the power of [the number of intersections]. This subset would constitute the equivalence classes that might fit a particular crossword word.

算法：

• 采用第一个/下一个未解决的填字游戏单词。为它分配合适的第一个/下一个
  词。

• Take the first/next unsolved crossword word. Assign it the first/next word that fits.

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

Take the first/next intersection. Assign the other crossword word the first word that fits.

这篇关于Python中的空填字游戏求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！