回溯与状态恢复：N 皇后

1 一句话问题

在 n × n 的棋盘上放 n 个皇后，要求谁也攻击不到谁，问有多少种放法。

皇后的攻击范围是：同一行、同一列、同一条对角线（两个方向都算）。

输入 4
输出 2

  这两种：
    . Q . .        . . Q .
    . . . Q        Q . . .
    Q . . .        . . . Q
    . . Q .        . Q . .

2 先用纸笔手算一遍

在纸上画个 4×4 的格子，自己试着摆一遍。摆的过程中你几乎一定会做这两件事：

1. **一行一行地放。**因为两个皇后同行就直接违规了，所以每行恰好一个，一行都不能多。
2. 放不下去了就退回上一行，把上一个皇后往右挪一格。

这两件事说出来平平无奇，但它们就是这一章的全部内容： 第 1 条决定了搜索树长什么样，第 2 条就是回溯。

从第 1 条还能立刻推出一个关键的表示法：

3 暴力：把所有排列生成出来，再一个个检查

有了上面那句话，暴力就是现成的：第 3 章刚学过全排列，直接枚举 0..n-1 的每个排列， 每生成一个完整摆法，就检查一遍对角线。

对角线怎么判？两个皇后 (r1, c1) 和 (r2, c2) 在同一条对角线上， 当且仅当 行差的绝对值 == 列差的绝对值。在纸上画两个点验证一下，立刻就信了。

点「运行 ▶」看结果

思路完全正确，n = 8 秒出。它将成为我们的标准答案。

4 实测：它有多慢

本机实测：

倍数那一列在持续变大 —— 这说明两者的差别不是「常数快几倍」， 而是增长速度本身不一样。这类差距才是竞赛里真正决定生死的东西。

5 慢在哪：暴力把功夫全花在哪儿了

想清楚这件事：假设 n = 12，第 0 行放了 0 列，第 1 行放了 1 列 —— 这两个皇后已经在同一条对角线上，这个开局彻底废了。

但全排列暴力会怎么做？它会老老实实地把剩下 10 行的所有 10! = 3 628 800 种摆法 全部生成一遍，每一种都完整检查一次，然后每一次都得出「不行」。

数字比感觉可靠。下面这份把两种做法的工作量并排数出来：

点「运行 ▶」看结果

  n        n! (暴力)     回溯节点数      省了几倍     解的个数
---   --------------   ------------   ----------   ----------
  4               24             17          1.4            2
  6              720            153          4.7            4
  8            40320           2057         19.6           92
 10          3628800          35539        102.1          724
 12        479001600         856189        559.5        14200

注意 n = 4 那一行：剪枝只省了 1.4 倍，几乎没用。 剪枝在小数据上看不出价值，在大数据上决定生死 —— 所以千万别拿 n=4 去判断一个剪枝值不值。

6 ★ 关键的一步

现在要解决一个实现问题：怎么快速判断「(r, c) 和已放的皇后冲突吗」？

每次都跟前面所有皇后比一遍当然可以，但有更利索的办法 —— 开三个标记数组， 占用了就打勾，撤销时把勾擦掉：

↘ 方向（左上到右下）：同一条上的格子，r - c 相同
↙ 方向（右上到左下）：同一条上的格子，r + c 相同

  r-c 的值             r+c 的值
   0  1  2  3          0  1  2  3
  -1  0  1  2          1  2  3  4
  -2 -1  0  1          2  3  4  5
  -3 -2 -1  0          3  4  5  6

7 回溯写法

点「运行 ▶」看结果

核心就是这个三段式，请把它背成肌肉记忆：

for (int c = 0; c < n; c++) {
    if (col[c] || d1[r-c+n-1] || d2[r+c]) continue;   // ★ 剪枝：冲突就根本不往下走

    col[c] = d1[r-c+n-1] = d2[r+c] = true;    // 进入：占用
    dfs(r + 1);                               // 递归：交给下一行
    col[c] = d1[r-c+n-1] = d2[r+c] = false;   // 撤销：还回去
}

8 把每一步打印出来

点「运行 ▶」看结果

对着输出，专门找这两种行：

• ✗ 冲突 —— 每出现一次，就意味着底下一整棵子树被跳过了。这些是省下来的白工。
• ← 撤回 —— 从递归回来，把占用还回去。数一数它出现的次数，和 ✓ 放下 是一一对应的。

n = 4 的最后统计是：真正进入的节点 17 个，被当场剪掉 44 次，而暴力要检查 24 种完整摆法。

9 单步看回溯

播放一遍，盯住这几件事：

• 淡红色的格子是被现有皇后攻击到的地方。放下一个皇后的瞬间， 一整片格子变红 —— 那就是 col、d1、d2 三个数组在起作用。
• 撤销的那一帧：皇后消失，红色也跟着退回去。如果代码里漏了撤销， 这片红色就会永远留在棋盘上 —— 想象一下那个画面，你就再也不会忘记写撤销了。
• 右边的节点数和剪掉的分支在一路涨，而最底下那个「暴力要检查的摆法数」是死的。 两者的比例就是剪枝的价值。
• 把 n 改成 6、7 各看一遍。n = 6 只有 4 个解 —— 中间那一大段全是白忙活， 但每一次白忙活都被剪枝提前掐断了。

10 ★ 对拍验证

这几个错误一定要亲手试一次，它们是回溯的经典翻车现场：

• 把撤销那一行删掉 → 答案变小（n=8 会从 92 变成 4）。这是头号错误。
• 只撤销 col[c]，忘了撤对角线 → 更隐蔽，小 n 时甚至可能碰巧对
• d1 的下标写成 r - c（忘了 + n - 1）→ 负数下标，vector 越界， 运气好当场崩，运气不好静默地读到别的内存
• d2 写成 r - c + n - 1（两条对角线复制粘贴没改）→ 答案偏大
• 出口写成 if (r == n - 1) { ans++; return; } → 最后一行没放就开始数了

11 回头看：这一章其实在讲搜索

void dfs(int 第几步) {
    if (走完了) { 记录答案; return; }

    for (每一个可能的选择) {
        if (这个选择不合法) continue;      // ← 剪枝，全部的分数都在这儿

        做出选择;                          // 进入
        dfs(下一步);                       // 递归
        撤销选择;                          // 撤销
    }
}

12 自测