📑 本页目录（点开跳转）
13 · CSP 是什么
⏱ 33 分钟 ｜ ⭐⭐ 搜索第一次从「试」变成「推」
🎯 一句话
前面所有搜索章找的都是一条「路径」，约束满足问题（CSP）找的是一组「赋值」—— 路径本身毫无意义。
代价是问题必须写成「变量 + 值域 + 约束」这个固定格式； 回报是状态从此有了结构，搜索时可以推理，而不只是试。
🔀 一、转折：从「怎么走过去」到「最后填成什么样」
前面那一串搜索章（路径搜索、A*、运动规划、博弈树），状态都是黑箱： 算法只知道「从 A 能一步到 B，代价 3」。你要的答案是动作序列，路径本身就是交付物。
八皇后不是这样。你要的是最终那张棋盘。先放哪个皇后没人关心， 甚至「放」这个动作根本不存在 —— 只是我们为了搜索而虚构出来的。
讲义把这个对照写得很干脆：
| 难的部分 | 容易的部分 | |
|---|---|---|
| CSP（n 皇后） | 知道终态长什么样 | 怎么到达那里 |
| 路径搜索（魔方） | 怎么到达那里 | 知道终态（六面同色，一眼就认得） |
这个转折立刻带来两个好处。
⭐ 第一个：赋值可交换。 「先 WA=红 再 NT=绿」和「先 NT=绿 再 WA=红」是同一个状态。 所以搜索树每一层只需要固定住一个变量、枚举它的值就够了，分支因子是 $d$（值域大小） 而不是「剩下多少变量 × d」；$n$ 个变量的话，每个解都恰好出现在深度 $n$。
⭐⭐ 第二个，也是真正重要的那个：状态不再是黑箱。 算法看得见「这个状态由哪些变量、各取了什么值构成」，也看得见「哪些变量被哪条约束拴在一起」。 既然看得见结构，就可以在还没往下试之前推出「这条路必死」——
⭐⭐ 有结构，才谈得上推理。 黑箱搜索只能「试一步，看看撞不撞墙」；CSP 可以「不用试也知道那边是墙」。 这句话是下一章约束传播的全部前提，也是本章存在的理由。
🧩 二、三件套：变量、值域、约束
一个 CSP 由三样东西定义：变量 $X_1,\dots,X_n$（要填的空）、值域 $D_i$（每个空允许填什么）、 约束 $C$（哪些填法不许出现）。解 ＝ 每个变量都赋了值，且一条约束都没违反。
主线例子：澳大利亚地图着色
给澳大利亚 7 个行政区上色，相邻的两块不能同色。
- 变量：WA（西澳）、NT（北领地）、SA（南澳）、Q（昆士兰）、NSW（新南威尔士）、V（维多利亚）、T（塔斯马尼亚）
- 值域：全都是 $\{红, 绿, 蓝\}$
- 约束：$WA \ne NT$、$WA \ne SA$、$NT \ne SA$、$NT \ne Q$、$SA \ne Q$、$SA \ne NSW$、$SA \ne V$、$Q \ne NSW$、$NSW \ne V$ —— 共 9 条
⭐ 这个例子会贯穿本章和接下来两章：回溯、前向检查、AC-3、MRV、割集条件，全部在它身上跑一遍。 它只有 $3^7 = 2187$ 种赋值，每一步都能用手算验证。
一个解：$\{WA=红,\ NT=绿,\ Q=红,\ NSW=绿,\ V=红,\ SA=蓝,\ T=绿\}$（自己拿 9 条约束核一遍）。
约束图
把变量画成节点、把每条二元约束画成一条边，就得到约束图：
⭐ 约束图不是装饰，它本身就是可利用的信息：T 和谁都不相邻（独立子问题，单独上色即可）； SA 的度是 5（全图最难满足的变量，先动它还是最后动它，搜索代价差几十倍）； 删掉 SA，剩下 6 个点就变成一条链加一个孤立点 —— 这叫割集。后两条都是第 15 章的杀手锏。
🏷 三、约束的种类
| 种类 | 牵涉几个变量 | 例子 |
|---|---|---|
| 一元 | 1 | $M \ne 0$（首位不能是零） |
| 二元 | 2 | $SA \ne WA$ |
| 高阶 | ≥ 3 | $Y = D + E$ 或 $Y = D + E - 10$ |
| 全局 | 一整组 | AllDiff（这一组变量两两互不相同） |
| 连续变量上的不等式 | 2 | $EndJob_1 + 5 \le StartJob_3$（工序间隔） |
| 软约束（偏好） | —— | 「11 点的课比 8 点的课好」 |
⭐ 高阶约束都能拆成二元的（加辅助变量即可），所以理论上只讨论二元 CSP 不损失一般性 —— 下一章的 AC-3 就建立在这个事实上。
⚠️ 但拆开不等于该拆。 AllDiff 保留成一个整体，传播能力比拆成一堆两两不等强得多：
5 个变量共享一个只剩 4 个值的池子 —— 鸽笼原理一秒判死。 可是两两不等的版本看不出来：任意两个变量之间都还有合法组合，每一条约束单独看都是满足的。
⚠️ 软约束不是 CSP，是约束优化（COP）：问的不再是「有没有解」，而是「哪个解的违反代价最小」。 真实排课系统的复杂度大半在这里 —— 硬约束（老师不能同时在两间教室）必须满足，软约束（别排周五下午）尽量满足。
👑 四、n 皇后：建模比算法重要
$n \times n$ 棋盘放 $n$ 个皇后，互不攻击。
笨模型：$n^2$ 个布尔变量（每格放不放）。$8 \times 8$ 就是 64 个变量、$2^{64}$ 个赋值。
好模型：注意到每列必然恰好一个皇后，于是：
- 变量：$Q_1, \dots, Q_n$（第 $i$ 列的皇后在第几行）
- 值域：$\{1, \dots, n\}$
- 约束：$Q_i \ne Q_j$（不同行）、$|Q_i - Q_j| \ne |i - j|$（不同对角线）
⭐⭐ 「同一列不能有两个皇后」这条约束在建模那一步就蒸发了 —— 它被编码进了「变量 = 列」这个选择里，算法根本不需要检查。 搜索空间从 $2^{64}$ 降到 $8^8 \approx 1.7 \times 10^7$。
⭐ CSP 里最大的性能提升往往来自换个建模方式，不是换个算法。 这一点和特征工程之于机器学习是同一个道理。
4 皇后的一个解是 $(Q_1,Q_2,Q_3,Q_4) = (2,4,1,3)$，拿两条约束核一遍就知道对不对。
🔢 五、密码算术：SEND + MORE = MONEY
每个字母代表一个不同的数字，首位不能是 0。求：
$$\texttt{SEND} + \texttt{MORE} = \texttt{MONEY}$$
- 变量：S E N D M O R Y
- 值域：$\{0,\dots,9\}$
- 约束：AllDiff(S,E,N,D,M,O,R,Y)；一元约束 $S \ne 0$、$M \ne 0$
麻烦在于「加法成立」是一条牵涉 8 个变量的高阶约束。 ⭐ 解法是引入隐变量（进位）$C_1, C_2, C_3, C_4 \in \{0,1\}$，把它拆成一列一条：
$$D+E = Y + 10C_1,\quad N+R+C_1 = E + 10C_2,\quad E+O+C_2 = N + 10C_3,\quad S+M+C_3 = O + 10C_4,\quad M = C_4$$
一个 8 元约束变成 5 个至多 4 元的约束 —— 每条都只牵涉三四个变量，传播起来快得多。
手推（全程不需要搜索）：
- $M = C_4 \le 1$ 而 $M \ne 0$ → M = 1
- $S + 1 + C_3 = O + 10$，$S \le 9$、$C_3 \le 1$ → $O \le 0$ → O = 0
- 第三列若 $C_3 = 1$ 则 $E + C_2 = N + 10$，左边最大 10、右边最小 10，逼出 $N = 0 = O$ 冲突 → $C_3 = 0$，回代 S = 9
- 于是 $E + C_2 = N$ 且 $E \ne N$ → $C_2 = 1$，N = E + 1
- 第二列 $(E{+}1) + R + C_1 = E + 10$ → $R + C_1 = 9$；$R = 9$ 已被 S 占 → $C_1 = 1$，R = 8
- 第一列 $D + E = Y + 10$，剩下只有 $\{2,3,4,5,6,7\}$ 可用。取 $E = 5 \Rightarrow N = 6$，$D = Y + 5$ → D = 7, Y = 2
$$9567 + 1085 = 10652 \quad\checkmark$$
⚠️ 第 6 步之前一次分支都没有 —— 前五步全是约束逼出来的唯一可能。 这正是下一章的主题：推理能把搜索空间压到几乎不用搜。
🏭 六、这东西今天在哪儿跑着
⭐ CSP 不是历史遗迹，它是排程类软件的默认底座：
| 场景 | 变量 | 值 | 典型约束 |
|---|---|---|---|
| 排课 / 排考 | 每门课 | （时段, 教室） | 同一老师/教室不冲突；考试间隔 ≥ 1 天 |
| 护士排班 | 每人每天 | 早/中/夜/休 | 夜班后必须休；每周工时上限；技能覆盖 |
| 资源分配 | 每个任务 | 哪台机器 | 机器容量；工序先后（连续不等式约束） |
| 数独 | 81 个格 | 1–9 | 每行/列/宫一条 AllDiff |
| 寄存器分配 | 每个中间变量 | $k$ 个物理寄存器 | 同时活跃的两个变量不能占同一个 |
| 硬件配置 / 运输调度 | 每个部件 / 每车货 | 型号 / 班次 | 兼容性、容量、时间窗 |
⭐⭐ 寄存器分配值得单独看一眼：「同时活跃」的两个中间变量连一条边，$k$ 个物理寄存器就是 $k$ 种颜色 —— 这就是地图着色，一模一样。 澳大利亚那张小图不是玩具，它是编译器后端每天在解的问题的最小版本。
⚠️ 诚实一点：工业界今天很少手写回溯，而是把问题喂给 CP-SAT / MIP 求解器。 但那些求解器内部跑的正是接下来两章的东西。会写这几十行，你才知道求解器为什么会卡、该怎么改模型。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 14-回溯与约束传播.html | 本章只把问题写成了 CSP，一个也没解。下一章拿同一张澳大利亚图，把回溯、前向检查、AC-3 依次跑一遍，同一个死局被三种方法在三个不同的深度发现 |
| ../博弈论与集体决策/05-推理与分辨率.html | ⭐⭐ SAT 和 CSP 是近亲：那一章把命题压成 CNF 子句集再用分辨率推，本章把问题压成变量+值域+约束。CNF 就是「所有值域都等于 {真, 假}」的 CSP，而分辨率干的事和下一章的约束传播是同一件事。想知道「把语义问题降成约束」这个动作能走多远，去那里 |
| ../AI基础设施/07-算子融合与编译.html | 那一章讲编译器怎么把多个算子融成一个 kernel、让中间结果留在寄存器里不落显存。「留哪些、留在哪个」正是本章最后那条寄存器分配 ＝ 图着色：一边是澳大利亚地图，一边是你每天跑的 CUDA kernel |
✅ 检查点
- CSP 和前面那些路径搜索问题，要的答案有什么根本不同？「难的部分」分别难在哪？
- 「赋值可交换」带来了什么具体好处？$n$ 个变量的 CSP，解出现在搜索树的第几层？
- ⭐⭐ 状态「有结构」为什么比「可交换」更重要？它让算法多出了什么能力？
- 写出澳大利亚地图着色的变量、值域和全部约束。一共几条？搜索空间多大？
- 约束图上，SA 和 T 分别有什么特殊之处？各自能被利用来做什么？
- AllDiff 拆成一堆两两不等，会损失什么？举个具体例子。
- n 皇后为什么用「每列一个变量」而不是「每格一个布尔变量」？哪条约束被建模消灭掉了？
- SEND+MORE=MONEY 里为什么要引入进位隐变量？手推出 M、O、S 三个字母的值。
👀 答案
- 路径搜索要的是动作序列，路径本身就是交付物；CSP 要的是一组赋值，路径毫无意义。⭐ 讲义的对照：n 皇后难在「知道终态长什么样」、容易在「怎么到达」；魔方正好反过来。
- 「先 WA=红 再 NT=绿」和反过来是同一个状态，所以搜索树每层只需固定一个变量，分支因子是 $d$ 而不是「剩余变量数 × d」。⭐ 每个解都恰好在深度 $n$。
- ⭐⭐ 状态不再是黑箱：算法看得见「哪些变量、取了什么值、被哪条约束拴着」，于是能在还没往下试之前推出「这条路必死」。黑箱搜索只能「试一步看撞不撞墙」，有结构才谈得上推理 —— 这是第 14 章约束传播的全部前提。
- WA NT SA Q NSW V T（7 个）；值域全是 $\{红,绿,蓝\}$；约束 $WA{\ne}NT$、$WA{\ne}SA$、$NT{\ne}SA$、$NT{\ne}Q$、$SA{\ne}Q$、$SA{\ne}NSW$、$SA{\ne}V$、$Q{\ne}NSW$、$NSW{\ne}V$ —— 9 条。搜索空间 $3^7 = \mathbf{2187}$。
- SA 的度是 5（全图最高）→ 最难满足的变量，第 15 章的 MRV / 度启发冲它去；T 的度是 0 → 独立子问题。⭐ 另外删掉 SA 后剩下 6 个点是一条链加一个孤立点（树结构）—— 第 15 章割集条件的入口。
- 损失传播强度。⭐ 5 个变量共享一个只剩 4 个值的池子，AllDiff 用鸽笼原理一秒判死；两两不等的版本每一条单独看都是满足的，看不出矛盾。
- 因为「每列必然恰好一个皇后」，变量可以定成「第 $i$ 列的皇后在第几行」。⭐⭐ 「同列不能有两个皇后」这条约束在建模那一步就蒸发了。空间从 $2^{64}$ 降到 $8^8 \approx 1.7\times 10^7$。最大的性能提升常来自换建模，不是换算法。
- 因为「加法成立」原本是一条牵涉 8 个变量的高阶约束，加 4 个进位隐变量后拆成 5 条至多 4 元的列约束。推导：$M = C_4 \le 1$ 且 $M \ne 0$ → M = 1；$S+1+C_3 = O+10$ 逼出 O = 0；排掉 $C_3 = 1$ 得 S = 9。最终 $9567 + 1085 = 10652$，⭐ 前五步一次分支都没有。
🛑 可以停在这里
⚡ 走神救援
⭐⭐ 根本转折：前面搜索章找的是一条路径（动作序列就是交付物），CSP 找的是一组赋值，路径毫无意义。 讲义的对照句：n 皇后难在「知道终态」、容易在「怎么到达」；魔方反过来。转折带来两个好处：⭐ ① 赋值可交换，搜索树每层只固定一个变量、分支因子是 $d$，每个解都恰好在深度 $n$；⭐⭐ ② 状态不再是黑箱 —— 算法看得见变量、值和约束，就能在还没试之前推出「这条路必死」。有结构才谈得上推理，这是第 14 章约束传播的全部前提。 三件套：变量 + 值域 + 约束，解 ＝ 全赋值且零违反。主线例子澳大利亚地图着色：7 个变量、值域 $\{红,绿,蓝\}$、9 条「相邻异色」约束，空间 $3^7 = \mathbf{2187}$。约束图本身就是信息：SA 度 5（最难，第 15 章 MRV 冲它去）、T 度 0（独立子问题）、删掉 SA 剩下的就是一棵树（割集条件）。约束分一元 / 二元 / 高阶 / 全局（AllDiff）/ 连续不等式 / 软约束；⚠️ AllDiff 拆成两两不等会损失传播强度 —— 5 个变量抢 4 个值，整体看鸽笼原理一秒判死，拆开则每条单独看都满足。n 皇后的教训是⭐⭐建模比算法重要：每列一个变量（值＝行号）后「同列不能有两个」在建模那一步就蒸发了，空间从 $2^{64}$ 降到 $8^8 \approx 1.7\times10^7$。SEND+MORE=MONEY 的教训是隐变量：4 个进位变量把一条 8 元约束拆成 5 条至多 4 元的列约束，然后 M=1 → O=0 → S=9 → N=E+1 → R=8 → 9567+1085=10652，⭐前五步一次分支都没有。现实落点：排课排考、护士排班、资源分配、数独、寄存器分配、运输调度，⭐⭐ 其中寄存器分配就是图着色（同时活跃连边，$k$ 个寄存器 ＝ $k$ 种颜色）—— 澳大利亚那张小图是编译器后端每天在解的问题的最小版本。
下一节 👉 14-回溯与约束传播.md
去那里的理由：本章只是把问题写成了 CSP，一个也没解。 下一章拿同一张澳大利亚图，让回溯、前向检查、AC-3 依次上场 —— 同一个死局，三种方法分别在深度 5、深度 4、深度 3 发现它。 那三个数字的差距，就是「推理」相对「试」的全部价值。