八皇后

本章题海战术

典型例题	leetcode题目	leetcode链接
N 皇后	leetcode 51	https://leetcode.cn/problems/n-queens/description/

八皇后(leetcode 51)

面试官您好，八皇后(leetcode 51)是回溯算法的经典入门题，我从解题思路、代码实现和复杂度几个维度来讲解～

1. 问题定义

在 8×8 的国际象棋棋盘上放置 8 个皇后，要求任意两个皇后不能处于同一行、同一列、同一条对角线上，求解所有合法的摆放方案总数或具体棋盘布局。

通用的 N 皇后问题解法与八皇后完全一致，仅需把边长 8 替换为 n。

2. 核心解题思路 💡

采用回溯 + 剪枝的核心思想，通过降维优化大幅简化判断逻辑：

• 按行依次放置皇后，每行只放 1 个，天然消除行冲突；
• 放置时只需校验 3 个约束条件：
  • 1.当前列没有其他皇后；
  • 2.主对角线（左上→右下）：同一条对角线上 行号 - 列号 的值固定；
  • 3.副对角线（右上→左下）：同一条对角线上 行号 + 列号 的值固定。

如果当前位置合法就继续往下一行放置；走到第 8 行说明找到一个有效解；如果当前行无合法位置，就回退到上一行换一列重试，这就是回溯「试错 - 回退 - 重试」的本质。

3. 回溯过程图解 🧩

以简化的 4 皇后为例，完整展示回溯的决策流程：

4. Java 代码实现 ⚡

用一维数组替代二维棋盘存储结果（下标 = 行号，值 = 列号），空间更省，判断效率更高：

import java.util.ArrayList;
import java.util.List;

public class EightQueens {
    private List<List<String>> result = new ArrayList<>();
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        int[] path = new int[n]; // path[i] = 第i行皇后所在的列号
        backtrack(0, path);
        return result;
    }

    // 回溯：处理第 row 行的皇后放置
    private void backtrack(int row, int[] path) {
        // 终止条件：所有行放置完成，记录一个有效解
        if (row == n) {
            result.add(buildBoard(path));
            return;
        }
        // 枚举当前行的每一列
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, path)) {
                path[row] = col;
                backtrack(row + 1, path);
                // 回溯：数组会被后续循环覆盖，无需手动撤销
            }
        }
    }

    // O(1) 校验当前位置是否存在冲突
    private boolean isValid(int row, int col, int[] path) {
        for (int i = 0; i < row; i++) {
            if (path[i] == col) return false; // 同列冲突
            if (Math.abs(row - i) == Math.abs(col - path[i])) return false; // 对角线冲突
        }
        return true;
    }

    // 将一维数组转换为棋盘格式
    private List<String> buildBoard(int[] path) {
        List<String> board = new ArrayList<>();
        for (int col : path) {
            char[] rowChars = new char[n];
            for (int i = 0; i < n; i++) rowChars[i] = '.';
            rowChars[col] = 'Q';
            board.add(new String(rowChars));
        }
        return board;
    }
}

5. 复杂度分析 📊

维度	复杂度	说明
时间复杂度	O(n!)	第 1 行有 n 种选择，第 2 行最多 n-2 种（排除 1 列 + 2 条对角线），整体呈阶乘级增长
空间复杂度	O(n)	递归调用栈深度为 n，一维路径数组占用 O (n)，不计入结果集的额外存储

6. 进阶优化点 ✨

1. 位运算优化：用 3 个整数分别标记列、主副对角线的占用状态，通过位运算 O (1) 完成冲突判断，速度提升显著，空间进一步压缩；
2. 对称剪枝：利用棋盘的左右对称性，只枚举一半的列，再通过对称生成另一半解，减少约一半的计算量；
3. 针对 N 极大的场景，还可以延伸到舞蹈链（DLX）、启发式搜索等更高效的算法。

八皇后本质考察的是「全排列枚举 + 约束条件剪枝」的回溯思想，同类题型还有解数独、全排列、子集组合等，核心套路都是「做选择→递归→撤销选择」。

7. 核心亮点代码拆解 ⚡

