N 皇后问题如何用回溯法求解？（LeetCode 51）

简化版

在 N×N 棋盘放 N 个皇后，使任意两个都不在同一行、同一列、同一对角线上。回溯的关键简化是逐行放置——一行只放一个皇后，行冲突就自动避免了；剩下只需检查列和两条对角线。用三个布尔数组标记「哪列、哪条主对角线、哪条副对角线」已被占。放一个皇后就置标记、递归下一行，冲突或走完就撤销。对角线用 r−c（主）和 r+c（副）编码。

详细版

List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];                 // queens[r] = 第 r 行皇后所在列
    boolean[] col   = new boolean[n];          // 列占用
    boolean[] diag1 = new boolean[2 * n - 1];  // 主对角线（\），下标 r-c+n-1
    boolean[] diag2 = new boolean[2 * n - 1];  // 副对角线（/），下标 r+c
    backtrack(0, n, queens, col, diag1, diag2, res);
    return res;
}
void backtrack(int r, int n, int[] queens, boolean[] col,
               boolean[] d1, boolean[] d2, List<List<String>> res) {
    if (r == n) { res.add(build(queens, n)); return; } // 每行都放好了
    for (int c = 0; c < n; c++) {
        int id1 = r - c + n - 1, id2 = r + c;
        if (col[c] || d1[id1] || d2[id2]) continue;    // 冲突，剪枝
        queens[r] = c; col[c] = d1[id1] = d2[id2] = true;   // 做选择
        backtrack(r + 1, n, queens, col, d1, d2, res);      // 下一行
        col[c] = d1[id1] = d2[id2] = false;                 // 撤销
    }
}

逐行放置：第 r 行只试放一个皇后，行冲突天然消除。
三个标记数组：列 col、主对角线 diag1、副对角线 diag2，O(1) 判断冲突。
对角线编码：同一条主对角线（\）上 r−c 相同；同一条副对角线（/）上 r+c 相同。
build 把 queens[] 转成 .Q.. 形式的棋盘字符串。

完整版教学

一、问题与约束

N 皇后：在 N×N 棋盘上放 N 个皇后，要求任意两个皇后互不攻击——即不能同行、不能同列、不能在同一条对角线（主对角线 \ 或副对角线 /）上。求所有摆法。这是回溯 + 剪枝的经典代表题。

朴素想法是「棋盘每格放或不放」，但那样搜索空间巨大。关键的问题简化能大幅压缩搜索。

二、按行放置：天然避免行冲突

核心简化：一行恰好放一个皇后，逐行往下放。 因为 N 个皇后放在 N 行、每行一个，「同行冲突」从根上就不可能发生——我们连「同行」都不用检查了。

于是回溯的层次变成「行」：第 0 行选一列放皇后 → 第 1 行选一列 → …… → 第 N 行（r == n）说明每行都放好了，收集一个解。每一层的「选择列表」是当前行的 N 个列，逐个尝试。

三、三个标记数组：列、主对角线、副对角线

去掉行冲突后，放皇后在 (r, c) 时只需保证：该列没被占、该主对角线没被占、该副对角线没被占。为了 O(1) 判断，用三个布尔数组记录占用情况：

col[c]：第 c 列是否已有皇后；
diag1[...]：(r,c) 所在的主对角线是否已有皇后；
diag2[...]：所在副对角线是否已有皇后。

放皇后时把这三个位置置 true，撤销时置回 false——又是「做选择 / 撤销选择」的对称操作，只不过一次改三个标记，撤销时也要三个全还原。

四、对角线的编码技巧（r−c 与 r+c）

怎么把「一条对角线」映射到数组下标？靠两个恒等式：

主对角线（\，左上到右下）：同一条上的所有格子，行 − 列 相同。r − c 的取值范围是 −(n−1) 到 n−1，为了当数组下标（非负），加上偏移 n−1，即 id1 = r − c + n − 1，范围 0 ~ 2n−2，共 2n−1 条。
副对角线（/，右上到左下）：同一条上 行 + 列 相同。r + c 范围 0 ~ 2(n−1)，即 0 ~ 2n−2，也是 2n−1 条，直接当下标 id2 = r + c。

记忆点：主对角线看 r−c（要加偏移防负），副对角线看 r+c。这是棋盘对角线判重的通用技巧，数独、对角线遍历都用得上。

五、代码与回溯 + 复杂度

主流程：对当前行 r 遍历每一列 c，算出 id1、id2，若列或两对角线任一被占就 continue 剪枝；否则放皇后（置三个标记、记 queens[r]=c）、递归到 r+1、返回后撤销。r == n 时用 queens[] 拼出棋盘加入结果。

复杂度：第 0 行有 n 种选择、第 1 行至多 n 种……上界约 O(n!)（不是 n^n，因为列不重复用），加上每次拼棋盘 O(n²)。实际因对角线剪枝，可行分支远少于 n!，能解到 n 十几的规模。空间 O(n)（三个标记数组 + 递归栈）。

若只要方案数（N 皇后 II），把收集解换成计数即可，还能用位运算（用三个整数的二进制位代替布尔数组）进一步加速，是常见的进阶优化。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：按行递归使每行恰放一个皇后；columns、diag1(r-c+n-1)、diag2(r+c) 同时保证列和两类对角线无冲突。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：n=4 搜索最终得到 2 个解；位置 (1,3) 的主对角线索引为 1-3+3=1，副对角线为 4。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：位运算可用 n 位掩码加速；n=2、3 无解；对角线数组长度为 2n-1。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：按行放置后只检查列即可。 皇后还会沿两类对角线攻击。
误区：r-c 可直接作数组下标。 可能为负，需加 n-1 偏移。
误区：找到一个解就应立刻返回。 题目要求全部方案时必须继续搜索。
追问：为什么不用行标记？ 递归层就是行，每层只放一个。
追问：复杂度能精确写 n! 吗？ n! 是常用上界，列与对角剪枝会减少实际节点。
追问：如何用位掩码？ 用列、主副对角可用位求当前可选位置，并逐个取最低位。

九、加强记忆

N 皇后回溯：逐行放置（每行一个皇后，行冲突自动消除），只需查列 + 两条对角线。三个布尔数组标记占用，其中主对角线用 r−c+n−1、副对角线用 r+c 当下标（同一条对角线该值相同）。放皇后置三标记、递归下一行、返回撤销（一次改三个、撤销全还原）。r==n 收集解。复杂度约 O(n!)，靠对角线剪枝大幅收窄；只求方案数可用位运算加速。

简化版

详细版