生成填字游戏的算法 [英] Algorithm to generate a crossword

问题描述

给定一个单词列表，你会如何将它们排列成纵横字谜网格?

Given a list of words, how would you go about arranging them into a crossword grid?

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

It wouldn't have to be like a "proper" crossword puzzle which is symmetrical or anything like that: basically just output a starting position and direction for each word.

推荐答案

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

I came up with a solution which probably isn't the most efficient, but it works well enough. Basically:

1. 按长度降序对所有单词进行排序.
2. 说出第一个单词并将其放在黑板上.
3. 接下一个词.
4. 搜索已经出现在黑板上的所有单词，看看是否有任何可能的交叉点(任何常见的字母)与这个单词.
5. 如果这个词有可能的位置，循环遍历黑板上的所有词并检查新词是否干扰.
6. 如果这个词没有打破板子，那么把它放在那里并转到第 3 步，否则，继续寻找一个地方(第 4 步).
7. 继续这个循环，直到所有单词都被放置或无法放置.

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

This makes a working, yet often quite poor crossword. There were a number of alterations I made to the basic recipe above to come up with a better result.

• 在生成填字游戏结束时，根据放置的单词数量(越多越好)、棋盘的大小(越小越好)以及高宽比给它打分(越接近 1 越好).生成多个填字游戏，然后比较它们的分数并选择最好的一个.
  • 我决定在任意时间内创建尽可能多的填字游戏，而不是运行任意次数的迭代.如果你只有一个小的单词表，那么你会在 5 秒内得到几十个可能的填字游戏.更大的填字游戏可能只能从 5-6 种可能性中选择.

  这篇关于生成填字游戏的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！