你一定见过这种东西：

C A N T O R
G A U S S .
E U L E R .
A B E L . .
. . . . . .
. . . . . .

一个字母方格，藏着若干单词——横着、竖着，有时候斜着。找到它们是游戏，但出这道题才是有趣的工程问题：给你几个单词，怎么把它们都塞进格子里？

这件事比看起来难。单词可以斜放，可以反向，两个单词可能在某个格子相交——相交处的字母必须相同。暴力枚举所有摆法代价太大，还容易遗漏。

这篇文章介绍一种优雅的做法：把”出谜题”变成一个填色游戏，然后用舞蹈链算法自动求解。顺带揭露一个很容易写错的细节——以及 Knuth 用来修复它的一个小技巧。

先把问题说清楚

给你 4 个词：ABEL、CANTOR、GAUSS、EULER，一个 6×6 的格子，要求：

  • 每个词恰好放一次
  • 可以横放、竖放、斜放（8 个方向）
  • 如果两个词在某格相交，该格字母必须相同

问：有多少种合法的摆法？

答案是 244,792 种。

手算？不可能。暴力枚举？太慢。这篇文章介绍的方法几秒钟就算完了。

把”摆词”变成”涂色”

关键洞察：我们可以把这道题重新描述为一个涂色问题。

每个格子想象成一个空白格，可以被涂上某个字母的颜色。规则很简单：

同一个格子可以被涂色多次，但所有涂色必须用同一种颜色。

每次”把一个词以某个方向放在某个位置”就是一个涂色方案——它会把经过的每个格子涂成对应的字母。

比如”ABEL 从 (0,0) 向东放置”这个方案，会把：

  • 格子 (0,0) 涂成 A
  • 格子 (0,1) 涂成 B
  • 格子 (0,2) 涂成 E
  • 格子 (0,3) 涂成 L

如果另一个方案也经过格子 (0,3)，它必须也涂 L，否则就冲突了。

这种”可以重复但颜色必须一致”的约束，正是 Knuth 在 TAOCP 4B 里引入的”颜色项”扩展。简单来说：颜色项允许同一个格子被多次覆盖，但要求每次覆盖携带的颜色（这里就是字母）必须相同。上一篇介绍了它的基本原理；这篇文章要解决一个用颜色项时几乎所有人都会踩到的坑。

两个词共享一个格子——看起来对，其实错了

来看最小的反例。把 ABEL 和 LAND 放进 4×4 的格子，它们可以在字母 L 处相交：

A B E L
. . . A
. . . N
. . . D

ABEL 横放第 0 行，LAND 从格子 (0,3) 向下竖放。两个词都经过格子 (0,3)，字母都是 L——合法！

用颜色项写出这道题，算法搜索时大概是这样的：

  1. 选”ABEL 横放第 0 行”这个方案
  2. 把格子 (0,3) 涂成 L
  3. 净化：扫描格子 (0,3) 这一列的所有其他候选方案，删掉那些想把 (0,3) 涂成其他颜色的方案
  4. 继续选”LAND 从 (0,3) 向南放置”

问题出在第 4 步之后：LAND 向南这个方案也经过格子 (0,3)，它也需要”净化”格子 (0,3)——再次扫描这一列，再次删掉那些颜色不对的候选。

但有些候选早在第 3 步就被删过一次了！

删了两次会怎样？

想象格子 (0,3) 这一列里有一个候选方案 X，颜色是 D（不是 L）。第 3 步删掉它，同时把这列的”剩余可用候选数”减 1。第 4 步再删一次，计数再减 1。

回溯时，两次删除只被恢复一次，计数器就乱掉了。某些列明明还有可用方案，计数器却说”没了”——算法错误地以为走入了死胡同，或者走错了方向，最终给出错误的答案。

如果我们只考虑横向和纵向（不含对角线），并且要求两个词至少在一个格子上交叉，正确答案是 16 个。但用有 bug 的版本来跑，程序会给出 28 个解。多出来的 12 个全是错的，但程序不会报错，只会静默地给你假答案。

贴纸修复法

这个 bug 的根源是：第一次净化没有留下任何痕迹，第二次净化以为自己是第一个操作者。

Knuth 的修复方案非常简单：让第一次净化留下一个贴纸。

规则：净化操作扫描格子列时，遇到颜色相同的候选，不是跳过，而是贴上”已处理”标签（书里叫 COMMITTED）。删除操作遇到有”已处理”标签的节点，直接跳过，什么都不做。

效果：

  • 第一次净化（来自 ABEL 的方案）把格子 (0,3) 里某个颜色是 L 的候选贴上标签
  • 第二次净化（来自 LAND 的方案）扫描到这个候选，看到标签，跳过，不再重复操作

回溯时，逆向扫描，把标签揭掉，恢复成原来的颜色——一切如初。

这个贴纸机制有个细节很精妙：当前选中方案本身的节点不会被贴上标签。因为在净化开始之前，选中方案已经被”提取”出了列链（用于其他操作），净化扫描列时根本找不到它。这样，回溯时这个节点的颜色始终是原始值，算法才能正确判断”该调用哪个恢复操作”。

