第7章｜回溯与搜索
Unit 09 · LeetCode #51 · 优化版
← Unit 08
51
N-QueensRow · Columns · Diagonals
递归层固定一行，
候选只剩这一行的列。
每放置一个皇后，就同时占用一列、一条 row-col 主对角线和一条 row+col 副对角线。回溯时四类共享状态必须同步撤销，否则后续兄弟分支会继承不存在的攻击关系。
LeetCode #51 题目模型逐行放置，每行一个皇后，列和两类对角线不能重复
题目要求
在 n×n 棋盘放置 n 个皇后，使任意两个皇后不在同一行、同一列或同一条对角线上，返回全部棋盘方案。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
pass
本页主实验
- 使用
n=4； - 两个解为
[1,3,0,2]与[2,0,3,1]； - 失败分支使用
[0,2]展示同步撤销。
状态契约
state = row + queens + 3 constraint sets
candidate = col in current row
next state = row + 1
column key = col
diag_down key = row - col
diag_up key = row + col
与 Unit 08 的联系
单词搜索用路径内访问状态阻止重复格子；N 皇后把冲突压缩成三个集合，让候选检查从扫描历史皇后变为常数时间查询。
Row-Driven Search
row 就是递归深度，因此每层只处理一行，不需要额外维护行集合。
Column Constraint
col in columns 表示该列已经有皇后，候选立即失败。
Diagonal Encoding
同一主对角线的 row-col 相等；同一副对角线的 row+col 相等。
Synchronized Undo
撤销时必须同时恢复 queens、列和两类对角线集合。
1. 当前行候选
2. 对角线编码
3. 失败分支撤销
4. 约束污染反例
5. 槽位＋真实轨迹
6. 迁移 #52
已恢复上次学习位置、代码槽位与运行轨迹。
n=4 棋盘逐行选择不冲突的列
棋盘、当前行与攻击线
路径与三组约束
queens：每行对应列
当前行候选列
三组占用状态
已记录完整棋盘
为什么当前状态成立
当前递归契约
搜索事件
当前 row
当前 col
row-col
row+col
完成条件row == n
下一层row + 1
结构不变量
约束不变量
已放皇后
当前可用列
已记录方案
约束集合大小
状态一致
1. 完整演示
2. 功能提示槽位
3. 关键代码补全
4. 独立完成
提示逐步减少：先理解职责，再恢复代码，最后关闭上方脚手架。关键槽位补全先选左槽位 → 再选右侧代码
待填语义槽位
待选代码标签 · 仅显示代码
实时拼接后的代码骨架0 / 7
当前认知焦点1 / 1
准备运行
代码 × 状态逐行联动current / visited / queue / 递归栈 / 棋盘
真实递归状态树：仅真正进入 backtrack(row) 的合法前缀是节点冲突 col 只在候选检查层出现
状态依赖问题
运行到关键状态时这里会出现问题；回答不会阻塞逐行运行。
独立完成｜关闭槽位提示后，从空白结构自己写独立代码不依赖上方槽位完成状态。
#51 完整提交代码
渐隐脚手架：完整演示 → 语义职责 → 关键代码 → 独立完成各模块均可独立复盘，不作为导航门禁。
#51：收集棋盘
合法叶节点把当前列序列转换成字符串棋盘，追加到 result。
#52：返回计数
合法叶节点直接 return 1；搜索空间不变，只压缩输出。
完整叶节点
return 1
return 1
无解子树
return 0
return 0
父状态
sum(children)
sum(children)
根状态
2
2
0row0 col0
1row0 col1
1row0 col2
0row0 col3
变化槽位补全同样：先语义槽位 → 再代码标签
待填语义槽位
待选代码标签 · 随机顺序
实时拼接后的迁移骨架0 / 8
当前认知焦点1 / 1
准备运行
#52 使用与 #51 完全相同的 17 个合法递归状态节点返回值发生变化
代码 × 状态逐行联动total / child_count / current / visited
状态依赖问题
关键计数状态会在这里提问；不会阻塞运行。
独立完成｜不依赖迁移槽位是否通过返回前一步不会重新锁住这里。
#52 完整提交代码
第7章 Unit 09 已完成
N 皇后的递归层固定为行，候选是当前行的列；列、主对角线和副对角线集合共同压缩攻击关系。选择和撤销必须同步更新所有共享状态。
状态row、queens、columns、diag_down、diag_up
候选当前行所有不冲突的 col
主对角线row-col 相等
副对角线row+col 相等
完成条件row==n
迁移 #52完整解返回1，父状态累加计数