这里分两档给出：面试标准写法（基础满分）和位运算进阶版（加分拉差距），均为可直接运行的核心片段。

7.1 基础标准写法（面试必答・核心亮点）

这是面试中最稳妥、扣分点最少的写法，核心亮点是降维设计 + 隐式回溯，比二维棋盘的写法高一个档次。

// 核心回溯入口
private void backtrack(int row, int[] path) {
    // 终止条件：所有行放置完成，找到有效解
    if (row == n) {
        result.add(buildBoard(path));
        return;
    }
    // 枚举当前行所有可选列
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, path)) {
            path[row] = col;          // 做选择：记录当前行皇后的列位置
            backtrack(row + 1, path); // 递归处理下一行
            // ✅ 技术亮点：无需显式撤销选择，下一轮循环直接覆盖数组值，天然完成回溯
        }
    }
}

// ✅ 技术亮点：数学规律校验，无需遍历整行整列
private boolean isValid(int row, int col, int[] path) {
    for (int i = 0; i < row; i++) {
        if (path[i] == col) return false;                  // 同列冲突
        if (Math.abs(row - i) == Math.abs(col - path[i]))  // 对角线冲突
            return false;
    }
    return true;
}

亮点总结：

1. 空间降维：用 path[行号] = 列号 的一维映射替代 n×n 二维棋盘，空间复杂度从 O (n²) 压缩至 O (n)
2. 逻辑去重：按行放置天然保证行不重复，直接省去行冲突的判断逻辑
3. 代码精简：利用数组原地赋值特性，省略了回溯算法中「撤销选择」的冗余步骤

7.2 位运算极致优化版（进阶加分・拉开差距）

大厂面试的加分项，用纯位运算实现 O (1) 冲突判断，完全没有循环校验，性能比基础版提升 5~10 倍，是体现算法功底的亮点写法。

private int count = 0;
private int n;

// 仅统计八皇后解的总数，不存储具体棋盘
public int totalNQueens(int n) {
    this.n = n;
    dfs(0, 0, 0, 0);
    return count;
}

/**
 * 位运算回溯核心（全O(1)操作，无循环校验）
 * @param row      当前处理行
 * @param colMark  列占用标记：二进制位为1表示该列已被占用
 * @param mainDiag 主对角线占用标记（左上→右下）
 * @param subDiag  副对角线占用标记（右上→左下）
 */
private void dfs(int row, int colMark, int mainDiag, int subDiag) {
    if (row == n) { count++; return; }
    
    // 计算当前行所有合法位置：取反后保留n位有效位，1代表可放置
    int validPos = ((1 << n) - 1) & ~(colMark | mainDiag | subDiag);
    
    while (validPos != 0) {
        int pos = validPos & -validPos; // lowbit技巧：取出最低位的1，即选中一列
        validPos &= validPos - 1;       // 清除已选中的位置，不再重复枚举
        
        // ✅ 技术亮点：对角线随行下移自动左/右偏移，天然对应下一行的冲突位置
        dfs(row + 1, 
            colMark | pos, 
            (mainDiag | pos) << 1, 
            (subDiag | pos) >> 1
        );
    }
}

亮点总结：

1. 极致效率：3 个整数的二进制位映射占用状态，单次冲突判断仅需一次位或运算，O (1) 时间复杂度
2. 空间极致：全程仅用 4 个 int 变量传递状态，额外空间复杂度 O (1)（不计递归栈）
3. 技巧性强：lowbit 经典位运算技巧，快速提取可选位置，是算法功底的直观体现

8. 技术难点与解决方案对照表 📋

针对八皇后场景的常见痛点与对应解法，整理成面试可直接复述的结构化内容：

