第 115 章 高级搜索与精确覆盖¶
配套例题：BISHI28 构造数独、BISHI79 取数游戏 来源：S3 day2《链表 DLX 并查集》第 21–33 页（精确覆盖问题与暴力搜索）、第 37–45 页（十字链表与 Dancing Links）、第 46–50 页（\(S\) 启发式）、第 51–56 页（平面密铺建模）、第 57–67 页（数独建模）；S3 day2
Dancing Links.cpp（源码） 前置：31-链表、60-DFS深度优先搜索、62-记忆化搜索与剪枝
115.0 这一章为什么存在¶
S3 day2 的课件标题就叫《链表 DLX 并查集》——三分之一的篇幅（第 21–67 页，47 页）
在讲 Dancing Links（舞蹈链，缩写 DLX：一种用循环双向链表实现、
删除后能 \(O(1)\) 原样放回的搜索结构），还配了一份完整的 Dancing Links.cpp。
这是整套本地资料里唯一一个「专门为一个算法配源码」的数据结构。
但牛客题单里一道 DLX 题都没有。原因很清楚：
| 事实 | 后果 |
|---|---|
| DLX 只解「精确覆盖」这一类问题 | 笔试题单是「模板必刷」，覆盖面优先，冷门专题不进 |
| 精确覆盖题的输入通常是数独 / 拼图 | 读入与建模代码比算法本身长，不适合做笔试题 |
| DLX 的核心是高频指针操作 | 在 Python 里天然吃亏，出题人不会拿它卡人 |
那为什么还要学？因为 DLX 是「可撤销数据结构」这个思想的最佳范例：
31 章 的
ArrayLinkedList.restore就是从这里抄来的。 「删除节点时不清空它的pre/nxt，于是撤销只需一行」—— 这个技巧在带回溯的搜索里到处能用，不只是精确覆盖。
这一章的定位：
| 目标 | 说明 |
|---|---|
| 补上 S3 day2 的 DLX 缺口 | 精确覆盖 + 十字链表 + cover/uncover 的完整实现 |
| 把「高级搜索」的其余成员一并收齐 | 迭代加深、IDA*、双向搜索、A* —— 这些散落在 61/62 章，这里做统一的选型表 |
| 给出诚实的可行性判断 | DLX 在 CPython 里常数极大，什么规模该放弃 |
| 用题单里最接近的两题落地 | BISHI28（数独的构造版）、BISHI79（搜索被状压 DP 取代的反例） |
先给结论：
纯 Python 的 DLX 能在 10 ms 内解掉「世界最难数独」（\(9\times9\)）， 也能在 0.6 秒内枚举 \(6\times8\) 骨牌密铺的全部 167089 种方案。 但 \(8\times8\) 骨牌密铺（\(1.3\times10^7\) 种方案）要 45 秒—— Python 的 DLX 大约每秒能走 \(5\times10^5\) 个搜索树节点，比 C++ 慢 20–40 倍。
115.1 精确覆盖问题¶
S3 day2 第 22–23 页的定义：
精确覆盖问题：在一个 \(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操作不一样：精确覆盖要删掉「冲突的行」，重复覆盖不删。
115.2 暴力搜索与两个剪枝¶
S3 day2 第 24 页先给了最朴素的做法：
枚举 \(2^n\) 种选取行的情形，利用链表加速 \(\Theta(n+m)\) 时间检查是否合法。
\(n \le 100\) 时 \(2^{100}\) 显然不行。第 33 页给出搜索的框架：
直接暴力搜索的一般流程： 1. 如果当前矩阵没有列，则要求满足。 2. 任意选取一列，如果这一列上没有 1，则无解。 3. 否则依次遍历这一列上所有有 1 的行，其中必须有一行被选中。 钦定某一行被选中，删去所有被覆盖的列和不能再选择的行， 得到一个更小的矩阵，递归下去处理。
这个框架里藏了两个关键点：
| 关键点 | 为什么重要 |
|---|---|
| 「必须有一行被选中」 | 把「选或不选每一行」（\(2^n\)）变成「这一列由谁来盖」（分支数 = 该列 1 的个数）——指数的底数从 2 降到「列上 1 的个数」 |
| 「这一列没有 1 就无解」 | 免费的可行性剪枝 |
然后第 46–50 页给出那个决定生死的优化：
为了能够尽可能避免回溯，每次选取含有 1 的个数最少的一列。 可以看到，如果矩阵中存在没有 1 的列，那么矩阵不合法，上述优化能够直接检测到。 对于绝大部分情况，这个算法可以比较轻松地跑过 \(n, m \approx 500\) 的数据。
这叫 \(S\) 启发式（\(S[c]\) 是列 \(c\) 上 1 的个数）。它同时做了两件事：
- 最小分支优先：先处理选择最少的约束，搜索树最窄的一层放在最上面；
- 顺带完成可行性剪枝：\(S\) 最小值为 0 时立刻返回。
\(S\) 启发式不是「可选优化」，是 DLX 快的全部秘密。 去掉它，数独求解会从 10 ms 退化到几十秒甚至跑不出来。 这也是 62 章「搜索顺序剪枝」的最强案例： 同一棵搜索树，换个枚举顺序，规模差几个数量级。
115.3 十字双向链表¶
S3 day2 第 37–40 页：
能有解的矩阵一般 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时纵链只有列头一个元素。
115.4 Dancing Links：\(O(1)\) 撤销¶
S3 day2 第 41–45 页是整个课件最精彩的一段：
暴力搜索还有一个比较费时间的地方：每次递归前都要保存现有的状态，确保能够回溯。 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」，不要图省事乱序恢复。 完整讨论见 31-链表 的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，没有第二个。
115.5 模板：数组模拟的 DLX¶
Python 里不要用对象 + 引用实现十字链表（每个节点一个 class 实例，
\(729\times4 \approx 3000\) 个对象，属性访问全走 __dict__，慢 3–5 倍）。
正确姿势和 31 章 的 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 是本教程里少数可以放心用递归的算法（对比 112 章 的 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
115.6 两个经典建模¶
建模一：数独¶
S3 day2 第 67 页给出了完整的建模方案：
注意到上面的每一条规则都对应着 \(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 的「世界最难数独」，课件第 63 页那张图）：
| 输入（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 解数独——数独恰好是它最舒服的场景。
建模二：平面密铺¶
S3 day2 第 51–56 页：
例题：用 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\) 行。 建表本身很快，问题全在搜索树的大小。
两个建模陷阱： 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 皇后（课件留的思考题）¶
课件第 67 页问：
问题：可以使用精确匹配解决 \(n\) 皇后问题吗？
答案是「一半可以」。\(n\) 皇后有四类约束：
| 约束 | 类型 |
|---|---|
| 每行恰好一个皇后 | 精确（必须恰好 1 次） |
| 每列恰好一个皇后 | 精确 |
| 每条主对角线至多一个 | ⚠️ 至多，不是恰好 |
| 每条副对角线至多一个 | ⚠️ 至多 |
所以 N 皇后需要 DLX 的一个扩展：可选列（secondary column）—— 这些列参与「冲突检测」（被盖过就不能再盖），但不参与「必须被盖」的终止判断。 实现上就是：把可选列不接入列头横链，只保留纵链。
这道思考题的价值在于点明 DLX 的适用边界： 约束必须是「恰好一次」。见到「至多一次」「至少一次」， 要么改成可选列，要么改用重复覆盖 + IDA*，不能直接套模板。
115.7 「高级搜索」的其余成员¶
DLX 只是高级搜索的一支。把整个家族放在一张表里对照：
| 方法 | 核心思想 | 适用信号 | 主讲章节 |
|---|---|---|---|
| 迭代加深 IDDFS | 限深 DFS，深度从 1 逐次加 1 | 答案深度小、分支因子大、BFS 会 MLE | 62 章 |
| IDA* | IDDFS + 乐观估价 \(h\) | 同上，且能给出「还差至少几步」的下界 | 本章 115.7 |
| 双向搜索 | 从起点与终点同时扩展，中间相遇 | 起点终点都确定、状态空间对称 | 61 章 |
| A* | 按 \(f = g + h\) 排序的优先队列 | 求单一最优解、有好的 \(h\) | 117 章 |
| DLX | 精确覆盖 + \(S\) 启发式 + \(O(1)\) 撤销 | 「每个约束恰好满足一次」 | 本章 |
IDA*：给 IDDFS 装上估价函数¶
IDDFS 的限深循环里加一条剪枝：
\(h\) 必须是乐观估计（\(h \le\) 真实剩余步数），即所谓 admissible； 否则会剪掉最优解，答案偏大。
# [片段]
def ida_star(start, is_goal, neighbors, h, max_limit=100):
"""IDA*：迭代加深 + 乐观估价函数。返回最少步数，找不到返回 -1。
h(u) 必须满足 h(u) <= 真实剩余步数（乐观），否则结果可能非最优。
空间 O(d)，这是它相对 A* 的唯一优势（A* 要存整个优先队列）。
"""
def dfs(u, g, limit):
f = g + h(u) # g 是已走步数，h 是剩余步数的乐观下界
if f > limit:
return f # ★ 返回「超出的最小 f」，用于下一轮的 limit
if is_goal(u):
return -1 # 用 -1 表示找到
nxt = limit + 1 # 下一轮 limit 的候选：所有被剪掉的 f 的最小值
# 初值比 limit 大 1，保证任何真实的 f 都能压过它
for v in neighbors(u):
r = dfs(v, g + 1, limit)
if r == -1:
return -1 # 子树里找到了，一路向上直接返回
if r < nxt:
nxt = r # 收集被剪掉的最小 f
return nxt
limit = h(start) # 起始上限取估价值：比它小的深度不可能有解
while limit <= max_limit:
r = dfs(start, 0, limit)
if r == -1:
return limit # h 乐观 -> 第一次找到时的 limit 就是最优步数
limit = r # ★ 下一轮直接跳到最小的越界 f，不是 limit+1
return -1
limit = r而不是limit += 1是 IDA* 的精髓： 下一轮的深度上限直接取「本轮所有被剪掉的 \(f\) 值的最小值」， 一次跳到位，避免了大量无效的中间轮次。边权全为 1 时两者等价， 边权不等时前者能快好几倍。
常见估价函数：
| 问题 | \(h\) |
|---|---|
| 八数码 / 十五数码 | 各数字到目标位置的曼哈顿距离之和 |
| 魔方 | 各面错位块数 / 8（每次转动最多修好 8 块） |
| 重复覆盖（最少行数盖住所有列） | 贪心地「选一列 → 删掉能盖它的所有行覆盖的列」的轮数 |
| 木棒拼接 | 剩余木棒总长 / 目标长度 |
双向搜索的收益¶
| 单向 BFS | 双向 BFS | |
|---|---|---|
| 扩展的状态数 | \(O(b^d)\) | \(O(2 b^{d/2})\) |
| \(b=4, d=20\) | \(10^{12}\) ❌ | \(2\times10^6\) ✅ |
双向搜索是唯一能把指数「开平方」的通用手段， 但要求「反向邻居可枚举」且「起点终点都明确」。 见 61 章 的双向 BFS 小节。 数论里的同一思想叫 BSGS（114 章）， 组合里叫 meet in the middle（\(2^{40}\) 子集和拆成两半）。
115.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 重复覆盖 + IDA*，规模稍大 ❌ 常数再叠一层，基本没戏 题目明说「\(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（103 章）， 因为 DP 把「等价的中间状态」合并了，而搜索必须一条条走完； - 要具体方案 → DLX 是标准答案。
BISHI79 就是这个判断的活教材（见下）。
115.9 例题¶
BISHI28 构造数独（简单）¶
定义「数独」为 \(n\times n\) 的非负整数矩阵 \(B\)，使每行和、每列和都等于 \(k\)。 给定 \(n \le 10^3\)、\(k \le 10^9\)，构造任意一个；不存在则输出 \(-1\)。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI28 原题（牛客）。
✅ 题解见
solutions/BISHI28.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 校验（真的去算行和列和）， 不能拿标准答案逐字比对。见
solutions/_spj/。
BISHI79 取数游戏（中等）¶
\(N\times M\) 的非负整数矩阵，取出若干数，使任意两数不八连通相邻，求最大和。 \(T \le 20\) 组，\(N, M \le 6\)，\(a_{ij} \le 10^5\)。官方标签：dfs。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI79 原题（牛客）。
✅ 题解见
solutions/BISHI79.py，已通过官方样例验证。 本题在 62-记忆化搜索与剪枝 也有讲解（剪枝视角）； 这里从「搜索 vs 状压 DP」的选型视角再看一遍。
官方标签写着 dfs，但正解不是 dfs。 这正是 115.8 那条判断的实证。
朴素 DFS 逐格决策：\(2^{36} \approx 7\times10^{10}\) 个状态，加剪枝也救不回来。 问题的结构是：
八连通相邻只会发生在「同一行相邻列」和「相邻两行且列号差 \(\le 1\)」， 隔一行以上的两个格子永远不相邻。
于是「本行选了哪些列」这个 \(M\) 位 mask 完整概括了历史—— 第 \(r+1\) 行的合法性只依赖第 \(r\) 行的 mask，不依赖更早的行。 这就是无后效性，可以逐行递推。
| 做法 | 状态数 | Python 判断 |
|---|---|---|
| 逐格 DFS + 剪枝 | \(\le 2^{36}\) | ❌ |
| 逐行状压 DP | \(N \times 2^M = 6 \times 64\) | ✅ 瞬间 |
| DLX（重复覆盖） | 不适用 | ❌ 这是最优化问题，不是覆盖问题 |
两条合法性判定（一次位运算搞定，不用双重循环）：
| 约束 | 表达式 |
|---|---|
| 行内不选相邻列 | mask & (mask << 1) == 0 |
| 与上一行不冲突（正上 + 两个斜上） | (m1 \| m1 << 1 \| m1 >> 1) & m2 == 0 |
第二条是本题最漂亮的一步：把上一行的 mask 向左右各扩一位， 一次「与」运算同时覆盖了正上方和两个斜上方三种冲突， 不需要分三种情况判断。
import sys
def main() -> None:
data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
n, m = int(data[p]), int(data[p + 1]); p += 2
rows = []
for _ in range(n):
rows.append([int(v) for v in data[p:p + m]])
p += m
full = 1 << m # mask 的取值范围是 [0, 2^m)
# 行内合法的 mask（同行不选相邻列）；M=6 时只有 21 个（斐波那契 F(8)）
masks = [s for s in range(full) if not (s & (s << 1))]
# 每个 mask 向左右扩一位，用于判定与下一行是否冲突（正上 + 两斜上）
spread = [s | (s << 1) | (s >> 1) for s in range(full)]
dp = [0] * full # dp[mask]：上一行选 mask 时的最大和
alive = [0] # 上一行取值为 0（空行）作为哨兵起点
for r in range(n):
row = rows[r]
val = {}
for s in masks: # 预处理本行每个 mask 的权值和
tot = 0
x = s
while x:
low = x & -x # lowbit 逐个取出选中的列
tot += row[low.bit_length() - 1] # 位号即列号，减 1 换成 0-indexed
x ^= low # 抹掉刚处理的这一位，循环必然终止
val[s] = tot
ndp = [-1] * full # -1 表示这个 mask 本行还不可达
for s2 in masks:
best = -1
for s1 in alive:
if spread[s1] & s2:
continue # 与上一行八连通冲突
if dp[s1] > best:
best = dp[s1] # 取所有合法前驱里的最大值
if best >= 0:
ndp[s2] = best + val[s2] # 前驱可达才更新，避免把 -1 带进求和
dp = ndp
alive = [s for s in masks if dp[s] >= 0] # 只保留可达 mask，缩小下一轮内层循环
out.append(str(max(dp))) # 末行任意合法 mask 都可以收尾
sys.stdout.write("\n".join(out) + "\n")
main()
复杂度：\(O(T \cdot N \cdot 21^2) < 6\times10^4\)，瞬间出结果。
四个坑（来自题解记录）：
mask >> 1对非负整数在 Python 里是安全的（不会出现符号位问题）；mask << 1可能超出 \(M\) 位，但与mask2相与时高位天然是 0，无害；- 多组数据每组都要重置
dp，别把上一组结果带进来； - \(a_{ij} \ge 1\) 全是正数，所以「一个都不选」只在被逼无奈时才最优；
dp初值取 0（空行 mask = 0 恒合法）是正确的； alive数组是个小优化：只在「上一行可达的 mask」里找， 把内层循环从 21 降到实际可达数。
本题给出的选型口诀： 「决策只依赖上一行 / 上一层」→ 状压 DP，不要写搜索。 DLX 和 DFS 是为「必须给出具体方案」或「约束无法压成小 mask」的情形准备的。 这两题（BISHI28 构造、BISHI79 状压）合起来说明了同一件事： 精确覆盖 / 搜索是最后的手段，先找结构。
想练手 DLX 的话¶
课件第 67 页给了两道练手题（原文有乱码，这里给可用的编号）：
| 想练 | 推荐题 |
|---|---|
| 精确覆盖模板 | 洛谷 P4929【模板】舞蹈链（DLX） |
| DLX 解数独 | 洛谷 P1074 靶形数独、POJ 3076 Sudoku（\(16\times16\)） |
| 重复覆盖 + IDA* | 洛谷 P4205 / UVa 11214 Guarding the Chessboard |
| IDA* | 洛谷 P2324 骑士精神、洛谷 P1763 埃及分数 |
| 双向搜索 | 洛谷 P4799 世界冰球锦标赛（\(2^{40}\) 折半） |
115.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* |
| IDA* | IDDFS + 乐观估价 \(h\)；limit 取「被剪掉的最小 \(f\)」 |
| \(h\) 必须乐观 | \(h \le\) 真实剩余步数，否则答案偏大 |
| 双向搜索 | 唯一能把指数开平方的通用手段 |
| 要「方案总数」 | 优先 状压 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*，规模稍大 |
| 逐格 DFS 解 BISHI79（\(2^{36}\)） |