exact cover · algorithm x · dlx

Dancing Links · 从 Exact Cover 到数独与 N 皇后

1 · Exact Cover：挑一组行，盖住每一列，不多不少

Exact Cover（精确覆盖）问题形式如下：给一张 0/1 矩阵,行是你能选的「可选项」，列是必须被满足的「约束」，格子里的 1 表示「这一行能满足这一列」。任务是挑出一组行，使得每一列恰好被一个 1 盖住——漏掉（某列计数 = 0）不行，重复（某列计数 ≥2）也不行，必须不偏不倚地正好 1。

下面这张就是 Knuth《Dancing Links》论文里的经典 6×7 矩阵。点任意一行把它加入 / 移出选择，底部「Σ 覆盖」会实时数出每列被盖了几次：绿色 = 恰好 1（完美）、灰色 = 0（尚未覆盖）、红色 = ≥2（重复覆盖）。目标是把所有列都点成绿色。

为什么「恰好一次」这么有用？ 因为现实里大量问题天生就是这个形状。比如数独:「每个格子要填一个数」「每行每个数出现一次」都是「恰好一次」的约束；比如用多米诺 / 拼图块铺满棋盘：每个格子要被某块盖住、且只能盖一次。只要能把约束摆成列、把选择摆成行，求解就统一变成了「在 0/1 矩阵上找 exact cover」。数独那节就把数独这样翻译过去。

「无解」也是常见情形。 切到「无解 3×3」：列 C 整列全是 0，没有任何行能覆盖它——这张矩阵不存在 exact cover，无论如何选择都无法满足。求解算法必须能识别这种死路并回溯，这正是 Algorithm X 要处理的事。

2 · Algorithm X：选列 → 试行 → 缩小 → 递归 → 回溯

在 Exact Cover 那节里这组行由我们手动构造，这一节交给算法自动完成。Knuth 的 Algorithm X 是一个直接的回溯：每一轮选定一列，从能覆盖它的候选行里尝试一个放进 solution，把这行覆盖到的列和与它冲突的行（同列也有 1）全部删除——矩阵随之缩小成一个子问题，递归下去；若某条路径走入死局，就撤销刚才的选择，换下一个候选。所有列都删光时，solution 即是一个 exact cover。

选哪一列？ 默认用 Knuth 的 S 启发式：选取当前候选行最少的那一列。直觉是「先处理最难满足、分支最少的约束」，能把搜索树剪得很小。可以切换到「最左列」对比——同样能解出，但通常要尝试更多次、回溯更多。单步往下点击，高亮列是当前选的列，绿色行在 solution 里，变淡的行 / 列表示已被删出当前子问题。

Algorithm X 的开销在哪？ 不在「选列试行」，而在 cover / uncover——每次都要遍历、删除大量行列，回溯时又要原样恢复。矩阵越大、回溯越频繁，这部分开销越显著。Dancing Links 不改动算法，只把矩阵换成一种删除和恢复都是 O(1) 的链表结构，Algorithm X 便大幅提速。

3 · Dancing Links：删除和还原都只要 O(1) 的「之舞」

Algorithm X 的开销在 cover / uncover 反复删行列、再原样恢复。Knuth 的解法落在数据结构上：把矩阵里每个 1 存成一个节点，上下左右各连一根指针，串成双向循环链表。这样从链里摘掉一个节点 x，只要两条赋值：x.right.left = x.left 和 x.left.right = x.right——左右邻居直接握手，跳过 x。

精髓在还原。注意上面两步完全没碰 x 自己的指针:x.left / x.right 依旧指着它原来的左右邻居。所以要把 x 放回去，无需任何记录、无需查找，直接 x.right.left = x; x.left.right = x 即可——邻居重新指回 x,O(1) 完成。指针在摘下与放回之间来回移动，Knuth 形容它像在跳舞，这就是 Dancing Links 的名字由来。

