生成填字游戏的算法

关闭。这个问题需要更多 focused 。它目前不接受答案。




21 天前关闭。










锁定。这个问题及其答案是 locked 因为这个问题是题外话但具有历史意义。它目前不接受新的答案或互动。








给定一个单词列表，你会如何将它们排列成一个填字游戏网格？

它不必像对称或类似的“正确”填字游戏:基本上只是输出每个单词的起始位置和方向。

最佳答案

我想出了一个可能不是最有效的解决方案，但它运行良好。基本上:

按长度降序对所有单词进行排序。

取第一个字放在黑板上。

取下一个字。

搜索已经在板上的所有单词，看看是否有任何可能的交叉点(任何常见的字母)与这个单词。

如果这个词有一个可能的位置，循环遍历黑板上的所有词并检查新词是否干扰。

如果这个词没有打断棋盘，则把它放在那里并转到第3步，否则继续寻找一个地方(第4步)。

继续这个循环，直到所有的单词都被放置或无法放置。

这使得一个有效但通常很差的填字游戏。为了得到更好的结果，我对上面的基本配方做了一些改动。

填字游戏结束时，根据填字数(越多越好)、棋盘的大小(越小越好)、高宽比(越接近 1 越好)。生成多个填字游戏，然后比较它们的分数并选择最好的一个。

我决定在任意时间内创建尽可能多的填字游戏，而不是运行任意次数的迭代。如果你只有一个小的单词表，那么你会在 5 秒内得到几十个可能的填字游戏。更大的填字游戏可能只能从 5-6 种可能性中选择。

放置新词时，不要在找到可接受的位置后立即放置它，而是根据它增加网格大小的程度和交叉点的数量(理想情况下，您希望每个词都被 2-3 个其他词交叉)。跟踪所有位置及其得分，然后选择最佳位置。

关于生成填字游戏的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/943113/