生成填字游戏的算法是如何产生的？为什么需要这个算法？以及如何解决生成填字游戏的问题？这个文章将算法的出现的原因以及解决方法。

十年前，我写了一个生成填字游戏的程序（在这个程序中，我使用了加密的规则，但是对于普通的填字游戏同样适用）。程序中有一个单词列表（包括相关的线索），这些单词按照使用频率的降序排列存储在一个文件中（这样不常使用的单词会排在文件的顶部）。然后，从客户端提供的池中随机选择一个模板，这个模板基本上是一个表示黑色方块和自由方块的位掩码。接下来，对于每个未完成的单词（即找到第一个空白方块，并查看右边（横向单词）或下方（纵向单词）是否也为空白方块），在文件中进行搜索，找到第一个符合条件的单词，同时考虑已经填入该单词的字母。如果没有符合条件的单词，就将整个单词标记为未完成，并继续下一个单词。最后，编译器需要填写一些未完成的单词（如果需要，还可以将单词和线索添加到文件中）。如果编译器无法想出任何想法，他们可以手动编辑填字游戏，更改约束条件，或者要求重新生成。当单词/线索文件达到一定大小（对于这个客户端，每天要添加50-100个线索），每个填字游戏通常只需要进行两到三次手动修正。

然而，这个算法对于我的情况并没有实际帮助，因为我只有大约6-12个单词。我的填字游戏更像是用户的学习练习，而不是一个单词谜题。尽管如此，这个算法还是很有趣！我考虑过这个问题很多次，但从未尝试过。现在，我想问一个关键的问题：这个算法的效果如何？仅适用于稀疏的填字游戏，还是也适用于密集的游戏（如论文中的游戏）？对于密集的填字游戏，需要多少线索？

我记得，即使对于密集的填字游戏，效果也相当不错。很多游戏都能够在无需干预的情况下完成，但仍然有大约五分之一的游戏需要添加一两个额外的单词。而且，我们在文件中有成千上万个单词。毫无疑问，回溯法可能有所帮助，但对于客户端来说，拒绝一个有5个未完成单词的游戏比想办法提供额外的线索更容易。根据我的观察，五个未完成单词是最多的情况。

生成填字游戏的算法（Algorithm to generate a crossword）的原因是为了创建一个具有良好质量的填字游戏或单词搜索游戏。该算法的解决方法如下：

1. 创建一个指定大小的网格和一个单词列表。

2. 对单词列表进行洗牌，并按从长到短的顺序对单词进行排序。

3. 将最长的单词放在左上角的位置（1,1），可以是垂直或水平方向。

4. 移动到下一个单词，在单词中的每个字母和网格中的每个单元格之间循环，寻找字母匹配的位置。

5. 当找到匹配时，将该位置添加到该单词的建议坐标列表中。

6. 遍历建议坐标列表，并根据单词与其他单词的交叉数量对单词的位置进行评分。评分为0表示不良的位置（与现有单词相邻）或没有交叉的单词。

7. 回到步骤4，直到单词列表耗尽。可以选择进行第二次遍历。

8. 现在应该有一个填字游戏，但由于一些随机位置的影响，质量可能好坏不一。因此，将此填字游戏缓存，并返回步骤2。如果下一个填字游戏在板上放置了更多的单词，则用它替换缓存中的填字游戏。这是时间有限的（在x秒内找到最佳填字游戏）。

最终，通过该算法可以得到一个不错的填字游戏或单词搜索游戏。它的运行速度相当不错，但如果有任何改进建议，请告诉我。较大的网格运行速度指数级下降；较大的单词列表运行速度线性下降。较大的单词列表也有更高的机会获得更好的单词位置数。

可能的改进方法是为其他单词提供更好的字母匹配可能性。可能的方法是按照每个单词所包含的不同字母的数量对单词进行排序，这通常会得到相同的结果。使用Python的array.sort(key=f)方法进行排序是稳定的，这意味着（例如）仅按长度对字母表排序的单词列表将保持所有8个字母的单词按字母顺序排序。

有用户反馈称，提供的网站链接无法打开，并且主要域名只会重定向到Twitter。询问是否有更新的代码链接。以下是Bryan的生成器的克隆版本链接：github.com/jeremy886/crossword_helmig。

生成填字游戏的算法

生成填字游戏的算法可以通过以下步骤实现：

1. 将所有的单词按照长度从长到短进行排序。

2. 将第一个单词放置在游戏板上。

3. 取下一个单词。

4. 搜索已经放置在游戏板上的所有单词，并查看是否存在可能的交叉位置（即是否存在共同的字母）。

5. 如果存在该单词的可能位置，循环遍历已经放置在游戏板上的所有单词，检查新单词是否会产生冲突。

6. 如果该单词不会破坏游戏板的完整性，则将其放置在该位置并回到步骤3，否则继续搜索其他位置（步骤4）。

7. 重复上述步骤，直到所有单词都被放置或无法放置。

然而，这个算法生成的填字游戏通常质量较差。为了得到更好的结果，可以进行以下改进：

1. 在生成填字游戏的结束时，根据放置的单词数量（越多越好）、游戏板的大小（越小越好）以及高度与宽度之间的比例（越接近1越好），给游戏打分。生成多个填字游戏，然后比较它们的得分并选择最优解。

2. 在放置新单词时，不要立即放置在找到的可接受位置上，而是根据它增加网格的大小和存在的交叉点数量给该位置打分（理想情况下，每个单词应该被2-3个其他单词交叉）。跟踪所有位置及其得分，然后选择最佳位置。

这个算法的效率并不是很高，但对于少量单词（少于10个），程序可以在毫秒内计算出所有可能的解决方案。算法的复杂度是指数级的。编写基本算法来穷举所有可能的组合是相对容易的，难点在于需要一些“捷径”来防止程序尝试所有无用的解决方案。

关于“检查新单词是否干扰”的问题，如果新单词与已存在的单词并排放置，会在相邻的方格中生成无意义的字母组合。例如：

LEMON

ERASE

如果“LE”、“ER”和“MA”等不是单词列表中的单词，这是错误的。另一方面，直接拒绝这样的相邻情况可能会放弃一些真正好的游戏板，比如：

W LEMON

ERASE

NEXUS

T T

是的，我知道你的意思 - 我放弃了这些选项，因为即使它们可以创建真正好的游戏板，检查起来太困难了（也就是说，我懒得检查），而且很可能只是干扰而已。

通过上述算法，可以生成填字游戏。还可以在这里找到一个实现了类似方法的例子：colab.research.google.com/drive/…