N 皇后
N 皇后要在 n × n 棋盘的每行放一枚皇后，使任意两枚不同列，也不同对角线。求解器按列从左到右尝试，冲突立即拒绝，一行无合法位置则撤销前面的选择。
每枚皇后登记三项：列、row - col、row + col。新位置三项都未占用才可放置；撤销时也要删掉三项，不能留下不存在皇后的约束。
N 皇后回溯如何工作
递归按行处理，放一枚后才调用 search(row + 1)，所以不必另查行冲突。
- 同列使用相同
col。 \对角线使用相同row - col。/对角线使用相同row + col。
用三个集合检查，按常见哈希模型每次期望 O(1)。冲突候选不修改棋盘；合法候选先加入 queens，再登记三个键并递归。子调用成功就保留结果并向外返回；失败则弹出皇后、删除三个键，再试下一列。
不变量是：失败子调用退出后，调用者必须看到选择前的完整状态。回溯是精确恢复，不只是把游标向后移动。
数独、排程、资源分配和约束求解也可采用“选择、占用、递归、失败后释放”的结构。本课只找第一个解，不枚举全部，不按对称性剪枝，也不用位掩码。
逐步演示
默认 n = 4，列顺序 0, 1, 2, 3。
search(0)尝试(0, 0)，三集合为空，放置并进入第 1 行。- 第 1 行拒绝
(1, 0)，因列占用；拒绝(1, 1)，因row - col = 0。(1, 2)合法，列向量前缀为[0, 2]。 - 第 2 行无位置：列 0 已占；列 1 与
(1, 2)同/对角；列 2 已占；列 3 与(1, 2)同\对角。返回 false。 - 移除
(1, 2)并释放三个键。第 1 行继续列 3，放(1, 3)。 - 第 2 行放
(2, 1)，但第 3 行四列均冲突。撤销(2, 1)；第 2 行后续也无选择，返回后再撤销(1, 3)。 - 第 1 行耗尽，撤销
(0, 0)。在根尝试下一列前，棋盘与三个集合都重新为空。 - 根放
(0, 1)；第 1 行拒绝 0、1、2 后放(1, 3)；第 2 行放(2, 0)；第 3 行拒绝 0、1 后放(3, 2)。 - 到 row = 4 的基础状态，返回列向量
[1, 3, 0, 2]，位置索引表示行，值表示列。
该过程检查 26 个候选格，临时放置 8 次，回溯 4 次。18 次即时冲突拒绝，使 114 个原始后缀行分配无需生成。无约束的四行分配有 4^4 = 256 个完整棋盘，只要求列不重复则有 4! = 24 个。单位不同：26 是候选访问数，256、24 是完整分配数，不能直接当成同一种工作量比较。
画布红线指出阻挡当前候选的皇后。X 表示即时冲突，从未放皇后；回溯环表示该位置曾合法放置，但其子树失败。右侧展开被剪掉的未来行选择，4 x 4 = 16 表示十六个未生成的后缀分配。
时间与空间复杂度
| 项目 | 界 | 说明 |
|---|---|---|
| 列不重复的完整候选空间 | O(N!) | 原始 N^N 行选择缩为列排列，对角规则再剪枝 |
| 本课逐行扫描全部列的保守时间界 | O(N × N!) | 每个有效前缀还会检查 N 个列候选 |
| 一次安全检查 | 期望 O(1) | 三次集合查询 |
| 辅助空间 | O(N) | 皇后路径、递归栈和占用键 |
实际工作量取决于列顺序。左到右时 n = 4 先回溯四次；n = 5 可直接找到 [0, 2, 4, 1, 3]，无一次撤销。较大的棋盘不一定让“首解”轨迹更难。
只需一个有效赋值、搜索树可承受时，可用集合实现。收集所有解要在成功时复制棋盘并继续，而不是提前返回。更大的 N 可考虑位掩码和对称剪枝；更丰富的排程约束适合专用约束或 SAT 求解器。
边界情况
- n = 1 立即得到
[0]。 - n = 2、3 无解，要耗尽根选择，返回 Python
None或 JavaScriptnull，所有集合清空。 - 画布只接受
1 <= n <= 5，不是算法上限。 - 改变列顺序可改变首解和回溯次数，但不改变合法棋盘集合。
- 枚举全部解时，成功基础状态要保存副本并继续。
常见错误
- 只撤棋盘，不清集合。 过期列或对角键会拒绝本来合法的候选。
- 添加与删除的对角公式不一致。
row - col对应\，row + col对应/。名称互换不影响数学，但登记、查询、删除必须一致。 - 第一个子调用失败就返回 false。 应继续试本行下一列，循环全部耗尽才返回 false。
- 冲突拒绝也修改状态。 冲突项没有进入棋盘，无需先写再清理。
- 误读结果向量。
[1, 3, 0, 2]的下标是行，值是列，不是皇后 ID。