TheF#WORD - 填字游戏生成器
4.96/5 (8投票s)
使用 F# 实现的填字游戏生成器。
引言
本文讨论了构建填字游戏的算法。文中描述了几种可以减少搜索时间的技术和启发式方法。该算法使用 F# 实现。
背景
填字游戏构建是一个约束满足问题，属于 NP 复杂度类。为了减少搜索空间，该算法采用了以下技术：
- 最受约束变量启发法 (most constrained variable heuristics) - 用于选择下一个要填充的模式
- 最少约束值启发法 (least constrained value heuristics) - 用于选择填充所选模式的单词
- 前向检查 (forward checking) - 用于保持可用单词列表与填字游戏的当前状态一致
- 回溯跳转 (backjumping) - 用于返回导致不一致的模式
- 树剪枝 (tree pruning) - 用于移除已知会导致死胡同的单词
所有这些主题都将在以下章节中讨论。
示例
为便于说明，我们构建了一个简单的字典来演示算法的某些行为。
下图显示了使用简单字典的算法单次运行情况。此外，为了得到可复现的示例，我们禁用了随机行为。此示例将用于展示算法的不同方面。
 |
| 使用简单字典的算法运行情况 |
填字游戏表示法
填字游戏表示为一个二维的字段数组。每个字段由几个属性描述：
- 字母 (letter) - 当前占据该字段的字母（特殊情况：
'_'- 空字段，'#'- 阻挡字段） - 填充计数 (fill count) - 存储该字段所属的模式中当前已填充的数量
- 冲突标记 (conflict marking) - 表示在最近一次尝试中，由于不一致性而无法填充其某个模式。
- 模式引用 (pattern references) - 该字段所属的水平和垂直模式的索引
字段被分组为算法操作的模式。模式有两个重要的状态：
- 选项 (options) - 对于当前填字游戏状态有效的、可用于填充该模式的单词池。
- 时间戳 (stamp) - 模式被填充时所在的算法步骤编号。
水平和垂直模式保存在单独的列表中，以便在搜索相连模式时更快地查找。模式引用实际上是这些列表中的索引。模式还具有全局唯一的 ID，因此算法可以在某些步骤中避免多次使用/处理同一个模式。
模式选择
算法每一步的第一件事是决定接下来应该填充哪个模式。算法选择可用单词数量最少的模式。这样做是为了让算法能尽早遇到不可避免的死胡同，并及早剪除错误的搜索路径。这种启发法被称为最受约束变量 (most constrained variable)。
如前所述，算法为每个模式维护一个有效单词列表。这个列表被称为模式的选项。因此，要选择最受约束的模式，只需找到选项数量最少的模式即可。这种方法的副作用是，连续填充的模式不一定相连，这不幸地使回溯变得更加复杂，但这是值得的。
单词选择
选定模式后，下一个决定是选择哪个单词来填充该模式。这次采用相反的方法。选择从相连模式中排除最少选项的单词，这为后续搜索留下了更大的灵活性。这种启发法被称为最少约束值 (least constrained value)。
单词的权重计算如下：
其中 \(\left | P_{i} \right |\) 是在假设单词 \(w\) 被选中的情况下，第 \(i\) 个未填充的相连模式的剩余选项数量。使用乘积而非求和是为了排除那些会导致某个未填充模式变得不一致的单词 (\(\left | P_{i} \right | = 0\))。
对所选模式的所有选项进行加权计算成本太高，尤其是在搜索的早期阶段，因此只考虑有限数量的单词。算法仅从单词池中取出几个单词，并选择权重最大的一个。一旦单词被选中，它就会从模式的选项中移除。
前向检查
一旦选择了单词，该选择所施加的约束就会传播到相连的未填充模式，这样只有有效的单词会作为这些模式的选项保留下来。这被称为前向检查 (forward checking)。
这一步是必要的，不仅是为了进行不一致性检查，也是为了获得前面已经描述过的最受约束变量。因此这两者是相辅相成的。可以实现更复杂的相容性检查，如弧相容性（AC-3 算法），但这些操作可能成本高昂。
在单词选择阶段，为了计算单词权重，已经生成了未填充模式的新选项集，因此这一阶段会重用这些选项集。剩下唯一要做的就是保存新的模式选项。
回溯跳转
一旦算法发现一个无法填充的模式，它必须返回到之前填充的某个模式，并用另一个单词填充它，希望问题能得到解决。这是算法中最复杂的部分。
朴素的回溯方法是为最近填充的模式选择另一个单词，但这远非最佳方式。简单回溯效率低下的原因是模式填充的顺序。由于算法首先填充最受约束的模式，因此在两个连续步骤中填充的模式可能根本不相连。如果是这种情况，那么更改第一个模式的单词并不能解决第二个模式的不一致性，只会浪费 CPU 周期。
更好的方法是只返回到与不一致模式相连的模式。这种技术被称为回溯跳转 (backjumping)。
为了解决这个问题，算法为每个填充的模式标记一个其被填充时的步骤编号。这个附加信息使得可以恢复模式被填充的顺序。现在可以确定应该更改哪个模式以及受该更改影响的所有模式的列表。
回溯跳转执行的步骤如下：
- 将不一致模式的所有字段标记为冲突
算法简单地为不一致模式的每个字段设置冲突标记。
- 确定算法需要回溯跳转到的目标模式
目标是最近填充的、比不一致模式填充得更早且与之相连的模式。为了确定哪个模式满足此条件，算法使用前面描述的时间戳。如果找不到这样的模式，则使用全局最近填充的模式作为目标。
回溯跳转到不相连的模式 步骤 #8 和 #9 演示了这种情况。如果这也失败了，意味着搜索回到了起点，并且没有更多选项可用。这表示搜索结束，填字游戏构建失败。
- 撤销所有依赖于回溯跳转目标的模式
一旦找到目标，所有依赖于它的模式都必须被撤销。为了生成这些模式的列表，算法从目标开始，并添加所有在目标之后填充的相连模式。对添加到列表中的每个新模式递归地重复此过程。列表完成后，列表中模式的字段会根据新的填充计数进行更新，并在必要时清除。
- 为所有受影响的模式恢复选项
必须根据保留填充状态的基础字段的值，为每个被撤销的模式重新生成可能单词的列表。前面描述的撤销过程也会影响到与被撤销模式相连的未填充模式。因此，受影响模式的最终列表是已清除模式和与它们相连的未填充模式的并集。对于列表中的每个模式，算法通过将字典中的单词与模式字段的状态进行匹配来形成单词列表。
- 剪枝目标模式的选项
剪枝过程在下一节中描述。
树剪枝
一旦算法回溯，就可以确定目标模式的哪些部分导致了问题，因此可以从有效选项列表中移除那些会重复同样错误的选项。
为了剪枝选项，算法将根据模式字段的冲突标记构建一个过滤器。如前所述，每次发现不一致模式时，其所有字段都会被标记为冲突。这些标记在回溯跳转过程中被保留和累积，只有在模式成功填充时才会被清除。
 |  |
