N皇后问题详解：回溯算法与剪枝思路全解析

1. N 皇后到底在考什么1.1 题目说的“放置规则”翻译成人话力扣 hot100 里的 N 皇后力扣编号 51是回溯算法里出镜率最高的一道题。很多人第一次看完题面会愣一下一个 n x n 的棋盘往里面放 n 个皇后要求它们互相不能攻击。皇后在国际象棋里能横着走、竖着走、斜着走也就是说任意两个皇后不能在同一行、同一列、同一条斜线上。放到一个数组场景里其实就是让你在棋盘上挑 n 个格子保证这些格子之间没有任何两个处于共行、共列或者共斜线的状态。这道题在很多刷题攻略里都排在回溯专题的前几名原因很简单它几乎是“回溯 剪枝”的标准教材。写这个题之前你需要先接受一个事实——它不是一个让你直接套模板就能秒杀的题它的“冲突判断”部分才是真正容易出错的地方。很多人第一次写的时候用的棋盘是二维字符数组然后递归的每一层代表行循环里的每一列代表当前行尝试放皇后的位置。这个模型想清楚之后代码的结构就基本定下来了。我当年第一次碰到这题是在准备面试刷 hot100 的时候。题目标着困难难度但后来仔细分析它其实没有用到什么特别高级的算法本质就是 DFS 状态恢复。困难主要体现在两个地方一是 n 的范围可以到 9 甚至更大纯暴力的排列组合会爆炸二是你要把“摆放结果”还原成题目要求的字符串棋盘格式这一步虽然不难但很容易在边界处理上翻车。1.2 Hot100 为什么要收录这题力扣 hot100 是很多人的刷题主线它选取的是面试和竞赛中最高频、最能考察算法思维的题目。N 皇后被收录进去我理解有三个原因。第一它考察的是你能不能把“递归搜索”和“约束条件”结合到一起。很多回溯题的回溯逻辑是固定的但 N 皇后要求你自行设计冲突检测这是新手和老手的天然分水岭。第二它非常适合作“状态压缩”的入门题。当 n 很大时你可以用三个整数来替代整个棋盘做冲突判断这种空间优化思想在后续的很多题里都能复用。第三它的输出形式有明确的格式要求能考察你对数据结构操作是否熟练。实际上hot100 题解 PDF 和各类刷题攻略里N 皇后永远会被放在“回溯算法”栏目的第一个或第二个位置紧跟在全排列、组合总和后面。它的代码量不算大但回看率特别高很多人在面试前一周还在重新默写这题的两种写法。2. 回溯解法的整体设计与思路拆解2.1 为什么第一反应应该是回溯拿到 N 皇后这个问题最自然的想法是从第一行开始逐个尝试把皇后放在这一行的每一列放下去之前检查一下当前布局合不合法合法就继续往下一行走不合法就换下一列如果当前行的所有列都不能放就回到上一行把上一行皇后换个位置。这就是回溯。你可能会问为什么不用动态规划因为 N 皇后要求的是“所有可行解”而且每一步的选择会影响后续所有选择这种问题的最优解本质上是搜索问题不是最优化问题。贪心也不可能皇后之间的冲突是全局性的无法通过局部最优推导全局最优。回溯天然适合这种“决策树 剪枝”的搜索模型。这题的搜索顺序也很有讲究。通常我们按行逐层搜索因为每行最多只能放一个皇后这个性质直接来源于题目规则——任意两个皇后不能在同一行。也就是说n 个皇后分布在 n 行上每行恰好只能有一个。如果某一行没有放皇后那总量就不够 n 个了。所以递归深度天然固定为 n每一层递归只需要解决“当前行的皇后放在哪一列”这一个问题。用决策树来想象根节点是空棋盘第一层有 n 个子节点第一行的 n 列选择第二层是第一行确定后第二行的可选列依此类推。不带任何剪枝时搜索空间是 n^n 级别。但加上合法检查之后大量分支会被直接截断实际的搜索规模会小很多至少在 n 9 时是能在毫秒级跑完的。2.2 棋盘表示与递归搜索的框架N 皇后题解里最常见的数据结构有两种选择。一种是用二维字符数组ListString作为棋盘在撤销时把字符重新改回点号另一种是用一维数组int[] queens记录每一行皇后所在的列比如queens[row] col就表示第 row 行的皇后放在第 col 列。最终生成棋盘时再根据这个一维数组一行一行地拼字符串。我强烈建议你优先理解第二种也就是用一维数组保存列信息。原因有两个首先一维数组做冲突判断更直观你只需要检查当前要放的列是否和之前所有行的列冲突再检查两条斜线是否冲突其次最终输出的时候根据列号在对应位置插入Q比在二维数组里反复改字符要干净得多。很多 hot100 题解 PDF 里给出的也是这种写法。递归搜索的伪代码框架其实很固定void backtrack(row) 如果 row n 把 queens 数组转换成棋盘格式加入结果集 返回 遍历 col 从 0 到 n-1 如果 (row, col) 这个位置可以放皇后 记录 queens[row] col backtrack(row 1) 撤销 queens[row] -1可以放皇后的判断条件需要满足三点第一当前列在之前没有被占用第二当前主对角线方向没有冲突第三当前副对角线方向没有冲突。这里再强调一下回溯的“撤销”操作非常重要。queens[row] -1看起来像是一句废话因为下一次循环会立刻覆盖这个位置的值但如果你的实现里还额外维护了colUsed、diagUsed、antiDiagUsed这类布尔数组那么撤销时一定要把这三个状态全部还原。漏掉任何一个状态都会导致后续搜索中出现错误的剪枝输出结果直接少解或者多解。2.3 回溯的“三要素”选择、约束、撤销我在写回溯题的时候习惯先用三句话把题目拆开。选择是什么约束是什么撤销是什么。N 皇后的选择是“当前行把皇后放在哪一列”也就是循环变量 col。约束是“这个位置和之前已放置的皇后不能同行、同列、同斜线”。由于我们是逐行放置的同行冲突天然不存在同列冲突可以用一个列占用数组或集合判断斜线冲突则需要靠坐标关系判断——两个位置如果处在同一条主对角线那么它们的row - col是一个常数如果处在同一条副对角线那么它们的row col是一个常数。撤销就是把这一行皇后恢复成未放置的状态。这里有一个常见的误区很多初学者认为撤销只需要把数组下标挪回去就行比如递归返回后自动就回到上一层了。但如果你真的用一个成员变量记录“当前行号”在递归入口对行号做自增、递归返回后做自减那么其实棋盘上的皇后位置数组不需要立刻清空因为它会在下一次放置时被覆盖。只有当额外使用布尔标记数组时才必须同步撤销标记不然会污染后续搜索。3. 核心细节解析与实操要点3.1 行列、对角线怎么高效判断皇后冲突判断是这题的重中之重。逐个遍历之前已经放过的皇后判断它们是否在同一列或同一条斜线上这种方法当然正确但每次放置都要 O(n) 的检查时间整体复杂度会变成 O(n * n!)在 n 较大时仍会超时。更好的做法是用空间换时间为列、主对角线、副对角线分别维护占用标记。列冲突很好办一个长度为 n 的布尔数组colUsedcolUsed[c]为 true 就表示第 c 列已经有皇后了。斜线冲突需要推导一下。假设当前位置是(row, col)主对角线上的所有格子都有一个共同特点row - col是固定值。副对角线上的所有格子row col是固定值。举例来说(0, 0)、(1, 1)、(2, 2) 这条主对角线上row - col都等于 0(0, 3)、(1, 2)、(2, 1) 这条副对角线上row col都等于 3。所以判断当前位置(row, col)是否和已有皇后冲突只需要检查下面这三个条件!colUsed[col] !diagUsed[row - col n - 1] !antiDiagUsed[row col]看到这里你可能会疑惑row - col可能是负数数组下标不能是负的所以需要统一加一个偏移量n - 1。加完之后row - col的范围从-(n - 1)到n - 1整体加n - 1后变成从 0 到2n - 2。主对角线标记数组的长度要开成2n - 1副对角线同理。我见过很多代码把这两个数组长度误写成 n导致运行到一半数组越界。这个问题在 n 比较小的时候不容易暴露一旦你测试 n 4 或更大立刻就会崩溃。所以记住主副对角线数组长度都要开2n - 1。3.2 剪枝与提前终止回溯天然的剪枝动作就是“发现当前行某一列不能放就跳过这一列”。但 N 皇后还有一个可以提前终止的隐藏条件如果你用行递归某一层发现所有列都不能放那么这一整棵子树都不用继续搜索了。递归算法里这个逻辑是隐式完成的——循环跑完仍然没有进入下一步递归函数自然返回上层会继续尝试其他位置。所谓的“提前终止”在一些变种题里会更明显比如“N 皇后 II”只要求统计解的个数那你在收集结果时不需要再生成棋盘字符串直接把计数器加一就能省下大量字符串拼接的时间。再进阶一点剪枝可以依赖对称性优化。N 皇后问题的解具有左右对称性如果某个解在第一行第 k 列放皇后那么把整个棋盘左右镜像后第一行第 n - 1 - k 列放皇后也是一个合法解。因此理论上可以让第一行的皇后只遍历左半部分然后通过镜像生成另一半结果。但这里有个坑当第一行的皇后恰好落在正中间列时镜像会和自己重合需要单独处理去重。实际工程里这个优化性价比不高因为真正耗时的不是第一层的搜索而是深层递归的冲突判断做对称剪枝会让代码复杂度高很多收益却很有限。除非你参加竞赛追求极限性能否则不建议在面试里写这种优化。3.3 少走弯路的几个小技巧第一点建议把棋盘每一行的字符串生成放到结果收集阶段统一处理不要在搜索过程中反复拼接字符串。搜索过程中你只维护queens数组收集结果时再遍历这个数组用 StringBuilder 按列号生成Q和.的排列。这样做的好处是搜索过程完全不受字符串操作干扰回溯时也不需要恢复字符串状态。第二点注意递归方法里的参数传递。如果queens数组是类的成员变量递归方法里修改它是全局生效的撤销时只需要覆盖旧值即可。但如果把queens复制一份传入下一层递归那么内存开销会很大而且深层递归的修改不会影响上层这反而违背了回溯的本意。正确做法是共享同一个数组配合“放置-撤销”模式。第三点尽量从第 0 行开始递归不要把行号从 1 开始。很多新手受日常计数习惯影响喜欢从 1 开始编号但数组下标天然从 0 开始从 0 开始写可以少很多减一的操作。4. 实操过程与核心环节实现4.1 完整可运行的 Java 代码我用 Java 写一版最常用的实现这份代码我在力扣上提交过n 9 时耗时可接受逻辑也比较清晰。class Solution { private ListListString res new ArrayList(); private int n; private int[] queens; private boolean[] colUsed; private boolean[] diagUsed; private boolean[] antiDiagUsed; public ListListString solveNQueens(int n) { this.n n; queens new int[n]; Arrays.fill(queens, -1); colUsed new boolean[n]; diagUsed new boolean[2 * n - 1]; antiDiagUsed new boolean[2 * n - 1]; backtrack(0); return res; } private void backtrack(int row) { if (row n) { res.add(buildBoard()); return; } for (int col 0; col n; col) { int diagIndex row - col n - 1; int antiDiagIndex row col; if (colUsed[col] || diagUsed[diagIndex] || antiDiagUsed[antiDiagIndex]) { continue; } queens[row] col; colUsed[col] true; diagUsed[diagIndex] true; antiDiagUsed[antiDiagIndex] true; backtrack(row 1); queens[row] -1; colUsed[col] false; diagUsed[diagIndex] false; antiDiagUsed[antiDiagIndex] false; } } private ListString buildBoard() { ListString board new ArrayList(); for (int row 0; row n; row) { char[] line new char[n]; Arrays.fill(line, .); line[queens[row]] Q; board.add(new String(line)); } return board; } }这份代码的核心思想就是用一个一维数组queens记录每行皇后的位置。buildBoard里每次新建一个char[]数组用Arrays.fill填充.再在皇后列号处改成Q最后转成字符串。这里新建数组的开销只在生成结果时发生对搜索过程没有任何影响。我实际运行时发现n 4 输出两组解n 8 输出 92 组解n 9 输出 352 组解跟已知数完全吻合。你可以用这个结果自查代码是否正确。4.2 Python 对比版与注意点Python 版本的代码结构几乎一样但有几个语言层面的注意点。class Solution: def solveNQueens(self, n: int) - List[List[str]]: self.n n self.queens [-1] * n self.col_used [False] * n self.diag_used [False] * (2 * n - 1) self.anti_diag_used [False] * (2 * n - 1) self.res [] self.backtrack(0) return self.res def backtrack(self, row: int) - None: if row self.n: self.res.append(self.build_board()) return for col in range(self.n): diag_index row - col self.n - 1 anti_diag_index row col if self.col_used[col] or self.diag_used[diag_index] or self.anti_diag_used[anti_diag_index]: continue self.queens[row] col self.col_used[col] True self.diag_used[diag_index] True self.anti_diag_used[anti_diag_index] True self.backtrack(row 1) self.queens[row] -1 self.col_used[col] False self.diag_used[diag_index] False self.anti_diag_used[anti_diag_index] False def build_board(self) - List[str]: board [] for row in range(self.n): line [.] * self.n line[self.queens[row]] Q board.append(.join(line)) return boardPython 版本需要注意两点第一如果你把queens、col_used等定义成__init__里的实例变量那么每次调用solveNQueens时都要重新初始化否则上一次调用留下的状态会污染本次结果。力扣的测试用例会多次调用同一个Solution实例的方法这一点必须小心。第二Python 的递归深度默认是 1000n 最大也就 9完全够用不需要额外设置sys.setrecursionlimit。4.3 复杂度分析与极限测试从理论上分析回溯算法的时间复杂度没有一个简单的闭式表达因为剪枝会大量减少搜索节点。但可以确定的是合法解的个数约等于 0.143^n 这个量级搜索过程中的节点数远小于 n 的阶乘。空间复杂度比较明确递归深度 O(n)加上三个布尔数组 O(n)所以整体是 O(n)。我在本机做了一组简单测试n 8 时 Java 版本的运行时间大概在 5ms 左右n 9 在 20ms 左右n 10 会明显上涨但依然能跑完。如果你觉得慢可以尝试把布尔数组换成整型位标记也就是位运算版本速度会有明显提升。不过笔试面试中 n 一般不会超过 9所以常规解法完全够用。这里也提醒一个容易忽略的性能细节buildBoard里用了char[]和new String(line)这比直接用字符串拼接要高效得多。如果用String的substring拼接比如..repeat(col) Q ..repeat(n - col - 1)在结果数量很多时会产生大量中间字符串拖慢运行速度。5. 常见问题与排查技巧实录5.1 写回溯死循环 / 结果为空很多人第一次写完程序跑起来要么陷入死循环要么结果为 0这时候先不要怀疑算法策略通常问题出在状态标记上。结果为空的第一嫌疑是“剪枝条件写反了”。我之前见过有人把冲突判断写成if (colUsed[col] diagUsed[diagIndex] antiDiagUsed[antiDiagIndex])意思变成了“三个方向同时被占用才跳过”这完全错了。正确的语义是三个方向任意一个被占用就不能放要用逻辑或连接。这个 bug 一旦出现几乎不会有任何解能通过但代码逻辑看起来又很合理排查起来要仔细看条件运算符。死循环的常见原因是递归终止条件写错。回溯的递归终止条件必须是row n因为行号从 0 开始递增当处理完第 n - 1 行后row 变为 n表示所有行都已经放完。如果你把条件写成row n - 1就收集结果会漏掉最后一行而且可能递归不到终止状态导致栈溢出。5.2 重复解问题N 皇后本身不容易产生重复解因为每一行只放一个皇后行的递增顺序天然保证了不会出现两个完全相同的摆放序列。但如果你修改了搜索策略比如先枚举列再枚举行可能会遇到重复问题。另外需要注意力扣对解的顺序有要求吗实际测试中只要你的解集合内容正确顺序不影响通过。你不需要对结果做额外排序回溯按行的自然顺序产生的输出本身就是有规律的。如果发现解的个数比标准答案多优先检查撤销步骤。想象一个场景递归到某一层时col_used[2] 在之前被标记为 true但递归返回后你没有恢复成 false。那么后续同层的其他分支在尝试第 2 列时会发现被占用于是跳过导致正常应该有的解丢失反过来如果某个标记被错误地提前清除会让本不该放的位置通过了检查生成非法解这种情况最容易在多解检查时暴露。5.3 位运算优化简介N 皇后问题还有一个很经典的进阶版用整型变量代替布尔数组做状态压缩。核心思路是用一个整数的二进制位表示某列是否被占用1 表示占用0 表示空闲。主对角线和副对角线也分别用一个整数表示每次递归时通过位运算计算当前行所有可行的列位置。代码片段大致是这样的def backtrack(row, cols, diag, anti_diag): if row n: res.append(...) return available ((1 n) - 1) ~(cols | diag | anti_diag) while available: pos available -available # 取出最低位的 1 col pos.bit_length() - 1 available ^ pos # 移除这个位置 backtrack(row 1, cols | pos, (diag | pos) 1, (anti_diag | pos) 1)这里每递归一层对角线的标记需要整体右移或左移一位因为下一行的对角线相对当前位置会偏移。这个技巧在 n 非常大时能显著提升速度但对没接触过位运算的同学来说理解成本有点高。我的建议是先把布尔数组版本写熟再尝试用位运算重写一次这样对二进制状态的理解会有质的提升。6. 实战心得刷题落地的经验6.1 从 N 皇后到其他回溯题的迁移N 皇后之所以值得花时间吃透是因为它练会了之后能直接迁移到一批“棋盘类搜索题”以及很多“组合/排列需去重”的题目。比如力扣的第 37 题解数独本质上是 N 皇后问题的扩展每一格要填写 1 到 9同时要满足行、列、九宫格三种约束。你如果能熟练写出 N 皇后的三个布尔数组维护方式那数独的约束检查也会很自然地想到用三个布尔二维数组来维护。再看力扣 hot100 里的全排列和组合总和它们的回溯框架几乎一样区别只是在“选择列表”和“剪枝条件”上做文章。全排列的撤销需要恢复“已使用”标记组合总和的剪枝需要排序后跳过重复元素。这些都是 N 皇后递归模型的不同表现形式。我经常跟刷题的朋友说与其把回溯题一道一道背下来不如把 N 皇后当成“母题”画出模板再把其他题目套进模板里修改“选择、约束、撤销”三要素。你在面试里遇到一个新的回溯题时先大声说出这三要素分别是什么思路就已经清晰一半了。6.2 刷题节奏与 debug 建议很多人刷 hot100 会按照题号顺序去刷但回溯专题我认为不一定要按顺序。我的建议是先做全排列再做组合总和然后做 N 皇后最后挑战解数独。N 皇后放在中间是因为它能串联起前面两题的“排列组合”思维同时对“冲突检查”提出了更高要求。把它当作一个阶段性的验收题来刷效果比盲目刷三遍要好得多。如果真的卡住了建议采用分步验证法。先别急着写完整代码把搜索过程打印出来看每当放置一个皇后就打印当前 queens 数组的内容。n 4 的规模很小你有足够时间观察每一步状态的变化。如果发现某一步撤销后状态没恢复立刻就能定位到问题。等代码逻辑正确后再把打印语句删掉提交力扣。我还习惯在本地准备一组标准结果作为回归测试样本。我最常用的三组样本是n 4 应该有 2 个解n 8 应该有 92 个解n 9 应该有 352 个解。只要这组数据通过代码的正确性就基本有了保障。根据我个人的刷题体会N 皇后这道题的精髓不在于它的难度而在于它能让你一次性理解回溯算法的本质。花一个晚上把这题彻底吃透后面再遇到排列、组合、子集、岛屿类搜索题时你的思路会顺畅特别多。做题过程中如果每次都是在状态标记上栽跟头也不用气馁多写几次就会形成肌肉记忆那个“放置—递归—撤销”的节奏感一上来后续解题速度会有肉眼可见的提升。