N 皇后问题的 DFS 解法：从回溯框架到位运算，最详细教学

题目重述

在 N × N 的棋盘上放置 N 个皇后，要求：任意两个皇后都不能处于同一行、同一列或同一条对角线上。返回所有合法摆法（力扣 51）或合法摆法数量（力扣 52）。

以 N = 4 为例，共有两种解：

plaintext复制

. Q . . . . Q . . . . Q Q . . . Q . . . . . . Q . . Q . . Q . .

关键观察：把「放 N 个皇后」变成「每行放一个」

暴力枚举每个格子的做法是 N² 选 N，组合数爆炸。但题目约束里藏着两个信息：

1. 一共 N 个皇后，棋盘一共 N 行——每行恰好一个皇后
2. 一旦按行放置，「不同行」的约束自动满足

于是问题坍塌成一个逐行决策的过程：第 0 行选一列，第 1 行选一列……第 N-1 行选一列，只要每步满足「列不冲突、对角线不冲突」，放完就是解。

这就是 DFS（深度优先搜索）的状态空间：一棵深度为 N 的决策树，第 i 层代表第 i 行的列选择。

回溯三问

写任何回溯题，先回答三个问题：

伪代码骨架：

plaintext复制

function backtrack(row): if row === N: 记录解; return for col in 0..N-1: if 合法(row, col): 落子(row, col) backtrack(row + 1) 撤销落子(row, col) # 回溯：把状态还给上一层

「撤销」是回溯的灵魂——不撤销，一条路径的错误选择会污染兄弟分支。

版本一：最朴素的 Set 校验

最直觉的写法是用三个集合记录「已被占领」的位置：

ts复制

function solveNQueensBasic(n: number): string[][] { const queens: number[] = []; // queens[row] = col const cols = new Set<number>(); // 已占用的列 const diag1 = new Set<number>(); // 已占用的主对角线（\ 方向） const diag2 = new Set<number>(); // 已占用的副对角线（/ 方向） const solutions: string[][] = []; const render = () => queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)); const backtrack = (row: number) => { if (row === n) { solutions.push(render()); return; } for (let col = 0; col < n; col++) { // 对角线性质的推导见下一节 if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue; queens.push(col); cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(row + 1); queens.pop(); cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); } }; backtrack(0); return solutions; }

三个集合分别对应三类冲突，判断 O(1)，已经够解中等规模。但对角线为什么可以用 row - col 和 row + col 标识？这是本题唯一需要动脑子的数学。

对角线：两个常数

看棋盘坐标 (row, col)：

• 主对角线（\ 方向）：同一条对角线上的格子，row - col 是常数。 (0,0)、(1,1)、(2,2) 都是 0；(0,3)、(1,4) 都是 -3。
• 副对角线（/ 方向）：同一条对角线上的格子，row + col 是常数。 (0,3)、(1,2)、(2,1)、(3,0) 都是 3。

所以「皇后的对角线是否冲突」= 「两个常数值是否已被占用」。N 个格子、2N - 1 条对角线，两条常数各管一边，互不混淆。

版本二：布尔数组换掉 Set

Set 有哈希开销，棋盘规模有限时，用数组更直接：

ts复制

const cols = new Array<boolean>(n).fill(false); const diag1 = new Array<boolean>(2 * n - 1).fill(false); // row - col ∈ [-(n-1), n-1] const diag2 = new Array<boolean>(2 * n - 1).fill(false); // row + col ∈ [0, 2n-2]

判断时把 row - col 平移到非负索引（row - col + n - 1）。这一步已经把性能推到够用，但还有更优雅的形式。

版本三：位运算压缩

把三个「占用表」塞进三个整数：第 col 位为 1 表示第 col 列被占。冲突判断从「查表」变成「按位与」：

ts复制

function totalNQueens(n: number): number { let count = 0; const backtrack = (row: number, cols: number, ld: number, rd: number) => { if (row === n) { count++; return; } // 三个位图上,为 1 的位表示被占用;取反后为 1 的位就是当前行可用的列 // (1 << n) - 1 把范围限制在低 n 位,避免高位垃圾位干扰 let available = ~(cols | ld | rd) & ((1 << n) - 1); while (available) { // lowbit:取出最低位的可用列 const pick = available & -available; available ^= pick; // 从可用集合中移除 backtrack( row + 1, cols | pick, // 该列被占 (ld | pick) << 1, // 左对角线:下一行整体左移一位 (rd | pick) >> 1, // 右对角线:下一行整体右移一位 ); } }; backtrack(0, 0, 0, 0); return count; }

三个技巧一次看完：

1. ~(cols | ld | rd)——三个占用位图取并再取反，剩下的 1 就是本行可用的列；& ((1 << n) - 1) 砍掉高位。
2. available & -available——取出最低位的 1（lowbit），即最左边的可用列。
3. 对角线跟着行走：主对角线受影响的位置每往下一行就左移一列（<< 1），副对角线右移一列（>> 1）。这样连 row - col 的加法都省了——位移就是对角线的几何。

手工推演 n = 4

用版本三的思路走一遍（只走一条成功路径；代码按 lowbit 顺序会先探索第 0 列，该分支无解，最终找到的第一个完整解就是下表这条）：

表中第 2、3 行的 ld/rd 出现了超出 4 位的比特（如 11000），它们来自上一行 << 1 的溢出，不影响结果——available 计算末尾的 & ((1 << n) - 1) 会把高位置 0，只有低 4 位参与判断。

落子序列 [1, 3, 0, 2]，即第一个解。搜索树的其他分支会在某一行发现 available === 0（无列可用）而自然回溯。

复杂度

• 时间复杂度：O(N!) 量级——第 0 行最多 N 个选择，第 1 行最多 N-2 个（扣除列与对角线）……精确上界是 N!，实际被剪枝远低于此。
• 空间复杂度：O(N)——递归深度 N，三个位图常数空间。

常见错误清单

1. 对角线方向搞反：row - col 和 row + col 记混，测试小规模能过、大规模漏解。用 (1,1) 和 (0,3) 两个点现场推导一遍最稳。
2. 忘记撤销状态：cols.delete(col) 漏写，兄弟分支全被污染，结果全错或死循环。
3. 位运算版没限制位宽：~(cols | ld | rd) 在 32 位整数下高位全是 1，不加 & ((1 << n) - 1) 会往不存在的列落子。
4. 输出格式：力扣要求返回字符串棋盘，注意 ".".repeat() 的边界，别把 Q 拼出列外。

小结

N 皇后是回溯算法的「标准教学案例」：它足够小，可以手工推演；又足够深，能一路优化到位运算。真正的收获不是这道题，而是那个通用框架——把问题建模成逐层决策，用占用状态剪枝，用撤销状态回溯。后续做排列组合、数独、子集类问题，都是同一台机器换零件。