| 将不一致模式的字段 标记为冲突 | 在填充模式后 清除冲突标记 |
当回溯跳转到达其目标时，它需要做的就是移除那些与被标记字段模式相匹配的单词。
 |
| 剪枝过程演示 |
剪枝的效果可以在步骤 #9 和 #10 之间看到。在单词 AAAAA 未能产生解决方案后，算法选择了 DDDBB，尽管在字典中它前面还有 BBBAAA。这种方法相当简单，可以开发更复杂的算法，通过构建限制性较小的过滤器来剪枝更多选项，但本文并未实现。
 |
| 非最优剪枝过滤器 |
这个潜在的尝试序列会创建一个 ___AA 过滤器用于剪枝，但由于这两个不一致的模式不相互依赖，更好的选择是创建两个过滤器：___A_ 和 ____A，因为这对过滤器会移除更多的选项。
代码
填字游戏的字段由 CwField 记录表示
type CwField =
{ Letter : char
HorRef : int
VerRef : int
Count : int
Conflicted : bool }
模式由 CwPattern 类表示
type CwPattern(grid : CwField [,], dictionary : string array,
direction : CwDirection, no : int, xs : int, ys : int, length : int) =
// prune current options according filter produced
// using conflicted markings on underlying fields
member m.PruneOptions()
// restore all options according to state of underlying fields
member m.RestoreOptions()
// sets new options for the pattern
// options generated by the algorithm during word selection phase
member m.UpdateOptions(opts : string array)
// updates underlying fields with letters and increment their fill count
// removes the word from remaining options
member m.Fill(word : string, step : int)
// clears letters of underlying fields and decreases their fill count,
// but it keeps remaining options
member m.Undo()
// marks all underlying fields of pattern as conflicted
member m.MarkConflicted()
// array of letters in stored in underlying fields
member m.Letters
// tests whether any underlying field is marked as conflicted
member m.Conflicted
// string of letters in stored in underlying fields
member m.Word
// unique ID of the pattern in the crossword
member m.No
// X position of the first field
member m.X
// X position of the first field
member m.Y
// number of letters in the pattern
member m.Length
// direction of the pattern: horizontal or vertical
member m.Direction
// array of all remaining options
member m.Options
// number of options remaining
member m.Count
// step number if the algorithm in which the pattern was filled
member m.Stamp
填字游戏由 Crossword 类表示
type Crossword(filePath : string, dictionary : CwDictionary) =
// minimal pattern length
// shorter patterns are not considered during the construction
let minPatternLength
// maximal number of words that are taken into account
// when selecting word for a pattern
let maxWordPoolLength
// two-dimensional array of fields
let grid
// horizontal and vertical patterns
let hPatterns
let vPatterns
// returns list of crossword's patterns that are orthogonal
// to specified pattern
let orthogonal (pattern : CwPattern)
// selects pattern from queue of unfilled patterns
let selectPattern queue
// selects word for specified pattern
let selectWord (pattern : CwPattern)
// finds the target of backjump, clears the patterns
// and return them to queue
let backjump (start : CwPattern)
// main loop of the algorithm
member x.Solve(refreshRate : int)
// checks whether all patterns are correctly filled
member x.Check()
// prints crossword on console
member x.Print()
字典和谜题文件
字典存储在 words.txt 文件中，而谜题结构由 puzzle.txt 定义。'.' 表示可填字段，'#' 表示阻挡字段。
参考文献
历史
2017-03-14 - 初始版本发布