9

我得到了一个包含填字游戏蓝图的矩阵——当然是未填充的。我们的目标是填补整个谜题——这是 Checkio 的一项任务，我已经为此苦苦挣扎了很长一段时间。

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

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

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

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

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

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

还有一个填字游戏的例子：

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

填字游戏

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

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

4

1 回答 1

4

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

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

数据结构：

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

字典可按字长访问。

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

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

算法：

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

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

  • 如果没有更多的十字路口可以继续前进，请返回您来自的十字路口并继续下一个十字路口。
  • 如果字典中没有合适的词，则回溯一个交叉点并搜索下一个合适的词。
于 2017-08-31T11:29:08.980 回答