N皇后问题详解：Java回溯算法与递归剪枝实战

很多人在刷 LeetCode 热题 100 的时候，遇到 N 皇后这道题第一反应往往是“这题看起来好复杂”“棋盘、皇后、回溯，听着就不像简单题”。确实，它不像反转链表或者两数之和那样有一个固定的套路模板，而是需要你真正理解递归的状态回退逻辑。但换个角度看，N 皇后恰恰是回溯算法最经典、最直观的范例，一旦你把它的递归树想清楚，后面再遇到全排列、组合总和、子集、数独求解这类题，都会轻松不少。这篇文章我想以 Java 实现为主线，把 N 皇后从问题建模、算法选型、代码实现到调试心得完整拆一遍，适合正在准备面试、刷题到回溯专题卡壳的同学，也适合想复习递归搜索原理的开发者。

1. 问题拆解：N 皇后到底在考什么

1.1 从八皇后到 N 皇后：规则的本质

N 皇后问题最早可以追溯到经典的八皇后问题，简单说就是在一个 N×N 的棋盘上放置 N 个皇后，让它们彼此之间不能互相攻击。国际象棋里的皇后攻击范围很霸道，同一行、同一列、同一条对角线上的棋子都能一步吃到，所以题目要求任意两个皇后不能共行、不能共列、不能共斜线。

这种“互相制约”的描述其实隐藏了一个更底层的判断逻辑：我们需要在一个二维棋盘上做多组选择，每一次放置都会对未来可放置的位置产生约束。这跟很多实际场景很像，比如排课表的时候同一时间不能安排两个老师到同一教室，会议室预定的时候不能让时间重叠，甚至八叉树文件系统里查重路径。你不需要真去模拟棋盘上皇后走棋的过程，只需要把“冲突检测”抽象成坐标系上的行列与斜线关系。

N 中的 N 并不是固定值，LeetCode 上最常考的是 N=4、N=8 这种规模，但理论上 N 可以更大。随着 N 增大，搜索空间呈爆炸式增长，4 皇后可能只有 2 个解，8 皇后有 92 个解，10 皇后就有 724 个解，到 15 皇后以上暴力枚举基本跑不动了。这也就是为什么这道题天然适合用回溯来做——它能通过提前剪枝把大量无效分支砍掉，而不是把所有可能都试一遍。

1.2 为什么选择回溯算法而不是状态压缩或搜索

如果你接触过一些高级算法，可能会问：N 皇后能不能用动态规划？能不能用位运算直接枚举？能不能用 A* 搜索？答案是：动态规划不太行，因为 N 皇后的约束条件不满足无后效性原则，前面放置的皇后会影响后面所有位置的合法性，状态空间又高度稀疏；A* 搜索需要设计良好的评估函数，否则性能未必比回溯好，而且题目要求的是全部解，不是找最优路径。

回溯算法本质上是一种带剪枝的深度优先搜索。它把问题拆成“决策序列”：每一行放一个皇后，那么第 i 行可以选择第 0 列到第 N-1 列中的某一列，但必须满足该列和两条对角线没有被之前的皇后占据。如果某一行所有列都试过都不行，就回到上一行，换一个列位置再往下试。这个过程用递归实现特别自然，因为递归调用栈本身就是“路径选择”和“撤销选择”的天然载体。

选择回溯还有一个原因：N 皇后的有效解数量增长虽然快，但剪枝后的搜索空间相对可控。真正的完全解空间是 N 的 N 次方级别，而在回溯中，每行最多 N 个选择，放置失败的分支很快就会被剪掉，实际递归节点数远小于理论值。对于 LeetCode 的 N 取值范围，Java 回溯解法配合合理的冲突检测，运行时间通常在几毫秒到几十毫秒，完全够用。

2. 回溯算法核心框架与 N 皇后的对应关系

2.1 回溯三步曲：路径、选择、结束条件

回溯算法写多了你会发现，几乎所有回溯题都遵循同一个框架。第一步定义“路径”，也就是已经做出的选择，在 N 皇后里就是“已经摆放好的前 i 行皇后位置”；第二步定义“选择列表”，也就是当前位置可以尝试的选项，N 皇后里就是“当前行可以放置皇后的列索引”；第三步定义“结束条件”，N 皇后里就是“我们已经放满了 N 行，说明得到了一个完整解”。

把这个框架对着 N 皇后看，递归函数自然就长这样：