技术难点	痛点影响	解决方案	核心原理
冲突判断效率低	原生写法需遍历所有已放置皇后，单次校验 O (n)，n 增大时耗时指数级上升	对角线数学建模 + 位运算标记法	主对角线「行号 - 列号」值固定、副对角线「行号 + 列号」值固定；用二进制位直接映射占用状态，O (1) 完成校验
棋盘存储空间冗余	二维数组存储棋盘，空间占用 O (n²)，n 增大时内存浪费严重	一维数组行列映射	下标代表行号，值代表列号，用线性结构完整表达二维位置信息，空间压缩至 O (n)
全量枚举计算冗余	完整枚举所有列的排列，存在对称重复的无效计算	对称剪枝优化	棋盘具备左右对称性，仅枚举前半部分列，找到解后通过镜像翻转生成另一半解，计算量减少约 50%
递归深度过高栈溢出	n 极大时递归深度等于 n，超出 JVM 默认栈深度，触发 StackOverflowError	迭代式回溯实现	用栈结构手动模拟递归调用栈，保存每一行的枚举状态，规避 JVM 递归栈深度限制
结果集内存膨胀	n 增大时解数量指数级增长，存储所有棋盘布局占用大量内存	计数模式 / 按需生成	若题目仅求解的总数，不存储具体棋盘，只维护计数器；需输出时再按需生成单种布局
对角线逻辑易写错	新手容易混淆两条对角线的计算逻辑，导致边界错误或漏判	固定公式 + 小用例验证	记住「行差绝对值 == 列差绝对值 → 同对角线」，用 4 皇后小用例快速验证逻辑正确性

真实面试模拟

真实面试模拟

面试官 😊：

你好，欢迎来参加今天的面试。先来个经典算法题热热身吧——八皇后问题(leetcode 51)你应该听过，能简单说下这个问题是什么吗？

求职者 🤓：

好的。八皇后就是在 8×8 的国际象棋棋盘上，放 8 个皇后，要求它们互相不能攻击。皇后的攻击范围是横、竖、两条对角线，就像一个“米”字。我们要找出所有合法的摆放方式，经典答案是一共有 92 种解。

面试官 👍：

对，描述得挺清楚。那你打算怎么解呢？说说思路。

求职者 💡：

我打算用回溯算法。核心思路是逐行放置皇后，因为每行有且只能有一个皇后。在每一行，我从第 0 列试到第 7 列，如果当前位置和前面已经放好的皇后不冲突，就放下皇后，然后递归进入下一行。如果某一行所有列都试过都不行，就回溯到上一行，换一个列继续试。

为了快速判断冲突，我用一个一维数组 queens[row] = col 表示第 row 行的皇后放在第 col 列。判断是否与前面第 i 行的皇后冲突，就看三个条件：

• 同列：queens[i] == col
• 主对角线（左上到右下）：row - col == i - queens[i]
• 副对角线（右上到左下）：row + col == i + queens[i]

只要满足任意一个条件，就不能放。

面试官 🧐：

嗯，思路清晰。那你觉得为什么用 row - col 和 row + col 就能判断对角线？能画一下吗？

求职者 ✍️：

当然。假设我们已经放了两个皇后：

  0 1 2 3 4 5 6 7
0 . . . . ♛ . . .
1 . . ♛ . . . . .
2 . . . . . . . .

• 皇后1在 (0,4)，row-col = 0-4 = -4
• 皇后2在 (1,2)，row-col = 1-2 = -1，不相等，不在同一主对角线。

如果是同一条主对角线，比如 (0,2) 和 (1,1)，0-2=-2，1-1=0？哦不，这里更正一下：主对角线是左上到右下，特点是 行号 - 列号 为常数。例如 (0,3) 0-3=-3，(1,2) 1-2=-1，不对，它们不在同一主对角线。正确的是 (0,3) 和 (1,4)：0-3=-3，1-4=-3，这才相等。刚才我的图里 (0,4) 和 (1,2) 差值是 -4 和 -1，所以不在同一主对角线上，安全 ✅。

那副对角线呢？看 (0,4) 和 (1,3)：0+4=4，1+3=4，它们在一条副对角线上，冲突 ❌。所以用 行号+列号 为常数 来判断副对角线很巧妙。

面试官 😄：

很好，图画得不错。那你能直接用 Java 把这个回溯实现写出来吗？注意代码规范和边界条件。

求职者 ⌨️：

没问题，我马上写。我会定义一个 solve() 方法启动回溯，核心是 backtrack(row) 递归。

public class EightQueens {
    private int[] queens = new int[8]; // 索引=行号, 值=列号
    private int solutions = 0;

    public void solve() {
        backtrack(0);
        System.out.println("总解数: " + solutions);
    }

