我第一次对“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}。现在要从这些子集里挑出一组它们要正好覆盖整个全集而且两两之间不能有交集。AB 就是一个合法解因为 {1,2} 和 {3,4} 加起来是完整的 {1,2,3,4}而且不重叠。CB 不行因为 C 和 B 之间有公共的数字 3。很多看起来八竿子打不着的问题最后都能归结成这种精确覆盖模型。数独就是最典型的案例每一个格子要填一个数字每一行、每一列、每一个宫都不能出现重复数字。如果你把所有“在某格填某数”的候选动作当成行把所有“某个格子正好有一个数”“某行正好有数字1到9”之类的约束当成列那数独的求解就变成了从一个巨大的 0-1 矩阵里挑出若干行让每一列恰好碰到一次 1。1.2 算法X暴力回溯的正确打开方式Knuth 在提出 Dancing Links 时先给了个逻辑框架叫 算法X。它的思路并不复杂如果矩阵没有列了说明所有约束都满足得到一个解。否则挑选一列通常是当前 1 的个数最少的那一列。枚举这一列上为 1 的每一行假设这一行就是最终解里的一部分。既然选了这行那么这行涉及到的所有列都必须“被覆盖掉”。把这一行和这些列都从矩阵中删除得到一个更小的问题。对更小的矩阵递归执行算法X。如果递归失败就恢复刚才删除的内容尝试下一行。这个“删除”并不是真正把矩阵元素丢弃而是暂时隐藏。隐藏哪些部分呢选定了一行之后这行上所有为 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 vectorint 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; }; vectorNode nd; int root; int rowCnt; DLX(int cols) { ... } void add_row(const vectorint cols) { ... } void cover(int col) { ... } void uncover(int col) { ... } bool search(vectorint 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(vectorint 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; }; vectorNode 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 vectorint 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(vectorint 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; } };这个模板不依赖任何第三方库C11 以上都能编译。实际使用的时候你唯一要做的就是“把业务问题翻译成 0-1 矩阵的行和列”。4. 实战用舞蹈链求解数独4.1 数独的 324 个约束列用精确覆盖模型解数独核心是把数独规则翻译成 324 列。这 324 列分成四组约束类型列编号数量含义每个格子只能填一个数字0 到 8081第 r 行第 c 列正好有一个数字每一行每个数字只能出现一次81 到 16181第 r 行必须包含数字 1 到 9 各一次每一列每个数字只能出现一次162 到 24281第 c 列必须包含数字 1 到 9 各一次每个宫每个数字只能出现一次243 到 32381第 b 个宫必须包含数字 1 到 9 各一次每一行代表一个候选动作在格子 (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() { vectorstring 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); vectorarrayint, 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) }); } } } vectorint ans; if (dlx.search(ans)) { vectorstring 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到cuncover 里外层循环必须从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 问题与解决方案对照表现象可能原因解决办法递归进入死循环cover 与 uncover 遍历方向不对称严格保证 uncover 是 cover 的逆序搜索提前返回无解列编号映射错误导致约束列重复逐个打印 rowInfo核对四类列编号同一组数据不同运行结果不一致add_row 顺序影响行选择顺序这是正常的不同解不影响正确性结果中出现重复约束一行中重复加入了同一个列编号add_row 前对 cols 去重内存占用持续增长多组数据复用同一个 DLX 对象每组数据重新构造 DLX特别难啃的数独还是很慢没有做最小列优先检查 search 中选择列的代码是否始终取 cnt 最小6.2 两个容易忽略的边界细节第一个是根节点初始化。root.l要指向最后一个列头最后一个列头.r要指向 root。漏掉任意一环遍历根节点右侧链表时会直接死循环。第二个是空列。如果在 search 开始后根节点右侧还有列但这一列的 cnt 已经变成 0说明这个分支下没有行能满足这个约束应该立刻返回 false。最小列优先会自然选择这种空列然后进入 for 循环时一次也进不去最终 uncover 后返回 false。不需要额外判断但理解这个逻辑对调试很有帮助。还有一个我踩过的坑数独模型里已经给出数字的格子只加入一行空格子加入九行这样才不会让某个格子列被多个数字覆盖。如果你把所有格子都加入九行DLX 可能会解出一个“同一个格子填了两个不同数字”的结果因为格子约束列被覆盖了两次而 DLX 严格保证每一列恰好一次所以这种模型下要么搜不出解要么解出来的盘面不符合数独规则。个人经验是遇到“解不出来”的问题先别怀疑模板先检查建模。DLX 模板本身非常机械真正容易出错的是“行代表什么、列代表什么”的翻译过程。仔细把这层关系理清楚再套模板几乎不会有大问题。最后再分享一个扩展技巧上次我写 Pentomino 拼图求解器时直接把这里的 DLX 类原封不动拿了过去只改了 add_row 的构建方式。列从“数独的四类约束”换成了“棋盘格子和方块形状约束”搜索逻辑一行都不用动。这也是舞蹈链最大的魅力你只需要把世界抽象成行和列剩下的搜索交给链表去跳舞。 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}。现在要从这些子集里挑出一组它们要正好覆盖整个全集而且两两之间不能有交集。AB 就是一个合法解因为 {1,2} 和 {3,4} 加起来是完整的 {1,2,3,4}而且不重叠。CB 不行因为 C 和 B 之间有公共的数字 3。很多看起来八竿子打不着的问题最后都能归结成这种精确覆盖模型。数独就是最典型的案例每一个格子要填一个数字每一行、每一列、每一个宫都不能出现重复数字。如果你把所有“在某格填某数”的候选动作当成行把所有“某个格子正好有一个数”“某行正好有数字1到9”之类的约束当成列那数独的求解就变成了从一个巨大的 0-1 矩阵里挑出若干行让每一列恰好碰到一次 1。1.2 算法X暴力回溯的正确打开方式Knuth 在提出 Dancing Links 时先给了个逻辑框架叫 算法X。它的思路并不复杂如果矩阵没有列了说明所有约束都满足得到一个解。否则挑选一列通常是当前 1 的个数最少的那一列。枚举这一列上为 1 的每一行假设这一行就是最终解里的一部分。既然选了这行那么这行涉及到的所有列都必须“被覆盖掉”。把这一行和这些列都从矩阵中删除得到一个更小的问题。对更小的矩阵递归执行算法X。如果递归失败就恢复刚才删除的内容尝试下一行。这个“删除”并不是真正把矩阵元素丢弃而是暂时隐藏。隐藏哪些部分呢选定了一行之后这行上所有为 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 vectorint 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; }; vectorNode nd; int root; int rowCnt; DLX(int cols) { ... } void add_row(const vectorint cols) { ... } void cover(int col) { ... } void uncover(int col) { ... } bool search(vectorint 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(vectorint 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; }; vectorNode 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 vectorint 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(vectorint 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; } };这个模板不依赖任何第三方库C11 以上都能编译。实际使用的时候你唯一要做的就是“把业务问题翻译成 0-1 矩阵的行和列”。4. 实战用舞蹈链求解数独4.1 数独的 324 个约束列用精确覆盖模型解数独核心是把数独规则翻译成 324 列。这 324 列分成四组约束类型列编号数量含义每个格子只能填一个数字0 到 8081第 r 行第 c 列正好有一个数字每一行每个数字只能出现一次81 到 16181第 r 行必须包含数字 1 到 9 各一次每一列每个数字只能出现一次162 到 24281第 c 列必须包含数字 1 到 9 各一次每个宫每个数字只能出现一次243 到 32381第 b 个宫必须包含数字 1 到 9 各一次每一行代表一个候选动作在格子 (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() { vectorstring 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); vectorarrayint, 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) }); } } } vectorint ans; if (dlx.search(ans)) { vectorstring 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到cuncover 里外层循环必须从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 问题与解决方案对照表现象可能原因解决办法递归进入死循环cover 与 uncover 遍历方向不对称严格保证 uncover 是 cover 的逆序搜索提前返回无解列编号映射错误导致约束列重复逐个打印 rowInfo核对四类列编号同一组数据不同运行结果不一致add_row 顺序影响行选择顺序这是正常的不同解不影响正确性结果中出现重复约束一行中重复加入了同一个列编号add_row 前对 cols 去重内存占用持续增长多组数据复用同一个 DLX 对象每组数据重新构造 DLX特别难啃的数独还是很慢没有做最小列优先检查 search 中选择列的代码是否始终取 cnt 最小6.2 两个容易忽略的边界细节第一个是根节点初始化。root.l要指向最后一个列头最后一个列头.r要指向 root。漏掉任意一环遍历根节点右侧链表时会直接死循环。第二个是空列。如果在 search 开始后根节点右侧还有列但这一列的 cnt 已经变成 0说明这个分支下没有行能满足这个约束应该立刻返回 false。最小列优先会自然选择这种空列然后进入 for 循环时一次也进不去最终 uncover 后返回 false。不需要额外判断但理解这个逻辑对调试很有帮助。还有一个我踩过的坑数独模型里已经给出数字的格子只加入一行空格子加入九行这样才不会让某个格子列被多个数字覆盖。如果你把所有格子都加入九行DLX 可能会解出一个“同一个格子填了两个不同数字”的结果因为格子约束列被覆盖了两次而 DLX 严格保证每一列恰好一次所以这种模型下要么搜不出解要么解出来的盘面不符合数独规则。个人经验是遇到“解不出来”的问题先别怀疑模板先检查建模。DLX 模板本身非常机械真正容易出错的是“行代表什么、列代表什么”的翻译过程。仔细把这层关系理清楚再套模板几乎不会有大问题。最后再分享一个扩展技巧上次我写 Pentomino 拼图求解器时直接把这里的 DLX 类原封不动拿了过去只改了 add_row 的构建方式。列从“数独的四类约束”换成了“棋盘格子和方块形状约束”搜索逻辑一行都不用动。这也是舞蹈链最大的魅力你只需要把世界抽象成行和列剩下的搜索交给链表去跳舞。 
