填字游戏生成器(瑞典填字游戏)- Java

Question

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

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

例如:

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

有人有什么建议吗？或者互联网上一些有用的文章？谢谢。

Answer 1

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

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 试图避免在不同的答案之间来回复制粘贴，但好吧，也许一些总结可能会有用