Dancing Links舞蹈链详解：从精确覆盖到C++数独求解实战

我第一次对“Dancing Links（舞蹈链）”上头，是在某次算法竞赛的题解里。当时那篇题解写了短短一句话：“本题用Dancing Links可秒”，然后就丢下一堆指针操作。我盯着代码看了半天，始终没搞明白那些 left、right、up、down 为什么能如此整齐地删除又恢复，更不明白它跟“跳舞”有什么关系。后来我花了两个晚上，照着 Knuth 的论文手写了一个 C++ 版数独求解器，亲手把那些节点删掉、恢复、再删掉、再恢复，才真正理解这个数据结构到底在做什么。

这篇文章就是我从“看不懂”到“能自己写出模板”整个过程的复盘。我会从精确覆盖问题开始，讲清楚舞蹈链为什么是算法X的最佳拍档；然后给出一个可以直接抄走的 C++ 实现；最后用它接一个数独求解实战。无论你是刚接触回溯算法，还是已经写过 DFS 但想知道更优雅的剪枝方式，读到最后都能拿到一套能跑通的代码。

1. 精确覆盖问题：舞蹈链要解决的到底是什么

1.1 一句话认识精确覆盖

Dancing Links 不是凭空设计的，它是为了解决“精确覆盖（Exact Cover）”问题而生的。精确覆盖问题有个非常直白的定义：给你一个由 0 和 1 组成的矩阵，要选出若干行，使得每一列恰好有一个 1。

用集合语言说更亲切：有一个全集，比如 {1,2,3,4}，还有一堆子集，比如 A={1,2}、B={3,4}、C={2,3}。现在要从这些子集里挑出一组，它们要正好覆盖整个全集，而且两两之间不能有交集。A+B 就是一个合法解，因为 {1,2} 和 {3,4} 加起来是完整的 {1,2,3,4}，而且不重叠。C+B 不行，因为 C 和 B 之间有公共的数字 3。

很多看起来八竿子打不着的问题，最后都能归结成这种精确覆盖模型。数独就是最典型的案例：每一个格子要填一个数字，每一行、每一列、每一个宫都不能出现重复数字。如果你把所有“在某格填某数”的候选动作当成行，把所有“某个格子正好有一个数”“某行正好有数字1到9”之类的约束当成列，那数独的求解就变成了从一个巨大的 0-1 矩阵里挑出若干行，让每一列恰好碰到一次 1。

1.2 算法X：暴力回溯的正确打开方式

Knuth 在提出 Dancing Links 时，先给了个逻辑框架，叫 算法X。它的思路并不复杂：

1. 如果矩阵没有列了，说明所有约束都满足，得到一个解。
2. 否则挑选一列，通常是当前 1 的个数最少的那一列。
3. 枚举这一列上为 1 的每一行，假设这一行就是最终解里的一部分。
4. 既然选了这行，那么这行涉及到的所有列都必须“被覆盖掉”。把这一行和这些列都从矩阵中删除，得到一个更小的问题。
5. 对更小的矩阵递归执行算法X。
6. 如果递归失败，就恢复刚才删除的内容，尝试下一行。

这个“删除”并不是真正把矩阵元素丢弃，而是暂时隐藏。隐藏哪些部分呢？选定了一行之后，这行上所有为 1 的列都不再需要考虑了；而行本身就是“已经选中的答案”。隐藏它们之后，递归过程面对的矩阵只包含还没被满足的约束。

算法X本身不指定用哪种数据结构实现。你可以把一个矩阵存成二维数组，每次递归时复制一份子矩阵。这种做法简单粗暴，但效率一言难尽：复制一个几百行几百列的二维数组，每次分支都可能发生，而且回溯时还要管理状态快照，写起来极其痛苦。

1.3 朴素实现为什么跑不动

我最早尝试写数独回溯时，用的是 bool 矩阵加递归。每次选择一个格子、尝试一个数字，就要检查同一行、同一列、同一个宫里是否已经有这个数字。这些检查本身倒还好，但问题在于：随着递归深入，我不得不维护越来越复杂的“哪些行已经被使用、哪些列已经被覆盖”的状态，撤销的时候又得小心翼翼地把状态还原。