下面是一条双向循环链表（H 是哨兵 head，首尾相接）。点一个节点把它从链里摘掉——它会掉下来，而左右邻居之间长出一条实线旁路跳过它；同时它自己保留的两根指针变成红色虚线，依旧勾着原来的邻居（这正是还原的依据）。再点带高亮圈的那个节点把它放回去。

一条约束：还原必须按移除的相反顺序。 正如 Algorithm X 回溯时 uncover 要严格镜像 cover。因此这里只有最后被摘掉的那个节点（高亮圈）能放回——这不是限制，而是 dancing links 能 O(1) 恢复的前提。连摘两个节点会发现，只能先放回后摘的那个。

3.1 · 真实矩阵是二维的：行环 × 列环

上面演示的是一维的环。真正的 DLX 矩阵是二维的：每个 1 节点同时在所属行的横向环、和所属列的纵向环里；每列还有一个 column header 节点统领，所有 header 又串成一个横向环挂在 root 下。cover 一列时，先把这个 header 从 header 环摘掉，再沿着列往下，对该列每个节点所在的整行，把行里其他节点从各自的纵向环摘掉。uncover 则严格反过来走一遍、用同样的「邻居认回」放回去。

但这张链表不是凭空就有的——得先从 0/1 矩阵织出来。下面单步演示这个构建过程：取一张 4×3 小矩阵，先摆好每列的 column header 与哨兵 root、串成横向环；再把每个值为 1 的格子变成节点；然后逐行用 left / right 串成横向环、逐列用 up / down 串成纵向环并挂到 header。织完，每个 1 节点就同时活在一行环与一列环里——右侧代码面板对应点亮当前阶段。

下面就是二维版本的 remove / resume——和上面一维的两步是同一回事，只是套了「列方向遍历 + 行方向遍历」两层循环。resume 里依然没有任何「查找放哪」的逻辑，全靠每个节点自己保留的 up/down/left/right。

这就是 DLX 名字的含义。 cover / uncover 各自只做常数次指针赋值（与被删节点的邻居数成正比，与矩阵总规模无关），回溯时还原无额外开销。把它接到 Algorithm X 上——算法不变，速度差异显著。数独这节用一个真实应用检验它。

4 · 数独：翻译成 Exact Cover，交给 DLX 求解

本节综合前面三节：Exact Cover 的问题形式、Algorithm X 的回溯，以及 Dancing Links 的 O(1) 删除 / 还原。

数独为何是精确覆盖？把它的规则翻译成列（约束）和行（选择）即可看出。一个候选「在第 r 行第 c 列填数字 d」是矩阵的一行；它恰好同时满足四类约束，各对应一列。求一个数独解，就是在这张 0/1 矩阵上找一组行，让每一列恰好被覆盖一次——一个标准的 exact cover，交给 DLX。

合计 324 列 约束、729 行 候选（9×9 格 × 9 个数）。谜面里每个已知数字就是「这一行必须入选」，等于提前 cover 掉它那 4 列；剩下的交给 Algorithm X + dancing links 搜索。选一道谜面，点 DLX 求解，看它填满全盘，顺带数出它一共试了多少个搜索分支。下拉里三档按 DLX 搜索分支数 (nodeVisits) 从少到多排列——为什么用它当难度、而不是提示数，见下方番外。

4.1 · 番外：数独的「难度」到底怎么定义？

上面三档的名字值得辨析——因为「困难 / 地狱级」和「17 提示」其实在量两件完全不同的事。一句话：「17 提示是理论下限」是可证明的事实，而「困难 / 地狱级」是没有统一定义的俗称。

###「17 提示是理论下限」——这个有严格定义，且被证明了

它回答的是：一个保证唯一解的标准 9×9 数独，最少需要几个 given（提示）？答案就是 17。2012 年 McGuire、Tugemann、Civario 用穷举计算证明了不存在 16 提示的唯一解数独，而 17 提示的唯一解盘确实存在（已知有几千个）。关键前提是**「唯一解」——提示再少，盘面就会冒出多个解、不再是良定义的谜题。而且它是个全局下限**：只说明「提示不可能更少」，并不代表「17 提示盘都很难」。

