第7章｜回溯与搜索
Unit 10 · LeetCode #37 · 重构版
← Unit 09
37
Sudoku SolverCSP · MRV · Transaction
候选是否合法之外，
还要决定先填哪个变量。
经典样例使用 MRV 后，真实递归搜索树会退化成一条 52 状态单链：每一层选中的 MRV 空格都只有一个候选。失败回滚仍然是算法必须满足的事务契约，但应与主样例的真实执行分开演示。
题目模型9×9 · 行 / 列 / 宫 · MRV · 原地保留成功路径
状态与约束
board 保存当前局面；rows / cols / boxes 压缩三类已占用数字。每层扫描所有空格，用 MRV 选择候选最少的变量。
candidate(r,c) = digits - rows[r] - cols[c] - boxes[box(r,c)]
box(r,c) = (r//3)*3 + c//3
本页真实性约束
- 主轨迹严格遵循 MRV，不插入人为错误分支；
- 经典样例在确定性候选顺序下没有失败回滚；
- 回滚单独放在“控制微实验”，明确标记为非主轨迹。
已恢复上次学习位置、槽位和轨迹。
1. 行列宫候选
2. MRV 变量选择
3. 失败回滚微实验
4. 约束污染反例
5. 槽位＋真实轨迹
6. 迁移 #36
经典 9×9 数独
棋盘与当前变量
深色：给定
蓝色：搜索填入
橙框：当前格
MRV：候选最少
候选与约束
当前变量
row—
col—
box—
候选—
合法候选
当前三个作用域
MRV 候选数量对比
当前关键状态链
当前正确性说明
数独搜索状态契约
约束与搜索职责
搜索事件
当前空格—
当前候选—
剩余空格—
状态一致—
一致性不变量
搜索决策
已填数字
剩余空格
当前候选数
搜索填入数
状态是否一致
1. 完整演示
2. 功能提示槽位
3. 关键代码补全
4. 独立完成
经典样例主轨迹只展示真实 MRV 执行；失败回滚在前一环节独立演示。关键槽位补全先选左槽位 → 再选右侧代码
待填语义槽位
待选代码标签 · 仅显示代码
实时拼接后的代码骨架0 / 9
当前认知焦点
代码 × 状态逐行联动queue / visited / current / pending / 递归栈
真实 MRV 搜索树：该经典样例退化为 52 状态单链每个选中变量都是单候选
状态依赖问题
运行到关键状态时这里会出现问题；回答不阻塞轨迹。
独立完成｜关闭上方脚手架后自己写完整求解器独立完成不依赖槽位是否已答对，也不作为主导航门禁。
#37 完整提交代码
渐隐脚手架：完整演示 → 功能语义 → 关键代码 → 独立完成
迁移题：LeetCode #36 有效的数独
只验证当前已填数字是否合法。保留 row / col / box 的约束索引，删除候选生成、MRV、递归和撤销。
#37：求一个补全
候选生成 + MRV + 回溯；失败撤销，成功保留。
#36：只验证已有数字
顺序扫描；重复立即 False，不产生任何搜索树。
读取 value
跳过 "."
先检查三集合
无冲突再 add
迁移关键槽位补全同样：左语义 → 右代码
待填语义槽位
待选代码标签 · 仅显示代码
实时拼接后的迁移代码骨架
#36 顺序扫描轨迹current / visited / queue / 扫描图
扫描图：visited = 已完成三组登记的已填格不是 DFS 搜索树
状态依赖问题
#36 独立完成
Unit 10 完成
数独把回溯升级为约束满足搜索：三类集合维护值约束，MRV 决定变量顺序；失败时四类状态事务式回滚，成功时 True 短路保留最终 board。经典样例本身在 MRV 下没有真实失败分支，因此回滚通过独立微实验学习。