    private void backtrack(int row) {
        if (row == 8) {            // 找到一个解
            printSolution();
            solutions++;
            return;
        }
        for (int col = 0; col < 8; col++) {
            if (isValid(row, col)) {
                queens[row] = col;        // 放置皇后
                backtrack(row + 1);       // 递归下一行
                // 回溯：下一次循环 col++ 会直接覆盖 queens[row]
                // 无需显式移除
            }
        }
    }

    private boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col ||
                row - col == i - queens[i] ||
                row + col == i + queens[i]) {
                return false;
            }
        }
        return true;
    }

    private void printSolution() {
        System.out.println("解 " + (solutions + 1) + ":");
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                System.out.print(queens[row] == col ? "♛ " : "· ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new EightQueens().solve();
    }
}

面试官 👀：

嗯，代码写得挺规整。那你说说这个解法的时间、空间复杂度是多少？

求职者 📊：

时间复杂度最坏是 O(N!)，但因为我们有剪枝，实际运行会快很多，8 皇后也只有 92 种解。空间复杂度 O(N)，主要就是递归栈深度和 queens 数组。

面试官 🤔：

能不能再优化一下？比如判断冲突有没有更快的方法？

求职者 🚀：

有！可以用位运算把列、主对角线、副对角线的占用状态压缩成三个整数。这样冲突判断就变成 O(1) 的位操作，常数时间，非常快。基本思路是：

• 用 colMask 记录哪些列被占了
• diag1 记录主对角线占用，下一行它会左移一位（因为行增加，列不变的话，主对角线“编号”会变化）
• diag2 记录副对角线占用，下一行它会右移一位

每一步用 available = ((1<<N)-1) & ~(colMask | diag1 | diag2) 得到所有可以放的列，然后每次取最低位的 1，递归下去。这种实现能大幅提升 N 皇后问题的运行速度。

这是技术亮点代码：

public class NQueensBit {
    private int N, count;
    
    public int totalNQueens(int n) {
        this.N = n;
        backtrack(0, 0, 0, 0);
        return count;
    }
    
    private void backtrack(int row, int colMask, int diag1, int diag2) {
        if (row == N) {
            count++;
            return;
        }
        // 得到当前行所有可用的列位置（bit 为 1 表示可用）
        int available = ((1 << N) - 1) & ~(colMask | diag1 | diag2);
        while (available != 0) {
            int pos = available & -available; // 提取最低位的1
            available ^= pos;                 // 移除该位
            // 递归：diag1左移，diag2右移
            backtrack(row + 1,
                      colMask | pos,
                      (diag1 | pos) << 1,
                      (diag2 | pos) >> 1);
        }
    }
}

这样冲突判断为 O(1)，整体算法效率极高，N=20 也能秒出。

面试官 🎯：

非常好！那结合这道题，你能总结一下技术难点和对应的解决方案吗？

求职者 🧑‍💻：

当然，主要有三个难点：

技术难点	为什么难	解决方案
1. 如何表示棋盘状态	二维棋盘看似需要二维数组，但皇后特性决定每行只有一个，容易浪费空间或造成冗余判断	用一维数组 queens[row] = col，索引表示行，值表示列，状态精简且访问 O(1)
2. 对角线的冲突判断	对角线不是直观的“行/列相等”，需要找到统一的数学规律	发现主对角线 row-col 为常数，副对角线 row+col 为常数，以此快速计算
3. 回溯时如何高效剪枝	普通判断每放一个皇后要遍历前面所有行，O(N) 检查	用三个集合（列、主对角、副对角）记录占用，判断降到 O(1)；进一步用位运算压缩到三个整数，常数时间更快
4. 解的数量与性能	N 较大时搜索树庞大，需极限优化	位运算版本利用 CPU 字长并行，结合对称性剪枝（第一个皇后只放前半行），可大幅减少计算量

面试官 🌟：

太棒了！从原理到实现，再到位运算极致优化，还能总结出难点和解决方案，说明你不仅会写代码，更有工程化思维。这轮面试，给你过！

求职者 😊：

谢谢面试官，我会继续深入学习算法底层优化。