###「难度」没有统一定义，常见三种口径

所需推理技巧的层级（人类视角，最主流）：解开它要用到的最难一步——naked / hidden single → 简单；locked candidates、pairs → 中等；X-Wing / Swordfish / XY-Wing → 困难；chains / 强行试错 → 地狱。
搜索 / 回溯量（算法视角）：brute-force 或 DLX 求解时试了多少分支、回溯多少次——也就是本页显示的 nodeVisits。本页就用它给三档排序。
提示数（最常被外行当指标，也最不可靠）：见下。

4.2 · 提示数 ≠ 难度

用这三档自己跑出来的数据对比一下就一目了然。下表数字来自本页这个「选最小列（S 启发式）」的 DLX；换一种选列策略，nodeVisits 会变，但结论不变：

谜面	提示数 clues	DLX 搜索分支 nodeVisits
入门	30	51
17 提示盘	17	64
地狱级	21	1471

注意这个反直觉的事实：地狱级的提示数(21)比那个 17 提示盘还多,DLX 却要试约 23 倍的分支；而 17 提示盘虽然提示最少，对 DLX 的负担却跟入门盘差不多(64 vs 51)。按提示数从多到少排是 ${30 \to 21 \to 17}$ ，按搜索分支从少到多排是 ${51 \to 64 \to 1471}$ ——两个排序几乎对不上。提示数和搜索难度近乎无关，这正是把难度标签绑到 nodeVisits、而不是提示数的原因。

同一套引擎，换个归约就能解别的难题。 把约束族重新设计一下：N 皇后（每行 / 每列 / 每条对角线最多一个皇后）、多米诺 / 五格骨牌铺满棋盘（每格恰好被一块盖住、每块用一次）、精确铺地图着色……都能摆成 0/1 矩阵，丢给同一个 DLX。这正是 Knuth 论文的核心主张：与其为每个谜题写专用求解器，不如把它归约成 exact cover，共用一个会跳舞的链表。N 皇后那节就把它真正归约出来，交给同一个求解器跑一遍——它还会引出一个数独没用到的机制：secondary column。

5 · N 皇后：用 secondary column 表达「至多一个」

数独的四类约束全是「恰好一次」，排成的列都是 primary。N 皇后却有两类约束，正好引出 Knuth 论文里为它专门设计的 secondary column——「至多一次」的可选列。

在 N×N 棋盘放 N 个皇后，两两不能同行、同列、同对角线。候选「在第 (r,c) 格放一个皇后」是矩阵的一行，它恰好覆盖四列：所在行、所在列、所在的两条对角线。求解就是挑 N 行，让每行 / 每列恰好覆盖一次、每条对角线至多覆盖一次。

为什么对角线不能也写成「恰好一次」？ 合法布局里 N 个皇后只占 N 条 ↗ 对角线，其余对角线本就空着——强求每条都被覆盖一次必然无解。secondary column 的处理是：header 照建、行覆盖它时照样删冲突行，但它不挂进 root 环，所以 Algorithm X 选列时永远不会去「找谁来覆盖它」，于是允许它留空；而一旦两个皇后落到同一条对角线，那一列就会被覆盖两次——这在 exact cover 里非法，自动被剪掉。这就是「至多一个」。

合计 6N−2 列(2N 个 primary + 2×(2N−1) 个 secondary)、N² 行候选（每格一行）。选一个 N，看 DLX 摆出一个合法布局；它会一次性枚举全部解并报出解的总数与试过的搜索分支数。点**下一个解 →**逐个翻看——N=8 的 92 个解都在里面。

primary 与 secondary 的唯一差别，就是「在不在 root 环上」。 同一套 cover/uncover、同一套选最小列启发式，只因 secondary 列不参与「待覆盖列」的循环，就从「恰好一次」松成了「至多一次」。数独不需要它（四类约束都得恰好满足）,N 皇后只改了这一处，就让同一个会跳舞的链表解出了完全不同的谜题。