• 进入递归时，我们拿当前行数 row 作为参数，初始从第 0 行开始。
• 在函数内部遍历每一列 col，如果 (row, col) 的位置与已放置的皇后不冲突，就把这个位置记录到棋盘数组里，然后递归处理 row+1。
• 递归返回后，一定要撤销刚才的放置，把棋盘恢复成原样，否则会影响同一层的其他分支尝试。

很多初学者容易漏掉“撤销”这一步。其实不撤销的话，到下一行时棋盘数组里会残留之前尝试过的皇后位置，冲突检测就会误判。这也是回溯和普通递归搜索最本质的区别：回溯在递归返回之后必须把状态重置到进入递归前的样子。

在 Java 里，我们通常用一个二维字符数组 char[][] board 来表示棋盘，初始全部填充为 '.'，放置皇后时把对应位置改成 'Q'，递归返回后再改回 '.'。这样做的好处是，得到解的时候直接把二维数组转成 List 就能返回结果，不需要额外构造数据结构。

2.2 数组表示与冲突检测的三种姿势

N 皇后最关键的细节就是如何快速判断当前位置是否安全。从数学上看，一个点 (row, col) 会和之前放置的皇后发生三种冲突：

• 同一列：之前某行 sameRow 上的皇后所在列 col 等于当前 col；
• 主对角线：同一条主对角线上的点满足 row - col 的值相同；
• 副对角线：同一条副对角线上的点满足 row + col 的值相同。

所以冲突检测有很多写法，常见的有三种。第一种是暴力检查之前所有皇后，逐行比较列和对角线，时间复杂度 O(N)，但实现最简单，N 较小时也不会很慢。第二种是用三个布尔数组 cols、diag1、diag2 分别标记“列是否被占用”“主对角线是否被占用”“副对角线是否被占用”，检测时间降为 O(1)。第三种是位运算，用一个整数的二进制位表示列和两条对角线的占用状态，适合追求极致性能的场景。

我推荐面试时优先掌握第二种。因为布尔数组的语义直观，不容易出错，而且足够快。diag1 的下标可以映射为 row - col + (N-1)，加上偏移量避免负数；diag2 的下标映射为 row + col。这样在放置皇后的时候，只需要把对应的三个布尔值置为 true，回溯撤销时再置回 false 即可，代码非常干净。

3. Java 实现：从最简模板到逐步精化

3.1 第一版：暴力回溯实现

为了理解整个搜索过程，先从最容易代码化的版本写起。我们不搞花哨的数据结构，直接用二维字符数组和一个简单的冲突检测函数。

class Solution { List<List<String>> res = new ArrayList<>(); int n; public List<List<String>> solveNQueens(int n) { this.n = n; char[][] board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); } backtrack(board, 0); return res; } private void backtrack(char[][] board, int row) { if (row == n) { res.add(format(board)); return; } for (int col = 0; col < n; col++) { if (isValid(board, row, col)) { board[row][col] = 'Q'; backtrack(board, row + 1); board[row][col] = '.'; } } } private boolean isValid(char[][] board, int row, int col) { // 检查上方同列 for (int i = 0; i < row; i++) { if (board[i][col] == 'Q') { return false; } } // 检查主对角线（左上方向） for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') { return false; } } // 检查副对角线（右上方向） for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') { return false; } } return true; } private List<String> format(char[][] board) { List<String> resRow = new ArrayList<>(); for (char[] row : board) { resRow.add(new String(row)); } return resRow; } }

这一版的思想很清楚：每一层递归负责一行，for 循环枚举所有列，合法就放，递归到底就保存结果。只要脑中有“递归树从左子树走到右子树再回头”的过程，代码就很好懂。

但要注意，这种写法的 isValid 每次都要从第 0 行往上扫描，最坏情况下复杂度是 O(N!) 再乘一个 O(N) 的检查因子。N=8 时还行，N=10 时明显变慢。这不是算法框架的问题，而是细节优化的空间。

3.2 优化：用布尔数组把冲突检测降到 O(1)

有了第一版的基础，接下来把 isValid 去掉，换成三个布尔数组。主对角线用 row - col + (n - 1) 映射，副对角线用 row + col 映射。

class Solution { List<List<String>> res = new ArrayList<>(); int n; boolean[] cols; boolean[] diag1; boolean[] diag2; char[][] board; public List<List<String>> solveNQueens(int n) { this.n = n; cols = new boolean[n]; diag1 = new boolean[2 * n - 1]; diag2 = new boolean[2 * n - 1]; board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); } backtrack(0); return res; } private void backtrack(int row) { if (row == n) { res.add(format()); return; } for (int col = 0; col < n; col++) { int d1 = row - col + n - 1; int d2 = row + col; if (cols[col] || diag1[d1] || diag2[d2]) { continue; } board[row][col] = 'Q'; cols[col] = true; diag1[d1] = true; diag2[d2] = true; backtrack(row + 1); board[row][col] = '.'; cols[col] = false; diag1[d1] = false; diag2[d2] = false; } } private List<String> format() { List<String> rows = new ArrayList<>(); for (char[] row : board) { rows.add(new String(row)); } return rows; } }

