很多人在刷 LeetCode 热题 100 的时候遇到 N 皇后这道题第一反应往往是“这题看起来好复杂”“棋盘、皇后、回溯听着就不像简单题”。确实它不像反转链表或者两数之和那样有一个固定的套路模板而是需要你真正理解递归的状态回退逻辑。但换个角度看N 皇后恰恰是回溯算法最经典、最直观的范例一旦你把它的递归树想清楚后面再遇到全排列、组合总和、子集、数独求解这类题都会轻松不少。这篇文章我想以 Java 实现为主线把 N 皇后从问题建模、算法选型、代码实现到调试心得完整拆一遍适合正在准备面试、刷题到回溯专题卡壳的同学也适合想复习递归搜索原理的开发者。1. 问题拆解N 皇后到底在考什么1.1 从八皇后到 N 皇后规则的本质N 皇后问题最早可以追溯到经典的八皇后问题简单说就是在一个 N×N 的棋盘上放置 N 个皇后让它们彼此之间不能互相攻击。国际象棋里的皇后攻击范围很霸道同一行、同一列、同一条对角线上的棋子都能一步吃到所以题目要求任意两个皇后不能共行、不能共列、不能共斜线。这种“互相制约”的描述其实隐藏了一个更底层的判断逻辑我们需要在一个二维棋盘上做多组选择每一次放置都会对未来可放置的位置产生约束。这跟很多实际场景很像比如排课表的时候同一时间不能安排两个老师到同一教室会议室预定的时候不能让时间重叠甚至八叉树文件系统里查重路径。你不需要真去模拟棋盘上皇后走棋的过程只需要把“冲突检测”抽象成坐标系上的行列与斜线关系。N 中的 N 并不是固定值LeetCode 上最常考的是 N4、N8 这种规模但理论上 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) 的位置与已放置的皇后不冲突就把这个位置记录到棋盘数组里然后递归处理 row1。递归返回后一定要撤销刚才的放置把棋盘恢复成原样否则会影响同一层的其他分支尝试。很多初学者容易漏掉“撤销”这一步。其实不撤销的话到下一行时棋盘数组里会残留之前尝试过的皇后位置冲突检测就会误判。这也是回溯和普通递归搜索最本质的区别回溯在递归返回之后必须把状态重置到进入递归前的样子。在 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 { ListListString res new ArrayList(); int n; public ListListString 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 ListString format(char[][] board) { ListString resRow new ArrayList(); for (char[] row : board) { resRow.add(new String(row)); } return resRow; } }这一版的思想很清楚每一层递归负责一行for 循环枚举所有列合法就放递归到底就保存结果。只要脑中有“递归树从左子树走到右子树再回头”的过程代码就很好懂。但要注意这种写法的 isValid 每次都要从第 0 行往上扫描最坏情况下复杂度是 O(N!) 再乘一个 O(N) 的检查因子。N8 时还行N10 时明显变慢。这不是算法框架的问题而是细节优化的空间。3.2 优化用布尔数组把冲突检测降到 O(1)有了第一版的基础接下来把 isValid 去掉换成三个布尔数组。主对角线用 row - col (n - 1) 映射副对角线用 row col 映射。class Solution { ListListString res new ArrayList(); int n; boolean[] cols; boolean[] diag1; boolean[] diag2; char[][] board; public ListListString 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 ListString format() { ListString rows new ArrayList(); for (char[] row : board) { rows.add(new String(row)); } return rows; } }这个版本的代码量并没有增加多少但 isValid 被彻底消除了。每次尝试一个位置时只需要做三次数组下标访问性能提升非常明显。我实际跑过 N10 的情况优化后耗时大约只有暴力版本的十分之一。这里有一个细节值得多说diag1 和 diag2 数组的长度都是 2 * n - 1这是因为 rowcol 的范围是 0 到 2n-2row-coln-1 的范围也是 0 到 2n-2。如果漏掉了这个偏移会出现数组越界异常或者把不同的对角线错误地映射到同一个下标。我建议在草稿纸上画一个 4×4 的棋盘把每条主对角线和副对角线的 row-col 值、rowcol 值写出来你会非常直观地理解这个映射关系。3.3 位运算进阶方案如果你是追求极限性能或者想秀一波操作可以用位运算来进一步优化。原理是让整数的二进制位分别表示“当前行某列是否被占用”“当前行主对角线方向是否被占用”“当前行副对角线方向是否被占用”。利用位运算取最低位的 1可以快速枚举可用的列。class Solution { ListListString res new ArrayList(); int n; public ListListString 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) { ListString 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 皇后这道题代码不长但新手写的时候错误一点都不少。我把常见问题整理成一张速查表你在翻车的时候直接对照着看。错误类型表现原因与排查方法结果少了若干解输出解的数量比正确答案少大概率是在回溯撤销时漏掉了某个状态恢复导致后续分支的冲突检测被“假占用”干扰结果重复同一个解出现多次可能是在递归过程中没有固定行顺序或者用了不正确的对称剪枝方式正常按行递归不会出现重复数组越界ArrayIndexOutOfBoundsExceptiondiag1 或 diag2 计算错误尤其没有加偏移量检查 row ± col 的范围输出全部是空棋盘没有任何 Q递归结束条件或行推进逻辑写错比如 row1 写成了 row死循环或栈溢出程序卡死或 StackOverflowError递归没有终止条件或者把 row 参数在递归调用中又改了回来返回结果出现全棋盘 . 的行某一行没有皇后在保存结果时board 对象还在被后续递归修改保存的是引用而不是快照Java 中需要 new String 生成新对象其中“结果重复”这个问题我想多说一句。有些人会尝试用对称性剪枝来减少搜索空间比如只搜索一半棋盘然后镜像映射。这个思路本身没问题但很容易出错因为你只对“列坐标”做了约束却没有考虑镜像后的解是否已经出现在递归过程中。如果你只是想先把题做出来建议先不要加任何剪枝老老实实按行从第 0 列到第 N-1 列遍历正确性优先。4.2 典型调试场景为什么我的结果总是多解或少解我在某个模拟项目中看到有人写了这样一个版本他用了二维布尔数组标记皇后位置递归逻辑看起来也对但 N4 的时候只输出一个解而标准答案有两个。排查了很久才发现问题出在他把“棋盘内容”保存到了一个成员变量里每次找到解后直接把这个成员变量转成 List 加入了结果集。在 Java 中如果你把 board 二维数组的引用直接塞进结果集之后回溯代码一旦把某个位置的 Q 改回 .,结果集里对应的解也会被同步修改。这其实是很多新手都会踩的坑。正确做法是每次保存结果时遍历当前 board用 new String(row) 生成不可变的字符串快照。这样后续任何修改都不会影响已经保存的解。另外一个隐蔽的问题是冲突检测里检查方向的遗漏。有些版本只检查了上方列和左上对角线没有检查右上对角线。因为在按行逐行放置时当前行的右上方向可能已经有之前行的皇后存在比如上一行放在当前列右边的位置第三行再放的时候就会和它形成副对角线冲突。如果你只检查两个方向就会得到一些错误解而且这些解在可视化里偶尔看起来还挺像那么回事特别容易误导你。我建议调试的时候先用 N4 跑一遍标准答案只有两个解的测试用例如果输出不是 2 个立刻去看冲突检测是否完整。然后试 N8正确结果应该是 92 个解。如果你写出来的程序输出 92 这个数说明核心逻辑基本没问题。这个方法可以作为一道快速自测题用不同的 N 去验证解的数量是否和已知数列一致。5. 拓展应用与面试视角5.1 LeetCode 热题 100 中的 N 皇后变体N 皇后在 LeetCode 上并不是孤立的一道题它有一个更精简的变体叫 N 皇后 II只要求返回解的个数不需要返回具体棋盘。看到这个题目你完全可以在 solveNQueens 的基础上把 res 从 ListList 改成一个 int 计数器找到完整解时 count 即可。甚至有更进阶的变体比如给你一个预置了某些皇后的初始棋盘求合法解的个数。这种题只是把“从空棋盘开始”的初始化条件改成了“从部分状态开始”核心的回溯框架完全没有变。面试官喜欢从 N 皇后出发问到“如果棋盘上有障碍物怎么办”“如果皇后攻击范围变成国际象棋里的骑士怎么办”其实考的都是你对状态定义和冲突检测的灵活应变能力。在做热题 100 的时候我建议把 N 皇后和以下回溯题目放在一起复习全排列、子集、组合总和、括号生成、单词搜索、解数独。它们共享同一个递归模板区别只在于路径的定义、选择的枚举方式、剪枝条件和结束条件。当你发现自己能把这些题互相联想起来时回溯就真的过关了。5.2 回溯算法在真实场景里的影子说到实际应用可能有人觉得刷题离工作太远。但回溯算法本身在真实软件开发中并不罕见。举几个例子分布式任务调度时要把一组任务分配到多个执行器上且满足资源约束可以用回溯做可行解的搜索推荐策略里的组合规则筛选当候选集不大时也会用回溯枚举所有合规组合甚至编译器里的某些约束求解本质上也是在做带回退的深度优先遍历。回溯算法的价值不在于它能处理千万级数据而在于它提供了一种“无遗漏枚举 及时止损”的思维方式。很多人说回溯性能差但它在很多小规模离散问题上是唯一简单可靠的解法。N 皇后恰好是理解这种思维的最小训练场你只需要关心“当前状态是否合法”“下一步有哪些选择”“什么时候保存答案”剩下的交给递归调用栈。我还想在工程层面多说一句在 Java 里写回溯时要注意递归深度。N 皇后的递归深度最多是 N 层N 在 100 以内完全不用担心栈溢出。但如果你把回溯用在某些搜索空间特别大的场景最好评估一下递归深度必要时用显式栈模拟递归避免默认栈空间不够用。如果你看完本文想要继续挑战自己可以尝试在不看任何参考的情况下用位运算版本写出 N15 的解数。你会发现 15 皇后的解数是 2275144 个按布尔数组遍历会有点慢但位运算版本在合理时间内还是能跑出来的。这个练习能帮你彻底理解剪枝的执行顺序和状态位的变化规律也会让你对算法优化产生更具体的体感。最后分享一个我个人的小经验很多人学回溯总喜欢背模板但模板背得再多遇到具体题目还是容易卡壳。真正有效的方法是拿一道题反复想“为什么递归返回之后要恢复状态”“为什么这个题目可以用同一套框架”然后用纸笔画出前几层的递归树把每一步的路径、选择和结束条件标出来。N 皇后就是最适合用来画递归树的题目因为棋盘本身就天然提供了二维的视觉化结构。我在实际回过头复习回溯专题的时候经常只重跑 N 皇后这一道题把三个版本的实现各写一遍再对比一下运行时间整个回溯的知识点就全部串起来了。希望这篇文章也能帮你建立起对回溯算法的直觉下一次在面试里看到 N 皇后时把它当成老朋友一样轻松解决。