一个快速创建谜题的算法

Question

我在http://www.puzzles.ca/wordsearch/transportation.html上发现了一个谜题，需要在网格中找到单词，可以从8个方向读取单词。这引发了以下问题：

我们已经有一组单词，请找出一种算法将这些单词放入给定的n x m网格中，其中n和m是已知的。如果网格的大小刚好足以适应字母并且单词重叠在一起，那么创建合适的网格可能很难。您是否有任何建议来解决这个问题？

- puzzleenthusiast

---

当单词集合排列在网格中时，您是否应该用随机字符填充空白处（会有空白处吗）？您必须确保不会意外创建新单词吗？ - Anders Lindahl

类似于生成纵横字谜的算法。 - Nick Dandoulakis

@Mehrdad，对算法的建议，尽可能快地执行。@Anders Lindahl：在我的情况下，其余的字母可以是任意的。 - puzzleenthusiast

由于这并非总是可能的，我认为你应该采用另一种方式。尝试将单词集放入它们可以适合的最小矩形中。您可以按字母顺序对单词进行排序，然后使用树尝试所有可能性。复杂度应该是类似于O（P ^ N）的东西，其中N是单词数，P取决于位置数量。 - Ricky Bobby

我认为如果网格很大且单词很多，将整个树放入内存需要太多的内存。我相信某种递归算法可以使用更少的内存完成任务。我在思考是否可以使用某种启发式搜索解决方案（最佳优先、IDA*、模拟退火）。但我无法评估这些算法的时间复杂度，或者我没有经验来判断它们是否有效。那么，对于这个问题，什么样的启发式方法会比较好呢？ - puzzleenthusiast

Answer 1

这个SO问题中描述了一个算法

https://dev59.com/8XNA5IYBdhLWcg3wfN2O#23435654

希望这能有所帮助。 更新：算法摘要（如前面链接中所述）。

1. 从网格中随机选择第一个空单词槽并填入合适的单词

2. 查找所有与已填充单词槽有交叉的空单词槽

3. 按约束比率（例如每个单词槽可用解决方案的数量）对它们进行排序

4. 循环遍历上一步中的空槽，并尝试一些候选单词（从可用单词中选择）

5. 选择填充网格一致性保持得当的单词槽和单词（即在填入此单词后，网格仍有解决方案），同时下一步的解决方案数最大（这可以最小化下一步的回溯），然后进入步骤2

6. 如果在上一步中没有找到单词，则尝试回溯到先前的单词并使用替代候选项（除非候选项已耗尽）

7. 可选地重置可能需要重置的任何单词槽（即将它们标记为空），然后进入步骤2

8. 如果没有找到回溯，则此配置无解

9. 如果所有空单词槽都已填充，则有一个解决方案

- Nikos M.

---

请问您能否提供更多的信息，而不仅仅是一个句子片段和链接呢？非常感谢！ - ElectronicGeek

这是用于填字游戏，而不是寻字游戏，因此它无法验证意外创建的匹配单词，你可能认为仍需要放置，甚至可能是多个，从而允许多个（包括错误的）解决方案。 - marcolz

@marcolz，鉴于我已经使用这个算法实现了专业的填字游戏制作者，我可以保证不会出现这种情况。如果一个空的单词槽确实被相交的填充单词槽填充，则会将其纳入考虑范围。有检查，但无法给出完整的实现，因为它很长，只能给出算法背后的一般思路。实际上，这些情况都受到了检查和照顾。 - Nikos M.