导读：Russell 与 Norvig 第 6 章把一大类问题（排课、排班、数独、调度）抽象为 CSP：变量、域、约束。解法骨架是回溯、传播加智能排序。
回溯搜索的三个增强
变量排序 MRV（剩余域最小优先）尽早失败；值排序 LCV（约束最少优先）给邻居留余地；度启发式处理平局。三者把指数搜索的常数压到工程可接受。
前向检查与弧相容（AC-3）：赋值后即时删除邻居的非法值，把失败发现在搜索树浅层。数独的人肉解法就是人肉弧相容。
结构与分解
约束图是树时线性可解：树分解把一般图切成树的胶水（图分割），分解宽度决定难度——CSP 难度不取决于变量数而取决于约束图的环。
局部搜索（最小冲突）对大规模 CSP 惊人有效：随机重启加最少冲突移动，数百万皇后的 n 皇后可解——完备性与效率的另一条路线。
与现代优化的接口
CSP 是 SAT 与整数规划的近亲：编码成 SAT 用现代求解器（CDCL）往往强于手写搜索。运筹调度用整数规划与约束规划混合。工程判断：约束硬且结构清晰用 CSP 与 SAT，目标软且连续用数值优化。
常见误区
- 变量排序固定导致在同一个坏分支反复深挖。
- 忽略值对称性，重复搜索等价解。
吃透自检
- 能实现 AC-3 并证明其复杂度
- 能对给定 CSP 选择合适的启发式组合
- 能解释树分解宽度与求解难度的关系