代码

加了贴纸机制的关键代码（完整实现见 dlx_colors.py）：

_COMMITTED = object()   # 贴纸：已被外层净化处理过

def _hide(row_node):
    """删除某行时，有贴纸的节点跳过"""
    j = row_node.R
    while j is not row_node:
        if j.color is not _COMMITTED:   # 有贴纸？跳过
            j.D.U = j.U
            j.U.D = j.D
            j.C.S -= 1
        j = j.R

def _purify(self, node):
    """净化：同色贴标签，异色删除"""
    col, color = node.C, node.color
    i = col.D
    while i is not col:
        if i.color == color:
            i.color = _COMMITTED    # 同色：贴标签
        else:
            self._hide(i)           # 异色：删掉
        i = i.D

def _unpurify(self, node):
    """回溯：逆序揭标签或恢复被删的行"""
    col, color = node.C, node.color
    i = col.U                       # 注意逆序
    while i is not col:
        if i.color is _COMMITTED:
            i.color = color         # 揭标签，恢复原色
        else:
            self._unhide(i)         # 恢复被删的行
        i = i.U

拼字谜题的完整建模

有了这个机制，把拼字谜题翻译成算法输入就很直接了：

概念 对应的”列” 说明
每个单词 主要列 必须恰好放一次
每个格子 颜色列 可以放多次，但颜色（字母）必须一致

每个”摆法”（单词 + 位置 + 方向）对应一行，覆盖：

  • 这个单词对应的主要列（说明”这个词已放好”）
  • 经过的每个格子的颜色列，颜色 = 对应字母
def create_word_search(rows, cols, words, allow_diagonal=True):
    W = len(words)
    num_primary = W                  # 前 W 列是主要列（单词）
    num_items   = W + rows * cols    # 后面每格一列（颜色列）

    options, labels = [], []

    for w_idx, word in enumerate(words):
        for dir_name, (dr, dc) in DIRECTIONS.items():
            for sr in range(rows):
                for sc in range(cols):
                    # 越界检查
                    er = sr + dr * (len(word) - 1)
                    ec = sc + dc * (len(word) - 1)
                    if not (0 <= er < rows and 0 <= ec < cols):
                        continue
                    # 构造这一行：主要项 + 每个字母的颜色项
                    option = [(w_idx, None)]
                    for k, ch in enumerate(word):
                        r, c = sr + dr*k, sc + dc*k
                        option.append((W + r*cols + c, ch))
                    options.append(option)
                    labels.append((w_idx, sr, sc, dir_name))

    dlx = DLX_C(num_primary, num_items, options)
    solutions = []
    for sol in dlx.solve():
        placement = [(words[labels[i][0]], *labels[i][1:]) for i in sol]
        solutions.append(placement)
    return solutions

运行一下：

words = ["ABEL", "CANTOR", "GAUSS", "EULER"]
solutions = create_word_search(6, 6, words)
print(len(solutions))   # → 244792

第一个解（恰好四词各占一行）：

CANTOR
GAUSS.
EULER.
ABEL..
......
......

更有趣的解包含斜向放置和字母交叉，都由算法自动处理，代码完全不需要为这些情况特殊处理。

词语矩形：顺带解决另一个问题

同样的框架，换个约束，就能解另一个谜题——词语矩形：横向单词填满每行，纵向单词填满每列，交叉格的字母必须相同。

C A T
D O G
E E L

横向：CAT、DOG、EEL；纵向：CDE、AOE、TGL。

建模完全类似：行和列各是一个主要项，格子是颜色项。区别在于主要项从”每个单词”变成了”每行和每列”——行和列各有一个主要项，表示这行（列）必须恰好填入一个合法单词。改几行代码就行，底层算法不需要动。

换个角度看这件事

回顾一下我们做了什么：

  1. 把”拼字谜题”描述为”每个单词必须恰好放一次，每个格子的字母必须一致”
  2. 把”字母一致”翻译成”颜色相同可以多次覆盖”
  3. 发现朴素实现有双重操作的 bug
  4. 用一个贴纸（COMMITTED 标签）修复它

整个过程最有意思的地方是：我们没有写任何”如何解谜题”的逻辑。我们只是描述了”什么是合法的谜题”，算法自己找出了所有答案。

这是这类搜索算法最吸引人的特质：把约束描述清楚，求解自动发生。出谜题、解谜题，用的是同一套框架。

你来试试？

完整代码在 dlx_colors.py 和 word_search.py，直接 clone 下来就能跑。

几个可以玩的方向：

  • 换一组词：把自己的名字或者感兴趣的词塞进去，看看有多少种藏法
  • 改变格子大小：同样的词，6×6 和 8×8 的解的数量差异有多大？
  • 加一个约束：如果要求所有词必须相交（每个词至少和另一个词共享一个格子），怎么修改建模？

欢迎在评论区留下你的发现。