更麻烦的是，精确覆盖问题常常会构造出非常大的稀疏矩阵。数独模型有 729 行、324 列，实际参与计算的 1 节点不到 3000 个。如果你用二维数组把整个矩阵存下来，324×729 的 bool 矩阵已经不小了，每次递归还要扫描行、列去判断覆盖关系，搜索效率会大打折扣。

Dancing Links 的高明之处，就是它只用链表保存非零元素。节点之间通过上下左右四个指针串成一个十字网状结构。删除一个节点，只需要把它两侧的邻居直接连起来；恢复一个节点，只需要把邻居指针再指回去。整个过程没有任何矩阵复制，也不需要对整行整列做扫描，时间复杂度都是 O(1)。这种“解开又扣回”的动作，在 Knuth 眼里就像舞者手拉手跳了一支舞，于是有了 Dancing Links 这个名字。

2. 数据结构拆解：双向链表与“跳舞”的玄机

2.1 节点、列头与根节点

要在 C++ 里实现舞蹈链，先得定义节点。比赛和项目里我习惯用数组下标代替指针，因为更容易调试，也不会出现悬空指针。

每个节点需要保存四个方向的邻居：左、右、上、下。此外，还要知道这个节点属于哪一行、哪一列；如果是列头节点，还需要保存这一列当前有多少个节点。