这个版本的代码量并没有增加多少，但 isValid 被彻底消除了。每次尝试一个位置时，只需要做三次数组下标访问，性能提升非常明显。我实际跑过 N=10 的情况，优化后耗时大约只有暴力版本的十分之一。

这里有一个细节值得多说：diag1 和 diag2 数组的长度都是 2 * n - 1，这是因为 row+col 的范围是 0 到 2n-2，row-col+n-1 的范围也是 0 到 2n-2。如果漏掉了这个偏移，会出现数组越界异常，或者把不同的对角线错误地映射到同一个下标。我建议在草稿纸上画一个 4×4 的棋盘，把每条主对角线和副对角线的 row-col 值、row+col 值写出来，你会非常直观地理解这个映射关系。

3.3 位运算进阶方案

如果你是追求极限性能或者想秀一波操作，可以用位运算来进一步优化。原理是让整数的二进制位分别表示“当前行某列是否被占用”“当前行主对角线方向是否被占用”“当前行副对角线方向是否被占用”。利用位运算取最低位的 1，可以快速枚举可用的列。

class Solution { List<List<String>> res = new ArrayList<>(); int n; public List<List<String>> solveNQueens(int n) { this.n = n; char[][] board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); } backtrack(board, 0, 0, 0, 0); return res; } private void backtrack(char[][] board, int row, int cols, int diag1, int diag2) { if (row == n) { List<String> temp = new ArrayList<>(); for (char[] line : board) { temp.add(new String(line)); } res.add(temp); return; } int available = ((1 << n) - 1) & ~(cols | diag1 | diag2); while (available != 0) { int bit = available & (-available); // 取最低位的 1 int col = Integer.numberOfTrailingZeros(bit); board[row][col] = 'Q'; backtrack(board, row + 1, cols | bit, (diag1 | bit) >> 1, (diag2 | bit) << 1); board[row][col] = '.'; available &= available - 1; // 去掉最低位的 1 } } }

位运算这个版本，核心在于用 cols 记录当前列占用，用 diag1 记录主对角线在下一行的受影响列，diag2 记录副对角线在下一行的受影响列。每次递归进入下一行时，主对角线约束要右移一位，副对角线约束要左移一位，因为斜线随着行数增加会平移一个位置。理解起来需要一点时间，但如果你已经吃透了布尔数组版本，再看位运算就会觉得它只是换了一种更紧凑的存储方式。

我不建议所有人一上来就写位运算。面试中更重要的是把回溯的思考过程讲清楚，布尔数组方案已经足够应对。位运算可以作为扩展知识储备，了解它的原理就好，等到需要处理更大规模 N 的时候再用不迟。

4. 实操过程中的坑与调试技巧

4.1 常见错误速查表

N 皇后这道题代码不长，但新手写的时候错误一点都不少。我把常见问题整理成一张速查表，你在翻车的时候直接对照着看。

其中“结果重复”这个问题我想多说一句。有些人会尝试用对称性剪枝来减少搜索空间，比如只搜索一半棋盘然后镜像映射。这个思路本身没问题，但很容易出错，因为你只对“列坐标”做了约束，却没有考虑镜像后的解是否已经出现在递归过程中。如果你只是想先把题做出来，建议先不要加任何剪枝，老老实实按行从第 0 列到第 N-1 列遍历，正确性优先。

4.2 典型调试场景：为什么我的结果总是多解或少解

我在某个模拟项目中看到有人写了这样一个版本：他用了二维布尔数组标记皇后位置，递归逻辑看起来也对，但 N=4 的时候只输出一个解，而标准答案有两个。排查了很久才发现，问题出在他把“棋盘内容”保存到了一个成员变量里，每次找到解后直接把这个成员变量转成 List 加入了结果集。

在 Java 中，如果你把 board 二维数组的引用直接塞进结果集，之后回溯代码一旦把某个位置的 Q 改回 '.',结果集里对应的解也会被同步修改。这其实是很多新手都会踩的坑。正确做法是每次保存结果时遍历当前 board，用 new String(row) 生成不可变的字符串快照。这样后续任何修改都不会影响已经保存的解。

另外一个隐蔽的问题是冲突检测里检查方向的遗漏。有些版本只检查了上方列和左上对角线，没有检查右上对角线。因为在按行逐行放置时，当前行的右上方向可能已经有之前行的皇后存在，比如上一行放在当前列右边的位置，第三行再放的时候就会和它形成副对角线冲突。如果你只检查两个方向，就会得到一些错误解，而且这些解在可视化里偶尔看起来还挺像那么回事，特别容易误导你。

我建议调试的时候先用 N=4 跑一遍标准答案只有两个解的测试用例，如果输出不是 2 个，立刻去看冲突检测是否完整。然后试 N=8，正确结果应该是 92 个解。如果你写出来的程序输出 92 这个数，说明核心逻辑基本没问题。这个方法可以作为一道快速自测题：用不同的 N 去验证解的数量是否和已知数列一致。

5. 拓展应用与面试视角

5.1 LeetCode 热题 100 中的 N 皇后变体

N 皇后在 LeetCode 上并不是孤立的一道题，它有一个更精简的变体叫 N 皇后 II，只要求返回解的个数，不需要返回具体棋盘。看到这个题目，你完全可以在 solveNQueens 的基础上把 res 从 List<List > 改成一个 int 计数器，找到完整解时 count++ 即可。

甚至有更进阶的变体，比如给你一个预置了某些皇后的初始棋盘，求合法解的个数。这种题只是把“从空棋盘开始”的初始化条件改成了“从部分状态开始”，核心的回溯框架完全没有变。面试官喜欢从 N 皇后出发，问到“如果棋盘上有障碍物怎么办”“如果皇后攻击范围变成国际象棋里的骑士怎么办”，其实考的都是你对状态定义和冲突检测的灵活应变能力。

在做热题 100 的时候，我建议把 N 皇后和以下回溯题目放在一起复习：全排列、子集、组合总和、括号生成、单词搜索、解数独。它们共享同一个递归模板，区别只在于路径的定义、选择的枚举方式、剪枝条件和结束条件。当你发现自己能把这些题互相联想起来时，回溯就真的过关了。

5.2 回溯算法在真实场景里的影子

说到实际应用，可能有人觉得刷题离工作太远。但回溯算法本身在真实软件开发中并不罕见。举几个例子：分布式任务调度时要把一组任务分配到多个执行器上且满足资源约束，可以用回溯做可行解的搜索；推荐策略里的组合规则筛选，当候选集不大时也会用回溯枚举所有合规组合；甚至编译器里的某些约束求解，本质上也是在做带回退的深度优先遍历。

回溯算法的价值不在于它能处理千万级数据，而在于它提供了一种“无遗漏枚举 + 及时止损”的思维方式。很多人说回溯性能差，但它在很多小规模离散问题上是唯一简单可靠的解法。N 皇后恰好是理解这种思维的最小训练场：你只需要关心“当前状态是否合法”“下一步有哪些选择”“什么时候保存答案”，剩下的交给递归调用栈。

我还想在工程层面多说一句：在 Java 里写回溯时，要注意递归深度。N 皇后的递归深度最多是 N 层，N 在 100 以内完全不用担心栈溢出。但如果你把回溯用在某些搜索空间特别大的场景，最好评估一下递归深度，必要时用显式栈模拟递归，避免默认栈空间不够用。

如果你看完本文想要继续挑战自己，可以尝试在不看任何参考的情况下，用位运算版本写出 N=15 的解数。你会发现 15 皇后的解数是 2275144 个，按布尔数组遍历会有点慢，但位运算版本在合理时间内还是能跑出来的。这个练习能帮你彻底理解剪枝的执行顺序和状态位的变化规律，也会让你对算法优化产生更具体的体感。

最后分享一个我个人的小经验：很多人学回溯总喜欢背模板，但模板背得再多，遇到具体题目还是容易卡壳。真正有效的方法是拿一道题反复想“为什么递归返回之后要恢复状态”“为什么这个题目可以用同一套框架”，然后用纸笔画出前几层的递归树，把每一步的路径、选择和结束条件标出来。N 皇后就是最适合用来画递归树的题目，因为棋盘本身就天然提供了二维的视觉化结构。我在实际回过头复习回溯专题的时候，经常只重跑 N 皇后这一道题，把三个版本的实现各写一遍，再对比一下运行时间，整个回溯的知识点就全部串起来了。希望这篇文章也能帮你建立起对回溯算法的直觉，下一次在面试里看到 N 皇后时，把它当成老朋友一样轻松解决。