第 115 章 精确覆盖与 Dancing Links¶
精确覆盖问的是：0/1 矩阵里选若干行，使每一列恰好被盖一次。 数独、平面密铺、N 皇后都能塞进这个模型——建模的全部工夫， 就是想清楚「什么是约束（列）、什么是决策（行）」。
Dancing Links 是它的标准实现：用十字双向链表存矩阵，删除时不清空指针，
于是撤销只要一条 pre->nxt = nxt->pre = x，\(O(1)\)。
配上「每次选 1 最少的列」这个 \(S\) 启发式，指数的底数从 \(2^n\) 降到「列上 1 的个数」。
Python 的现实：约每秒 \(5\times10^5\) 个搜索树节点，比 C++ 慢 20–40 倍。 求一个解（数独类）放心写；求方案总数上到 \(10^6\) 就该换状压 DP。
1 精确覆盖问题¶
先把定义摆清楚：
精确覆盖问题：在一个 \(n \times m\) 的 0/1 矩阵中（\(n\) 行 \(m\) 列）， 选出一些行，使得每一列上有且仅有一个 1。输出所有方案。
拿一个 \(6\times7\) 矩阵当例子。把它写清楚：
| \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) | \(c_6\) | \(c_7\) | |
|---|---|---|---|---|---|---|---|
| \(r_1\) | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| \(r_2\) | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| \(r_3\) | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| \(r_4\) | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| \(r_5\) | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| \(r_6\) | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
唯一解是 \(\{r_1, r_4, r_5\}\)：\(r_4\) 盖住 \(c_1c_4\)，\(r_1\) 盖住 \(c_3c_5c_6\)，\(r_5\) 盖住 \(c_2c_7\)，不重不漏。
两个术语的对应关系（这是建模时的思维模板）：
| 精确覆盖矩阵 | 现实含义 |
|---|---|
| 一列 | 一个必须被恰好满足一次的「约束」 |
| 一行 | 一个可以选或不选的「决策」 |
| 行 \(r\) 在列 \(c\) 上是 1 | 决策 \(r\) 能满足约束 \(c\) |
| 选出的行集 | 一个可行方案 |
建模的全部工夫就是想清楚「什么是约束、什么是决策」。 想清楚了，剩下的交给 DLX；想错了，代码再快也没用。
精确覆盖 vs 重复覆盖¶
| 问题 | 每列被覆盖的次数 | 解法 |
|---|---|---|
| 精确覆盖（exact cover） | 恰好 1 次 | DLX（本章） |
| 重复覆盖（repeat cover） | 至少 1 次，求最少行数 | DLX + IDA*（估价函数 = 剩余列数的下界） |
判断口诀：题目说「每个格子恰好被盖一次」→ 精确覆盖； 说「每个点至少被一个雷达覆盖，求最少雷达数」→ 重复覆盖。 两者的
cover操作不一样：精确覆盖要删掉「冲突的行」，重复覆盖不删。
2 暴力搜索与两个剪枝¶
先看最朴素的做法：
枚举 \(2^n\) 种选取行的情形，利用链表加速 \(\Theta(n+m)\) 时间检查是否合法。
\(n \le 100\) 时 \(2^{100}\) 显然不行。搜索的框架是：
直接暴力搜索的一般流程： 1. 如果当前矩阵没有列，则要求满足。 2. 任意选取一列，如果这一列上没有 1，则无解。 3. 否则依次遍历这一列上所有有 1 的行，其中必须有一行被选中。 钦定某一行被选中，删去所有被覆盖的列和不能再选择的行， 得到一个更小的矩阵，递归下去处理。
这个框架里藏了两个关键点：
| 关键点 | 为什么重要 |
|---|---|
| 「必须有一行被选中」 | 把「选或不选每一行」（\(2^n\)）变成「这一列由谁来盖」（分支数 = 该列 1 的个数）——指数的底数从 2 降到「列上 1 的个数」 |
| 「这一列没有 1 就无解」 | 免费的可行性剪枝 |
然后是那个决定生死的优化：
为了能够尽可能避免回溯，每次选取含有 1 的个数最少的一列。 可以看到，如果矩阵中存在没有 1 的列，那么矩阵不合法，上述优化能够直接检测到。 对于绝大部分情况，这个算法可以比较轻松地跑过 \(n, m \approx 500\) 的数据。
这叫 \(S\) 启发式（\(S[c]\) 是列 \(c\) 上 1 的个数）。它同时做了两件事：
- 最小分支优先：先处理选择最少的约束，搜索树最窄的一层放在最上面；
- 顺带完成可行性剪枝：\(S\) 最小值为 0 时立刻返回。
\(S\) 启发式不是「可选优化」，是 DLX 快的全部秘密。 去掉它，数独求解会从 10 ms 退化到几十秒甚至跑不出来。 这也是 记忆化搜索与剪枝「搜索顺序剪枝」的最强案例： 同一棵搜索树，换个枚举顺序，规模差几个数量级。
3 十字双向链表¶
能有解的矩阵一般 1 都比较稀疏，而暴力搜索花费了大量时间在遍历 0 上面。 为了避免访问无用的 0，考虑将所有 1 单独建立一个节点，构造十字链表：
每个节点同时处在横排和竖排两个循环双向链表中。 最上面一排 \(C_1\) 至 \(C_m\) 是辅助节点，用于快速寻找未被覆盖的竖排。
head节点也是用于方便遍历所有现存的列的辅助节点。
结构图（用上面那个 \(6\times7\) 矩阵，只画 \(r_1, r_4\) 两行）：
head ⇄ C1 ⇄ C2 ⇄ C3 ⇄ C4 ⇄ C5 ⇄ C6 ⇄ C7 ⇄ (回到 head)
↕ ↕ ↕ ↕ ↕ ↕
r1: [1]⇄──────[1]⇄[1] （横向也是循环的）
↕ ↕ ↕ ↕ ↕ ↕
r4: [1]⇄────────────[1]
↕ ↕ ↕ ↕ ↕ ↕
(回到 C1) ... (每列纵向也是循环的)
| 链 | 成员 | 用途 |
|---|---|---|
列头横链（含 head） |
head, \(C_1..C_m\) |
遍历「还没被覆盖的列」 |
| 每列纵链（含列头） | \(C_c\) 与该列所有 1 节点 | 遍历「这一列上有 1 的行」 |
| 每行横链（不含列头） | 该行所有 1 节点 | 遍历「这一行覆盖了哪些列」 |
三点必须记牢：
- 只存 1，不存 0——这是十字链表相对二维数组的全部价值；
- 所有链都是循环的，所以「走到
head/ 走回自己」就是遍历结束的判据，不需要NULL判断； - 列头节点自己也在纵链里，所以纵链永远非空，
S[c] == 0时纵链只有列头一个元素。
4 Dancing Links：\(O(1)\) 撤销¶
暴力搜索还有一个比较费时间的地方：每次递归前都要保存现有的状态，确保能够回溯。 DLX 在这方面有突出优势。回忆一下循环链表的删除操作：
void remove(Node *x) { x->pre->nxt = x->nxt; x->nxt->pre = x->pre; // x->pre = x->nxt = NULL; ← 注意这一行被注释掉了 }如果保留
x->pre和x->nxt的值不变，那么可以通过下面的操作将x还原到链表中：所以用一个栈，依次把被删除的节点压进去。回溯时就一直弹栈，恢复节点。 因此 DLX 是可撤销数据结构。
为什么能撤销：被删掉的节点 \(x\) 自己还记得当初站在哪两个人中间。
只要在 \(x\) 被删除期间，它的两个邻居没有被别的操作挤走，
x->pre->nxt = x; x->nxt->pre = x 就能原地插回去。
而 DLX 的搜索恰好保证了这一点：删除与恢复严格按栈序配对（后删的先恢复）， 所以任意时刻要恢复的那个节点，其邻居一定还在它记得的位置上。
⚠️ 这个技巧唯一的前提是「严格后进先出」。 如果中途对同一段链做了别的删除，
restore就会把链接错。 写 DLX 时永远按「cover 的逆序 uncover」，不要图省事乱序恢复。 完整讨论见 链表 的restore小节。
cover / uncover：以「列」为单位¶
实战里不会一个节点一个节点地删。选中行 \(r\) 之后要做的是：
选中行 r ⇒ 对 r 上每一个 1 所在的列 c，执行 cover(c)：
① 把列 c 从列头横链里摘掉（这个约束已满足）
② 对列 c 上的每一行 i（i != 列头）：
把行 i 的所有节点从各自的纵链里摘掉
（行 i 与 r 在列 c 上冲突，不能再选）
| 操作 | 语义 | 谁被摘掉 |
|---|---|---|
cover(c) |
列 \(c\) 已被满足 | 列 \(c\)（从横链）+ 与 \(c\) 相交的所有行（从各自纵链） |
uncover(c) |
撤销上一次 cover(c) |
完全逆序放回 |
uncover必须严格逆序：cover的两层循环是「纵链自上而下 → 横链自左向右」，uncover就必须是「纵链自下而上（U）→ 横链自右向左（L）」。 写成同向不会立刻报错，但链表会悄悄错乱，症状是「有时算对有时算错」—— 这是 DLX 最难调的 bug，没有第二个。
5 模板：数组模拟的 DLX¶
Python 里不要用对象 + 引用实现十字链表（每个节点一个 class 实例，
\(729\times4 \approx 3000\) 个对象，属性访问全走 __dict__，慢 3–5 倍）。
正确姿势和 链表 的 ArrayLinkedList 一致：六个平行的 list。
| 数组 | 含义 |
|---|---|
L[i] / R[i] |
节点 \(i\) 的左 / 右邻居（同一行内） |
U[i] / D[i] |
节点 \(i\) 的上 / 下邻居（同一列内） |
col[i] |
节点 \(i\) 所在的列号 |
row[i] |
节点 \(i\) 所在的行号（列头节点为 0） |
S[c] |
列 \(c\) 上 1 的个数（\(S\) 启发式用） |
编号约定：0 号是 head，\(1..m\) 是列头，\(m+1\) 起是矩阵里每个 1 的节点。
这样「判断是不是列头」只要 i <= m，省一个数组。
# [片段]
class DLX:
"""精确覆盖问题的 Dancing Links 求解器（数组模拟十字双向链表）。
列编号 1..ncol，0 号是 head 哨兵，ncol+1 起是矩阵中每个 1 对应的节点。
maxnode 要 >= 矩阵中 1 的总个数。
兼容 Python 3.9。所有指针都是 list 下标，没有对象、没有引用。
"""
def __init__(self, ncol, maxnode):
cap = ncol + 1 + maxnode # head 一个 + 列头 ncol 个 + 矩阵里的 1
self.n = ncol
self.L = [0] * cap
self.R = [0] * cap
self.U = [0] * cap
self.D = [0] * cap
self.col = [0] * cap # 节点所属列
self.row = [0] * cap # 节点所属行（列头为 0）
self.S = [0] * (ncol + 1) # 每列 1 的个数
for j in range(ncol + 1): # 0 是 head，1..ncol 是列头
self.L[j] = j - 1 # 编号连续，左邻就是 j-1
self.R[j] = j + 1
self.U[j] = j # 纵链初始只有自己（空列）
self.D[j] = j
self.col[j] = j # 列头的「所属列」就是它自己，便于统一处理
self.L[0] = ncol # 横链首尾相接，成为循环链表
self.R[ncol] = 0 # 首尾接上后就不需要任何 NULL 判断
self.cnt = ncol # 已分配的最大节点编号
self.ans = [] # 当前选中的行号栈
def add_row(self, r, cols):
"""加入行号为 r 的一行，cols 是该行为 1 的列号列表（必须非空）。"""
L, R, U, D = self.L, self.R, self.U, self.D # 绑成局部名字，循环里省属性查找
first = self.cnt + 1 # 记住这一行的第一个节点编号，最后要接环
for c in cols:
self.cnt += 1
i = self.cnt
self.col[i] = c
self.row[i] = r
self.S[c] += 1 # 该列的 1 又多了一个，S 启发式靠它
U[i] = U[c] # 插到列头 c 的「上方」= 纵链末尾
D[i] = c # 纵链是循环的，往下走回到列头
D[U[c]] = i # 原来的末尾改为指向 i
U[c] = i # 列头的上邻更新成新末尾
L[i] = i - 1 # 节点编号连续，横向先按相邻编号串起来
R[i] = i + 1
L[first] = self.cnt # 再把这一行的横链首尾接成环
R[self.cnt] = first # 于是从任一节点出发绕一圈能回到自己
def _cover(self, c):
"""列 c 已被满足：摘掉列 c，并摘掉与它冲突的所有行。"""
L, R, U, D, col, S = self.L, self.R, self.U, self.D, self.col, self.S
R[L[c]] = R[c] # ① 列 c 退出列头横链
L[R[c]] = L[c] # 只改邻居的指针，c 自己的 L/R 原样保留
i = D[c]
while i != c: # ② 纵链自上而下；回到列头 c 即遍历完一整列
j = R[i]
while j != i: # 横链自左向右；j 从 i 的右邻绕回 i 为止
D[U[j]] = D[j] # 把 j 从它所在的纵链里摘掉
U[D[j]] = U[j] # 同样只改邻居，j 的 U/D 保持不变
S[col[j]] -= 1 # j 所在列少了一个 1
j = R[j]
i = D[i]
# 注意：行 i 本身在列 c 上的那个节点没有被摘（j 从 R[i] 开始，绕回 i 就停），
# 因为整列 c 已经退出横链，不会再被访问；这也让 uncover 的对称写法成立
def _uncover(self, c):
"""撤销 _cover(c)。★ 两层循环方向必须与 _cover 完全相反。"""
L, R, U, D, col, S = self.L, self.R, self.U, self.D, self.col, self.S
i = U[c]
while i != c: # 纵链自下而上（与 cover 反向）
j = L[i]
while j != i: # 横链自右向左（与 cover 反向）
S[col[j]] += 1
U[D[j]] = j # 一行代码放回去 —— restore 的威力
D[U[j]] = j # j 自己一直记着当年的上下邻居，直接认回来
j = L[j]
i = U[i]
R[L[c]] = c # 最后把列 c 接回列头横链
L[R[c]] = c # 顺序也与 cover 相反：cover 先摘列后摘行
# 严格逆序是正确性的唯一前提：后摘的先放回，
# 保证每个节点放回时，它记着的两个邻居仍在原位
def dance(self):
"""求一个解：成功返回 True，选中的行号在 self.ans 里。"""
R, L, D, S, col, row = self.R, self.L, self.D, self.S, self.col, self.row
if R[0] == 0: # 没有列了 —— 所有约束都已满足
return True
# ---- S 启发式：选 1 最少的列 ----
c = R[0]
best = S[c]
j = R[c]
while j: # j == 0 即回到 head，遍历结束
if S[j] < best:
best = S[j]
c = j
j = R[j]
if best == 0: # 该列无解 —— 免费的可行性剪枝
return False
self._cover(c) # 钦定「列 c 这一轮必须被某一行盖住」
i = D[c]
while i != c: # 枚举「由哪一行来盖住列 c」
self.ans.append(row[i]) # 试选第 i 个节点所在的行
j = R[i]
while j != i: # 该行覆盖的其余列一并 cover
self._cover(col[j])
j = R[j]
if self.dance():
return True # 子问题成功，整条路径原样保留，直接返回
j = L[i] # ★ 逆序 uncover
while j != i: # 用 L 反向走一圈，恰好抵消上面的 R 正向
self._uncover(col[j])
j = L[j]
self.ans.pop() # 撤销这次试选，链表回到进入本层时的样子
i = D[i]
self._uncover(c) # 所有行都试过仍无解，把列 c 也放回去
return False
while j:而不是while j != 0:——head的编号是 0， 所以「遍历列头横链」的终止条件天然是j为假值。这是编号约定带来的一点便利。
递归深度 = 解中行的个数。数独是 81，密铺是格子数 / 方块面积， 都很小，所以 DLX 是全书里少数可以放心用递归的算法（对比 强连通分量 的 Tarjan 必须改迭代）。
求「全部解」的变体¶
原始定义是「输出所有方案」。把 dance 改成计数即可：
# [片段]
def count_all(self):
"""统计精确覆盖的方案总数。与 dance 的唯一区别：找到解不返回，继续枚举。"""
R, L, D, S, col = self.R, self.L, self.D, self.S, self.col
if R[0] == 0:
return 1 # ← dance 里这里是 return True
# 一条完整的选法算一个方案
c = R[0]
best = S[c]
j = R[c]
while j:
if S[j] < best:
best = S[j]; c = j
j = R[j]
if best == 0:
return 0
self._cover(c)
tot = 0
i = D[c]
while i != c:
j = R[i]
while j != i:
self._cover(col[j]); j = R[j]
tot += self.count_all() # ← 累加而不是提前返回
j = L[i]
while j != i:
self._uncover(col[j]); j = L[j]
i = D[i]
self._uncover(c)
return tot
6 经典建模¶
建模一：数独¶
完整的建模方案：
注意到上面的每一条规则都对应着 \(9 \times 9 = 81\) 个要求。 例如第二行中出现 3、第三行第四列上要有数字。总共 324 个要求，对应矩阵中 324 列。 对于每一种填数字的情况，即在第 \(x\) 行、第 \(y\) 列上填数字 \(c\)，至多 \(9^3 = 729\) 种。 注意有一些格子已经提前给出。每一种情况会满足一些要求，根据这一点来填充矩阵。
324 列 = 4 类约束 × 81：
| 列区间 | 约束 | 编号公式（列号从 1 开始） |
|---|---|---|
| \(1..81\) | 第 \(x\) 行第 \(y\) 列必须有数字 | \(9x + y + 1\) |
| \(82..162\) | 第 \(x\) 行必须出现数字 \(v\) | \(81 + 9x + v + 1\) |
| \(163..243\) | 第 \(y\) 列必须出现数字 \(v\) | \(162 + 9y + v + 1\) |
| \(244..324\) | 第 \(g\) 个 3×3 宫必须出现数字 \(v\) | \(243 + 9g + v + 1\) |
729 行 = 每个「在 \((x,y)\) 填 \(v\)」的决策，每行恰好 4 个 1（对应上面 4 类约束各一个）。 已经给出的格子只保留那一个 \(v\) 对应的行——这就是「题面给的数字」在模型里的表达方式， 比额外加约束简洁得多。
# [片段]
def solve_sudoku(grid):
"""DLX 解 9x9 数独。grid 是 9 行列表，0 表示空格；就地填好并返回，无解返回 None。
324 列 = 4 类约束 x 81；至多 729 行，每行 4 个 1。
实测：包括「世界最难数独」在内，单个数独 < 10 ms。
"""
dlx = DLX(324, 729 * 4) # 至多 729 行、每行 4 个 1
rows = {} # 行号 -> (x, y, v)
for x in range(9):
for y in range(9):
g = (x // 3) * 3 + y // 3 # 所在宫编号 0..8
for v in range(9): # v = 0..8 代表数字 1..9
if grid[x][y] and grid[x][y] - 1 != v:
continue # ★ 已给出的格子只生成一行
# 于是「题面给的数字」不必再写成额外约束
rid = (x * 9 + y) * 9 + v + 1 # 把 (x,y,v) 压成唯一行号，从 1 开始
rows[rid] = (x, y, v) # 反查表，最后要靠它把解翻译回棋盘
dlx.add_row(rid, [
x * 9 + y + 1, # 约束 1：(x,y) 要有数字
81 + x * 9 + v + 1, # 约束 2：第 x 行出现 v
162 + y * 9 + v + 1, # 约束 3：第 y 列出现 v
243 + g * 9 + v + 1, # 约束 4：第 g 宫出现 v
])
if not dlx.dance():
return None
for rid in dlx.ans:
x, y, v = rows[rid]
grid[x][y] = v + 1
return grid
自测（Inkala 的「世界最难数独」）：
| 输入（0 为空） | 输出 | 耗时 |
|---|---|---|
800000000 003600000 070090200 050007000 000045700 000100030 001000068 008500010 090000400 |
812753649 943682175 675491283 154237896 369845721 287169534 521974368 438526917 796318452 |
8 ms |
8 毫秒。\(S\) 启发式让搜索树只有几千个节点， 所以 Python 的常数劣势在这个规模上完全不构成问题。 不要因为「Python 慢」就放弃 DLX 解数独——数独恰好是它最舒服的场景。
建模二：平面密铺¶
例题：用 13 种俄罗斯方块密铺 \(n \times m\) 的方格纸，计算方案总数（\(n, m \le 15\)）。
构建模型：考虑精确覆盖问题：每一列有且仅有一个 1。 而密铺问题中：每一个格子能且只能被俄罗斯方块覆盖一次。 因此尝试构造矩阵，方格纸上每一个格子对应一列。 对于每种方块，首先可能有多种旋转的方式，其次在网格上不同的位置会占据不同的格子， 对应在矩阵中某一行的相应的列上填 1。 枚举所有方块摆放的可能性，构造矩阵跑精确匹配即可。
| 模型元素 | 密铺问题 |
|---|---|
| 列（约束） | 每个格子恰好被盖一次 → \(n \times m\) 列 |
| 行（决策） | 「某个方块、某个旋转/翻转姿态、放在某个位置」 |
| 行上的 1 | 这次摆放盖住的那些格子 |
行数估算：\(n=m=15\)、13 种方块、每种最多 8 个姿态（4 旋转 × 2 翻转）、 每个姿态约 \(15 \times 15\) 个落点 → 约 \(13 \times 8 \times 225 = 2.3\times10^4\) 行。 建表本身只是这 \(2.3\times10^4\) 行的一次性构造，问题全在搜索树的大小。
两个建模陷阱： 1. 姿态要去重。正方形块（O 形）4 个旋转全一样，若不去重会把同一个方案数出 4 遍； 2. 「方案总数」要不要区分同种方块的先后？精确覆盖天然按「行的集合」计数， 不区分顺序，所以直接用
count_all得到的就是密铺方案数——这正合题意。
实测数据（用最简单的 \(1\times2\) 骨牌代替俄罗斯方块，只为量化 Python 的搜索吞吐）：
| 棋盘 | 方案总数 | Python DLX 全枚举耗时 |
|---|---|---|
| \(4\times6\) | 281 | 0.001 s ✅ |
| \(6\times6\) | 6728 | 0.02 s ✅ |
| \(6\times8\) | 167089 | 0.56 s ✅ |
| \(8\times8\) | 12988816 | 44.6 s ❌ |
换算出的吞吐：约 \(3\times10^5\) 个解 / 秒，约 \(5\times10^5\) 个搜索树节点 / 秒。 这个数字就是本章的可行性判断基准。
建模三：N 皇后¶
还有一个问题：
问题：可以使用精确匹配解决 \(n\) 皇后问题吗？
答案是「一半可以」。\(n\) 皇后有四类约束：
| 约束 | 类型 |
|---|---|
| 每行恰好一个皇后 | 精确（必须恰好 1 次） |
| 每列恰好一个皇后 | 精确 |
| 每条主对角线至多一个 | ⚠️ 至多，不是恰好 |
| 每条副对角线至多一个 | ⚠️ 至多 |
所以 N 皇后需要 DLX 的一个扩展：可选列（secondary column）—— 这些列参与「冲突检测」（被盖过就不能再盖），但不参与「必须被盖」的终止判断。 实现上就是：把可选列不接入列头横链，只保留纵链。
这道思考题的价值在于点明 DLX 的适用边界： 约束必须是「恰好一次」。见到「至多一次」「至少一次」， 要么改成可选列，要么改用重复覆盖 + IDA*，不能直接套模板。
7 「高级搜索」的其余成员¶
DLX 只是高级搜索的一支。把整个家族放在一张表里对照：
DLX 只是高级搜索的一支。把整个家族放在一张表里对照：
| 方法 | 核心思想 | 适用信号 | 主讲章节 |
|---|---|---|---|
| 迭代加深 IDDFS | 限深 DFS，深度从 1 逐次加 1 | 答案深度小、分支因子大、BFS 会 MLE | 记忆化搜索与剪枝 |
| IDA* | IDDFS + 乐观估价 \(h\) | 同上，且能给出「还差至少几步」的下界 | 迭代加深与 IDA* |
| 双向搜索 | 从起点与终点同时扩展，中间相遇 | 起点终点都确定、状态空间对称 | 双向搜索 |
| A* | 按 \(f = g + h\) 排序的优先队列 | 求单一最优解、有好的 \(h\) | 图论进阶：k 短路与关键路径 |
| DLX | 精确覆盖 + \(S\) 启发式 + \(O(1)\) 撤销 | 「每个约束恰好满足一次」 | 本章 |
8 Python 下的可行规模¶
常见的说法是 DLX「对于绝大部分情况可以比较轻松地跑过 \(n, m \approx 500\) 的数据」—— 那是 C++ 的结论。Python 要打个 20–40 倍的折。
实测基准¶
| 场景 | 搜索树节点数（量级） | Python 耗时 | 判断 |
|---|---|---|---|
| \(9\times9\) 数独，求一个解 | \(10^3\)–\(10^4\) | < 10 ms | ✅ 随便用 |
| \(9\times9\) 数独，\(T=100\) 组 | \(10^5\)–\(10^6\) | 0.5–1 s | ✅ |
| 精确覆盖矩阵 \(n,m \le 100\)，求一个解 | 依赖数据 | 通常 < 1 s | ✅ |
| 精确覆盖矩阵 \(n,m \approx 500\)，求一个解 | 依赖数据 | 数秒–数十秒 | ⚠️ 看数据脸色 |
| 全枚举，方案数 \(\le 10^5\) | \(\approx\) 方案数 | < 1 s | ✅ |
| 全枚举，方案数 \(\approx 10^7\) | \(\approx 10^7\) | 45 s | ❌ |
| \(16\times16\) 数独（1024 列） | \(10^5\)–\(10^7\) | 秒级–分钟级 | ⚠️ |
换算公式（拿去估自己的题）：
诚实结论：
需求 Python 判断 求一个解，且 \(S\) 启发式有效（数独类） ✅ 放心写 DLX 求方案总数，且方案数 \(\le 10^5\) ✅ 求方案总数，方案数 \(\ge 10^6\) ❌ 换公式 / 换 DP 题目明说「\(n, m \le 500\)，输出所有方案」 ❌ 放弃，这是给 C++ 出的题
什么时候 DLX 不是最优解¶
DLX 是通用武器，通用武器通常不是最快的。
| 问题 | DLX | 更好的做法 |
|---|---|---|
| \(9\times9\) 数独 | 10 ms | 位运算 + 候选数剪枝，同样 10 ms 但代码短一半 |
| \(n\) 皇后计数 | 需要可选列扩展 | 位运算回溯（avail = ~(col|d1|d2)），快一个数量级 |
| \(1\times2\) 骨牌密铺计数 | \(10^7\) 个解要 45 s | 轮廓线状压 DP，\(O(nm2^m)\)，\(8\times8\) 只要 \(4\times10^5\) 次运算 |
| 俄罗斯方块密铺计数 | 指数 | 同样是轮廓线状压 DP（\(m \le 15\) 时 \(2^{15}\) 状态可行） |
关键判断：题目要「所有方案」还是「方案总数」？ - 要总数 → 优先考虑 状压 DP（状压 DP）， 因为 DP 把「等价的中间状态」合并了，而搜索必须一条条走完； - 要具体方案 → DLX 是标准答案。
BISHI79 就是这个判断的活教材，见 记忆化搜索与剪枝。
9 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI28 | 构造数独 | 简单 | 题解 |
BISHI28 构造数独（简单）¶
定义「数独」为 \(n\times n\) 的非负整数矩阵 \(B\)，使每行和、每列和都等于 \(k\)。 给定 \(n \le 10^3\)、\(k \le 10^9\)，构造任意一个；不存在则输出 \(-1\)。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 原题。
✅ 题解见
solutions/nowcoder/BISHI28/sol.py，已通过官方样例验证（special judge）。
这题为什么放在 DLX 章：它是「假数独」的完美反例。
题面里的「数独」和真数独毫无关系——真数独的约束是「每行/列/宫是 \(1..9\) 的排列」， 本题的约束只是「每行和 = 每列和 = \(k\)」。这一字之差把问题的难度从 NP 完全变成了送分题。
从精确覆盖的视角看清这一点：
| 真数独 | BISHI28 | |
|---|---|---|
| 约束类型 | 每个「行-数字」对恰好一次 | 每行/列的和等于 \(k\) |
| 约束是否「恰好覆盖一次」 | ✅ 是 → 可以建精确覆盖矩阵 | ❌ 不是，是线性等式 |
| 决策空间 | 729 行 | 元素值可取 \([0, k]\) 中任意整数，无限大 |
| 解法 | DLX / 回溯 | 直接构造 |
只要构造一个「主对角线全填 \(k\)、其余全填 0」的矩阵： 第 \(i\) 行只有 \(B_{ii}=k\)，行和 \(=k\)；第 \(j\) 列只有 \(B_{jj}=k\)，列和 \(=k\)。 对任意 \(n\ge1, k\ge1\) 都成立，所以 \(-1\) 是永远不会输出的分支（题面要求写上而已）。
import sys
n, k = map(int, sys.stdin.buffer.read().split()[:2]) # 只有两个数，取前两个 token
ks = str(k) # 提前转成字符串，n 行都要用
# 第 i 行：i 个 "0 "，一个 k，n-1-i 个 " 0"
# ★ 用字符串重复直接拼出整行，每行只有 O(n) 的 C 层操作，避免逐元素 print
rows = ["0 " * i + ks + " 0" * (n - 1 - i) for i in range(n)]
sys.stdout.write("\n".join(rows) + "\n")
四个工程要点（来自题解的踩坑记录）：
- 别照抄样例那种「每格都非零」的花式矩阵。样例给的是
1 3 / 3 1， 容易把人引向「怎么把 \(k\) 均摊到每一行」。对角线最省事也最不会错； - 输出量是瓶颈，不是算法。\(n=10^3\) 时有 \(10^6\) 个元素、约 \(2\times10^6\) 个字符。
逐元素
print必然 TLE；这里用"0 " * i让整行拼接落到 C 层， 最后一次性sys.stdout.write("\n".join(...))； - \(k\) 可达 \(10^9\)，元素本身是大数，但只有 \(n\) 个非零元素，输出量不会爆；
- \(n = 1\) 时
n - 1 - i = 0，" 0" * 0是空串，自然退化，无需特判。
答案不唯一 → 本地必须用 special judge 校验（真的去算行和列和）， 不能拿标准答案逐字比对：校验器放在各题目录里，文件名
spj.py。
想练手 DLX 的话¶
几道练手题：
| 想练 | 推荐题 |
|---|---|
| 精确覆盖模板 | P4929【模板】舞蹈链（DLX） |
| DLX 解数独 | P1074 靶形数独、POJ 3076 Sudoku（\(16\times16\)） |
| 重复覆盖 + IDA* | P4205 / UVa 11214 Guarding the Chessboard |
| IDA* | P2324 骑士精神、P1763 埃及分数 |
| 双向搜索 | P4799 世界冰球锦标赛（\(2^{40}\) 折半） |
10 本章速查¶
| 要点 | 结论 |
|---|---|
| 精确覆盖问题 | 0/1 矩阵中选若干行，使每列恰好一个 1 |
| 列 = ? | 约束（必须恰好满足一次） |
| 行 = ? | 决策（可选或不选） |
| 建模的全部工夫 | 想清楚「什么是约束、什么是决策」 |
| 搜索框架 | 选一列 → 枚举「由哪一行盖它」→ 删列删行 → 递归 |
| 指数底数 | 从 \(2^n\) 降到「列上 1 的个数」 |
| \(S\) 启发式 | 每次选 1 最少的列，DLX 快的全部秘密 |
| 免费剪枝 | \(S\) 最小值为 0 → 立刻无解 |
| 十字链表 | 每个 1 是一个节点，同时属于横、纵两条循环双向链表 |
| 只存 1 不存 0 | 十字链表相对二维数组的全部价值 |
| 可撤销的原理 | 删除时不清空 pre/nxt，撤销只需 pre->nxt = nxt->pre = x |
| 撤销的前提 | 严格后进先出，必须按 cover 的逆序 uncover |
uncover 的方向 |
纵链用 U、横链用 L，与 cover 完全相反 |
| Python 实现 | 六个平行 list（L/R/U/D/col/row），不要用对象 |
| 编号约定 | 0 = head，\(1..m\) = 列头，\(m+1\) 起 = 矩阵中的 1 |
| DLX 的递归深度 | = 解中行的个数（数独 81），可以放心递归 |
| 数独建模 | 324 列（4 类 × 81）× 729 行（每行 4 个 1） |
| 已给出的格子 | 只生成那一个数字对应的行 |
| 密铺建模 | 一列 = 一个格子；一行 = 一次「方块 + 姿态 + 落点」 |
| 密铺陷阱 | 对称的方块姿态要去重，否则方案数翻倍 |
| N 皇后 | 对角线是「至多一次」→ 需要可选列扩展 |
| 重复覆盖 | 每列至少一次，求最少行数 → DLX + IDA* |
| 要「方案总数」 | 优先 状压 DP，别用 DLX |
| 要「具体方案」 | DLX 是标准答案 |
| Python 吞吐 | 约 \(5\times10^5\) 个搜索树节点 / 秒 |
| 估时公式 | 耗时(秒) \(\approx\) 节点数 \(/\ 5\times10^5\) |
| 数据规模 → Python 现实性 |
|---|
| \(9\times9\) 数独求一个解 |
| \(9\times9\) 数独 \(T=100\) 组 |
| 精确覆盖 \(n,m\le100\) 求一个解 |
| 精确覆盖 \(n,m\approx500\)（C++ 轻松过） |
| 全枚举，方案数 \(\le 10^5\) |
| 全枚举，方案数 \(\ge 10^6\) |
| \(8\times8\) 骨牌密铺全枚举（\(1.3\times10^7\) 解） |
IDA* 与双向搜索的速查条目在 迭代加深与 IDA* 与 双向搜索 章末。