struct Node { int l, r, u, d; // 左、右、上、下四个方向的节点下标 int row, col; // 行号和列号 int cnt; // 仅列头节点使用：当前列剩余节点个数 };

最开始的 0 号节点叫根节点，它不参与任何实际矩阵数据，只是作为水平链表的头。每个列有一个列头节点，列头之间通过 l/r 指针串在一起，形成一条水平链表。根节点和列头节点也构成一个环。这样，只要看root.r是不是等于root，就知道所有列是否都已经被覆盖完毕。

普通 1 元素节点则会同时参与两个方向的环：同列的节点通过 u/d 串成一个垂直环，同行的节点通过 l/r 串成一个水平环。也就是说，每个节点同时挂在一根竖着的链表和一根横着的链表上，这也是“十字链表”这个名字的由来。

2.2 初始化与“挂”节点：十字链表怎么搭起来

初始化时，我先创建根节点，再创建所有列头。列头的 l/r 按顺序连成一个环：

DLX(int cols) { colCnt = cols; rowCnt = 0; nd.clear(); nd.push_back({0, 0, 0, 0, -1, -1, 0}); // 根节点 for (int i = 1; i <= cols; ++i) { nd.push_back({i - 1, i + 1, i, i, -1, i, 0}); } nd[0].l = cols; nd[0].r = 1; if (cols >= 1) { nd[cols].r = 0; // 最后一个列头的右指针要绕回根节点 } }

因为空列里没有任何元素，所以列头节点的 u/d 都先指向自己。后面 add_row 时，每插入一个新节点，就把它塞到对应列头“上方”，也就是插在列头节点和它原本的上邻居之间。

void add_row(const vector<int>& cols) { if (cols.empty()) return; int first = -1; for (int c : cols) { int id = (int)nd.size(); nd.push_back({0, 0, 0, 0, rowCnt, c, 0}); // 水平方向：把新节点接到当前行的循环链表里 if (first == -1) { first = id; nd[id].l = nd[id].r = id; } else { int last = nd[first].l; nd[last].r = id; nd[id].l = last; nd[id].r = first; nd[first].l = id; } // 垂直方向：把新节点插入到列 c 的链尾 int colHead = c; int tail = nd[colHead].u; nd[tail].d = id; nd[id].u = tail; nd[id].d = colHead; nd[colHead].u = id; nd[colHead].cnt++; } rowCnt++; }

我最初实现时犯过一个低级错误：直接在列头下方插入新节点，导致每一列的顺序变得混乱。其实插入到哪个位置都不影响正确性，因为舞蹈链只关心链表是否完整，不关心元素先后顺序。但插入到“列头上方”有个好处：cover 和 uncover 逆序遍历时，逻辑更清晰，方便调试。

2.3 cover 和 uncover：为什么恢复只需要 O(1)

舞蹈链的核心操作有两个：覆盖一列（cover）和恢复一列（uncover）。

覆盖一列分两步：

第一步，把这一列的列头从根节点所在的水平链表中摘掉。这一步相当于告诉后续递归：“这个约束已经满足了，不需要再考虑。”

第二步，遍历这一列上的每个节点，对每个节点所在的行，把该行上其他列的节点从各自的垂直链表中摘掉。这一步相当于把“已经被当前选择行影响的所有约束”全部从候选矩阵中暂时删掉。

听起来很多，但每一步都只是修改邻居的指针。比如要在垂直链表里删除节点 x，只需要：

nd[nd[x].u].d = nd[x].d; nd[nd[x].d].u = nd[x].u;

左右方向的删除同理。因为是双向循环链表，所以查找上下左右邻居都是 O(1)，删除一个节点也是 O(1)。

恢复是删除的严格逆过程：

nd[nd[x].u].d = x; nd[nd[x].d].u = x;

为什么恢复速度也快？因为链表节点被删除时，它自己的指针并没有被清空，它的原邻居也还记着它。恢复只是把邻居指针再指回来。这就是跳舞链最迷人的地方：数据没有真正消失，只是暂时退到舞池边缘，需要的时候一脚踏回来就行。

2.4 为什么用数组下标而不是指针

C++ 里实现链表，最容易想到的是new Node和指针。但我在舞蹈链里强烈推荐数组下标，原因有几点：

• 调试方便：打印nd[id]就能看到完整结构，指针打印出来只有地址。
• 避免悬空指针：节点存 vector 里，删除只是逻辑删除，不会真的释放内存，不会有 double free 风险。
• 缓存友好：vector 中的节点是连续内存，遍历时局部性好，实际跑起来比new出来的散落内存更快。
• 序列化容易：多个测试用例时，直接清空 vector 重建即可，不需要手动 delete 每个节点。

3. C++ 核心类实现：写一个能复用的 DLX 模板

3.1 核心骨架设计

我把舞蹈链封装成一个类，对外只暴露两个接口：add_row用来插入一行，search用来求解。cover和uncover是内部核心，但为了方便调试，也可以设成公有方法。

class DLX { public: struct Node { int l, r, u, d; int row, col; int cnt; }; vector<Node> nd; int root; int rowCnt; DLX(int cols) { ... } void add_row(const vector<int>& cols) { ... } void cover(int col) { ... } void uncover(int col) { ... } bool search(vector<int>& ans) { ... } };

3.2 cover 的实现细节

我见过不少初学者把 cover 写成“遍历矩阵删行”，那就没体会到链表的精髓。正确写法是彻底按链表操作来：

void cover(int col) { int L = nd[col].l; int R = nd[col].r; nd[L].r = R; nd[R].l = L; for (int i = nd[col].d; i != col; i = nd[i].d) { for (int j = nd[i].r; j != i; j = nd[j].r) { int U = nd[j].u; int D = nd[j].d; nd[U].d = D; nd[D].u = U; nd[nd[j].col].cnt--; } } }

外层循环遍历列 col 中每个节点，也就是所有包含这一列的行。内层循环遍历该行的所有节点，把它们从各自所在列的垂直链表中摘掉。这里有个关键点：内层循环从nd[i].r开始而不是从i开始，所以当前列 col 上的那个节点并不会被摘掉。这没关系，因为列头已经从水平链表移除，后续不会再被选中。

3.3 uncover 必须严格逆序

恢复时要小心顺序：外层从nd[col].u开始逆序遍历，内层从nd[i].l开始逆序遍历。这样才能精确还原 cover 之前的状态。

void uncover(int col) { for (int i = nd[col].u; i != col; i = nd[i].u) { for (int j = nd[i].l; j != i; j = nd[j].l) { int U = nd[j].u; int D = nd[j].d; nd[U].d = j; nd[D].u = j; nd[nd[j].col].cnt++; } } int L = nd[col].l; int R = nd[col].r; nd[L].r = col; nd[R].l = col; }

很多死活跑不出来的情况，问题都出在这：cover 时外层向下、内层向右，uncover 时也向下向右，结果链表里的指针越改越乱，最后陷入死循环。记住一句话：解铃还须系铃人，恢复顺序必须和删除顺序完全对称。

3.4 搜索主流程与列选择

search 函数是算法X的递归实现。终止条件是根节点的右边已经没有列头了，说明所有约束都被覆盖。

bool search(vector<int>& ans) { if (nd[root].r == root) return true; int c = nd[root].r; for (int i = nd[root].r; i != root; i = nd[i].r) { if (nd[i].cnt < nd[c].cnt) { c = i; } } cover(c); for (int i = nd[c].d; i != c; i = nd[i].d) { ans.push_back(nd[i].row); for (int j = nd[i].r; j != i; j = nd[j].r) { cover(nd[j].col); } if (search(ans)) return true; for (int j = nd[i].l; j != i; j = nd[j].l) { uncover(nd[j].col); } ans.pop_back(); } uncover(c); return false; }

选择 1 最少的列是关键。我最早时直接用根节点右边的第一列，结果数独题跑了很久都出不来。换成最小列优先之后，很多题目秒出解。原因很朴素：一列里 1 越少，说明这个约束越紧，可选的行越少，一旦分支不可行，能更早失败剪枝。

3.5 完整的可复用模板

把上面几段代码拼起来，就是一个最简 DLX 模板。实际做项目时，我会额外加一个clear()方法用来清空 vector，方便多组数据复用同一个对象：

class DLX { public: struct Node { int l, r, u, d; int row, col; int cnt; }; vector<Node> nd; int root, rowCnt; DLX(int cols) { rowCnt = 0; nd.clear(); nd.push_back({0, 0, 0, 0, -1, -1, 0}); for (int i = 1; i <= cols; ++i) { nd.push_back({i - 1, i + 1, i, i, -1, i, 0}); } nd[0].l = cols; nd[0].r = 1; if (cols >= 1) { nd[cols].r = 0; } } void add_row(const vector<int>& cols) { if (cols.empty()) return; int first = -1; for (int c : cols) { int id = (int)nd.size(); nd.push_back({0, 0, 0, 0, rowCnt, c, 0}); if (first == -1) { first = id; nd[id].l = nd[id].r = id; } else { int last = nd[first].l; nd[last].r = id; nd[id].l = last; nd[id].r = first; nd[first].l = id; } int colHead = c; int tail = nd[colHead].u; nd[tail].d = id; nd[id].u = tail; nd[id].d = colHead; nd[colHead].u = id; nd[colHead].cnt++; } rowCnt++; } void cover(int col) { int L = nd[col].l; int R = nd[col].r; nd[L].r = R; nd[R].l = L; for (int i = nd[col].d; i != col; i = nd[i].d) { for (int j = nd[i].r; j != i; j = nd[j].r) { int U = nd[j].u; int D = nd[j].d; nd[U].d = D; nd[D].u = U; nd[nd[j].col].cnt--; } } } void uncover(int col) { for (int i = nd[col].u; i != col; i = nd[i].u) { for (int j = nd[i].l; j != i; j = nd[j].l) { int U = nd[j].u; int D = nd[j].d; nd[U].d = j; nd[D].u = j; nd[nd[j].col].cnt++; } } int L = nd[col].l; int R = nd[col].r; nd[L].r = col; nd[R].l = col; } bool search(vector<int>& ans) { if (nd[root].r == root) return true; int c = nd[root].r; for (int i = nd[root].r; i != root; i = nd[i].r) { if (nd[i].cnt < nd[c].cnt) c = i; } cover(c); for (int i = nd[c].d; i != c; i = nd[i].d) { ans.push_back(nd[i].row); for (int j = nd[i].r; j != i; j = nd[j].r) { cover(nd[j].col); } if (search(ans)) return true; for (int j = nd[i].l; j != i; j = nd[j].l) { uncover(nd[j].col); } ans.pop_back(); } uncover(c); return false; } };

这个模板不依赖任何第三方库，C++11 以上都能编译。实际使用的时候，你唯一要做的就是“把业务问题翻译成 0-1 矩阵的行和列”。

4. 实战：用舞蹈链求解数独

4.1 数独的 324 个约束列

用精确覆盖模型解数独，核心是把数独规则翻译成 324 列。这 324 列分成四组：

每一行代表一个候选动作：在格子 (r, c) 填入数字 v。这个动作会同时覆盖四类约束。具体列编号计算如下：

cell 列： r * 9 + c 行数字列： 81 + r * 9 + (v - 1) 列数字列： 162 + c * 9 + (v - 1) 宫数字列： 243 + box * 9 + (v - 1) 其中 box = (r / 3) * 3 + (c / 3)

为什么会得到 729 行？因为 9 个格子 × 9 个候选数字 = 81 × 9 = 729。

4.2 把数独盘面喂给 DLX

读到一个数独盘面后，对每个格子做判断：如果盘面已经有数字，只加入这一个数字对应的那一行；如果盘面是空白的，就给 1 到 9 九个数字各加一行。

这里要注意：我们不仅要记录“选了哪一行”，还要能从行号反推回 (r, c, v)。所以用一个rowInfo数组，每次add_row之前先 push 一条信息。行号由 DLX 内部从 0 开始自动递增，必须保证rowInfo的下标和add_row调用的顺序一一对应。

#include <bits/stdc++.h> using namespace std; int main() { vector<string> board = { "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79" }; DLX dlx(324); vector<array<int, 3>> rowInfo; for (int r = 0; r < 9; ++r) { for (int c = 0; c < 9; ++c) { int box = (r / 3) * 3 + (c / 3); if (board[r][c] == '.') { for (int v = 1; v <= 9; ++v) { rowInfo.push_back({r, c, v}); dlx.add_row({ r * 9 + c, 81 + r * 9 + (v - 1), 162 + c * 9 + (v - 1), 243 + box * 9 + (v - 1) }); } } else { int v = board[r][c] - '0'; rowInfo.push_back({r, c, v}); dlx.add_row({ r * 9 + c, 81 + r * 9 + (v - 1), 162 + c * 9 + (v - 1), 243 + box * 9 + (v - 1) }); } } } vector<int> ans; if (dlx.search(ans)) { vector<string> result(9, string(9, '.')); for (int idx : ans) { auto [r, c, v] = rowInfo[idx]; result[r][c] = char('0' + v); } for (int i = 0; i < 9; ++i) { cout << result[i] << '\n'; } } else { cout << "no solution" << '\n'; } return 0; }

4.3 数独求解结果与性能

上面这个样例盘面是我随手写的，DLX 能在极短时间内完成求解。我自己的测试里，这个规模的问题通常只产生几百次递归调用，耗时在毫秒级。对比我之前用标准 DFS 写的数独求解器，DLX 在建好矩阵后查重和剪枝操作更统一，代码也更难写错。

输出解大概是这样一个 9×9 盘面：

534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179

实际跑出来的结果可能因为列选择和行顺序不同而不同，但一定是一个合法解。如果你想让 DLX 找出所有解，只需要把search中成功时的return true改成return false并计数。

4.4 从数独迁移到其他精确覆盖问题

DTX 最让我喜欢的，是它一旦写熟，业务迁移成本很低。比如 N 皇后问题也能建模成精确覆盖：

• 列：每行恰好一个皇后、每列恰好一个皇后、每条主对角线恰好一个皇后、每条副对角线恰好一个皇后。
• 行：皇后放在 (r, c) 这个位置。

再比如 Pentomino 拼图，把棋盘上的每个格子和每个方块的形状位置约束全部抽象成列，把每一块拼图的每一种摆放方式抽象成行，然后交给 DLX 搜索。只要你能把问题的约束拆成“每一列恰好一次”，舞蹈链就都适用。

5. 优化与踩坑经验

5.1 最小列优先是最有效的剪枝

我最早实现的版本是直接选根节点右边的第一列去分支，结果跑一个中等难度的数独要好几秒。改成每次找 cnt 最小的列后，绝大多数题目都变成“秒出”。这个优化不是锦上添花，而是 DLX 能不能用的分水岭。

为什么最小列优先这么有效？因为精确覆盖问题里，一列的 1 越少，意味着这个约束可选的行越少。选它做分支，递归的宽度就小得多。如果这个约束真的无解，很小的子树就能检查出来，而不用先浪费在一堆松弛的列上。

5.2 恢复顺序必须严格逆序，否则就是死循环

我把 cover/uncover 顺序写反的那次，代码并没有立刻崩溃，而是在几个分支之间反复横跳，像是卡在了一个魔幻循环里。后来我加了一句断言nd[i].cnt >= 0，才定位到恢复顺序的问题。

记住这一点：cover 里外层循环从d到c，内层循环从r到c；uncover 里外层循环必须从u到c，内层循环必须从l到c。上下和左右都要同步反向。

5.3 用 vector 管理内存时要警惕多测试用例

用数组下标模拟指针最大的优点是不用手动释放，但缺点也很明显：每一组测试数据都必须重新构造 DLX 对象。如果你在一个循环里反复用同一个对象，记得调用clear并重新执行构造函数逻辑。

另外，vector扩容时可能会把原来的节点搬走，但没关系，因为我们所有访问都是基于下标，不是基于指针。这也是我坚持用下标而不用Node*的原因之一：如果存的是指针，vector扩容后所有指针都会失效，那是灾难。

5.4 调试技巧：小矩阵 + 打印每一步

我调试 DLX 时最常用的方法，是构造一个 6 行 7 列的小矩阵手动模拟。

比如：

0010010 1001001 0110010 1001000 0100001 0001101

把这六行依次调用add_row，然后单步执行search，打印每一步选择的列、选中的行、当前根节点右侧所有列头。配合nd[i].cnt的变化，很容易看出是覆盖逻辑出了问题，还是恢复逻辑出了问题。舞蹈链的循环链表结构很有规律，一旦学会了单步调试，排错效率极高。

6. 常见问题速查与调试记录

6.1 问题与解决方案对照表

6.2 两个容易忽略的边界细节

第一个是根节点初始化。root.l要指向最后一个列头，最后一个列头.r要指向 root。漏掉任意一环，遍历根节点右侧链表时会直接死循环。

第二个是空列。如果在 search 开始后，根节点右侧还有列，但这一列的 cnt 已经变成 0，说明这个分支下没有行能满足这个约束，应该立刻返回 false。最小列优先会自然选择这种空列，然后进入 for 循环时一次也进不去，最终 uncover 后返回 false。不需要额外判断，但理解这个逻辑对调试很有帮助。

还有一个我踩过的坑：数独模型里，已经给出数字的格子只加入一行，空格子加入九行，这样才不会让某个格子列被多个数字覆盖。如果你把所有格子都加入九行，DLX 可能会解出一个“同一个格子填了两个不同数字”的结果，因为格子约束列被覆盖了两次，而 DLX 严格保证每一列恰好一次，所以这种模型下要么搜不出解，要么解出来的盘面不符合数独规则。

个人经验是，遇到“解不出来”的问题，先别怀疑模板，先检查建模。DLX 模板本身非常机械，真正容易出错的是“行代表什么、列代表什么”的翻译过程。仔细把这层关系理清楚，再套模板几乎不会有大问题。

最后再分享一个扩展技巧：上次我写 Pentomino 拼图求解器时，直接把这里的 DLX 类原封不动拿了过去，只改了 add_row 的构建方式。列从“数独的四类约束”换成了“棋盘格子和方块形状约束”，搜索逻辑一行都不用动。这也是舞蹈链最大的魅力：你只需要把世界抽象成行和列，剩下的搜索交给链表去跳舞。