1. 简介
生成填字游戏（Crossword Puzzle）的核心目标是将一组单词合理地放置在一个网格中，使得这些单词可以交叉排列。本文将介绍几种生成填字游戏的算法，重点在于如何选择单词的放置位置，以构建出高质量的填字游戏。
2. 逐词放置算法
2.1. 算法原理
该算法的基本思路是将单词逐个放置到网格中，直到放置的单词数量达到上限或没有单词可放为止。具体步骤如下：
- 随机打乱单词列表；
- 放置第一个单词在网格中央；
- 对于后续每个单词，尝试将其每一个字母与网格中已有的字母匹配；
- 若匹配成功，则尝试放置该单词并检查是否合法；
- 若合法，则放置该单词并继续处理下一个单词；
- 若所有尝试都不合法或没有匹配项，则跳过该单词。
伪代码如下：
algorithm IterativePlacement(words, maxWords):
shuffle(words)
word <- pop(words)
crossword <- place(word, null, 0, 0, HORIZONTAL)
count <- 1
while count < maxWords and len(words) > 0:
word <- pop(words)
for letter in word:
for y in rows(crossword):
for x in cols(crossword):
if crossword[y, x] = letter:
placement, ok <- canPlace(word, crossword, x, y)
if ok:
crossword <- place(word, crossword, placement.x,
placement.y, placement.direction)
count <- count + 1
continue
return crossword
这个算法的实现中，place() 和 canPlace() 是关键函数，但未在伪代码中展开。它们分别用于将单词放置到指定位置，并判断该位置是否合法。
2.2. 示例演示
我们以单词 SHOP 作为第一个单词放置，初始结果如下：
接着尝试放置 GREEDS，发现其最后一个字母 S 与 SHOP 的首字母匹配，成功放置：
继续尝试 FAINT，由于无匹配字母，跳过。
再尝试 SIMPLIFY，其字母 P 与 SHOP 中的 P 匹配，放置成功：
最终生成完整填字游戏如下：
✅ 优点：实现简单，适合快速生成初版填字游戏
❌ 缺点：随机性强，结果可能不够紧凑、美观
3. 多次生成择优算法
3.1. 算法原理
为了提升填字游戏质量，我们可以生成多个网格，然后从中选择得分最高的一个。该算法的伪代码如下：
algorithm RepeatedGeneration(words, maxWords, iterations):
maxScore <- 0
result <- null
for i <- 0 to iterations:
crossword <- generate(words, maxWords)
score <- generateScore(crossword)
if score > maxScore:
maxScore <- score
result <- crossword
return result
我们可以根据设定的迭代次数生成多个填字游戏，并根据评分函数选择最优解。
3.2. 评分函数设计
评分函数是决定“最优”的关键。常见的评分维度包括：
- 填充率：填充的格子越多，得分越高；
- 网格比例：越接近正方形得分越高；
- 单词平均长度：可根据偏好选择长词或短词。
一个示例评分函数如下：
algorithm GenerateScore(crossword):
sizeRatio <- rows(crossword) / cols(crossword)
if rows(crossword) > cols(crossword):
sizeRatio <- cols(crossword) / rows(crossword)
filled <- 0
empty <- 0
for y in rows(crossword):
for x in cols(crossword):
if crossword[y, x] = null:
empty <- empty + 1
else:
filled <- filled + 1
filledRatio <- filled / empty
return (sizeRatio * 10) + (filledRatio * 20)
假设我们有两个网格，第一个得分 21.93，第二个得分 12.37，则选择第一个。
⚠️ 注意：评分函数需根据实际需求调整，不同评分标准会显著影响最终结果。
4. 多路径择优放置算法
4.1. 算法原理
之前的算法在找到第一个可放置位置后就直接放置单词，可能导致后续单词难以插入。为了解决这个问题，我们可以：
- 对当前单词尝试所有可能的放置位置；
- 对每个位置生成一个新网格并打分；
- 选择得分最高的那个作为最终放置结果。
伪代码如下：
algorithm RepeatedWordPlacement(words, maxWords):
shuffle(words)
word <- pop(words)
crossword <- place(word, null, 0, 0, HORIZONTAL)
count <- 1
while count < maxWords and len(words) > 0:
word <- pop(words)
placements <- [ ]
for letter in word:
for y in rows(crossword):
for x in cols(crossword):
if crossword[y, x] = letter:
placements <- append(placements, findPlacement(word, crossword, x, y))
bestScore <- 0
bestBoard <- crossword
for placement in placements:
newBoard <- place(word, crossword, placement.x, placement.y, placement.direction)
newScore <- generateScore(newBoard)
if newScore > bestScore:
bestScore <- newScore
bestBoard <- newBoard
if bestScore > 0:
crossword <- bestBoard
count <- count + 1
return crossword
4.2. 进一步优化
虽然该算法每次选择最优放置位置，但仍可能因局部最优导致整体结果不佳。例如，某次放置虽然当前最优，但限制了后续单词的插入。
为解决这一问题，可以构建一个“深度优先”的搜索树，尝试所有可能的路径，直到一定深度，然后选择最终得分最高的路径。这类似于经典的搜索算法（如 DFS、A* 等），适用于对结果质量要求较高的场景。
✅ 优点：生成结果更紧凑、美观
❌ 缺点：计算复杂度高，适合离线生成
5. 总结
本文介绍了三种生成填字游戏的算法：
| 算法名称 | 特点 | 适用场景 |
|---|---|---|
| 逐词放置 | 简单易实现，速度快 | 快速原型、轻量应用 |
| 多次生成择优 | 多次生成取最优，结果更佳 | 对质量有一定要求的场景 |
| 多路径择优放置 | 每次选择最优路径，结果最优 | 高质量填字游戏生成 |
未来可以尝试实现深度搜索算法，进一步提升生成质量。如果你对这个方向感兴趣，不妨动手实现一个完整的填字游戏生成器试试看。