2

我正在尝试创建一个简单的 Java 生成器填字游戏（瑞典填字游戏）——只是为了好玩。我从网上下载了词汇（约30万字）。这些单词我保存在 HashMap 中（按字长排序）。生成器的输入是 X 和 Y 的大小以及一个谜题。我随机插入矩阵的拼图

但我无法找出一个可行的算法来填充矩阵的其余部分。

例如：

X X X X
X D O G
X X X X

有人有什么建议吗？或者网上有什么有用的文章？谢谢你。

4

1 回答 1

4

此处描述了一种用于编译填字游戏（如瑞典语、斯堪的纳维亚语等）的算法（当然还有其他 :)）

https://stackoverflow.com/a/23435654/3591273

更新：发布给出的 SO 链接中描述的算法的主要步骤（根据评论）

  1. 算法的第一步是随机选择一个空词槽（网格词），并用其相关词表中的候选词填充它（随机化可以在算法的连续执行中产生不同的解决方案）（复杂度 O(1) 或 O( N))

  2. 对于每个仍然为空的词槽（与已填充的词槽有交集），计算一个约束比率（这可能会有所不同，简单的是该步骤中可用解决方案的数量）并按此比率对空词槽进行排序（复杂度 O(NlogN ) 或 O(N) )

  3. 循环遍历上一步计算的空词槽，并为每个空词槽尝试多个候选解（确保保留“弧一致性”，即如果使用该词，则网格在此步骤之后有解）并根据下一步的最大可用性（即，如果当时在那个地方使用这个词，则下一步有最大可能的解决方案，等等。）（复杂度 O(N*MaxCandidatesUsed) ）

  4. 填写该单词（将其标记为已填写并转到步骤 2）

  5. 如果没有找到满足步骤 .3 标准的单词，请尝试回溯到上一步的另一个候选解决方案（此处的标准可能有所不同）（复杂度 O(N)）

  6. 如果找到回溯，则使用替代方法并可选地重置任何可能需要重置的已填充单词（再次将它们标记为未填充）（复杂度 O(N) ）

  7. 如果没有找到回溯，则找不到解决方案（至少使用此配置、初始种子等）

  8. 否则，当所有单词都填满时，您有一个解决方案

该算法对问题的解决方案树进行随机一致游走。如果在某个时候出现死胡同，它会回溯到前一个节点并遵循另一条路线。直到找到解决方案或用尽各种节点的候选者数量。

一致性部分确保找到的解决方案确实是一个解决方案，随机部分能够在不同的执行中产生不同的解决方案，并且平均具有更好的性能。

PS试图避免在不同的SO答案之间来回复制粘贴，但是好的，也许一些摘要可能有用

于 2014-05-02T20:25:14.423 回答