刷LeetCode刷到第51题N皇后时我估计你已经不是第一次接触回溯了。这道题在热题100里的位置很特殊它不像爬楼梯那样几行代码收工也不像二叉树题有明确的遍历套路它需要你真的把递归当成一棵树来想象还得处理斜线冲突这种数学味很重的条件。很多人背了回溯模板一上来还是懵为什么行和列两个循环就能描述棋盘为什么两条对角线的判断一张表就能解决我准备从递归树开始推给出可AC的Python写法再讲位运算优化和提交时容易翻车的细节。无论你是准备面试想刷透回溯还是单纯想搞懂N皇后都应该能从中找到自己需要的东西。1. 为什么N皇后值得放在必刷清单第一梯队1.1 一个面试官视角的解读N皇后在LeetCode热题100里难度标的是困难但它并不是那种需要灵光一现才能想出来的题。它考察的是三项基本功递归入口怎么写、状态怎么恢复、冲突条件怎么用数学规律简化。这些能力恰好是很多候选人简历里写着“熟悉数据结构与算法”但实际一写代码就露馅的地方。很多面试官愿意拿它当一面题是因为它比单纯问“二叉树前序遍历”要立体得多。前序遍历那类题背过模板就能过N皇后却要求你把问题拆成“每行放一个棋子、每列只能有一个、斜线不能碰”三个约束。如果你能一边在白板上画搜索树一边解释剪枝基本就能证明你的递归功底是活的而不是刷题背下来的。1.2 它的解题收获可以迁移到什么题这道题刷透之后收益会辐射到很多地方。最直接的是N皇后II、数独求解、括号生成、组合总和这一类“约束满足型”题目。我自己的体会是N皇后是理解回溯算法的最佳训练场之一。因为它天然具备“路径-选择-结束条件”三个要素路径就是已经放置的皇后位置选择就是当前行可以放在哪一列结束条件就是所有n行都放完皇后。一旦你从这个角度理解它再去做数独时会发现只是把“每行每列”换成了“每宫每行每列”把皇后冲突换成了数字冲突思路完全一致。1.3 刷之前需要先掌握什么如果你是刚开始接触回溯我建议先别直接硬啃N皇后。先把全排列、子集、组合这三道基础题刷明白。它们能帮你建立两个关键概念递归的终止条件以及递归返回之后如何撤销上一次的选择。N皇后比全排列多出来的部分是棋盘坐标和对角线的数学关系。全排列只需要记录“当前已选哪些数字”N皇后则需要记录“当前哪些列被占、哪些对角线被占”。理解了这一点你就已经理解这道题的核心了。2. 从递归树出发逐行放置的主线思路2.1 搜索树怎么画先想清楚一个问题为什么N皇后是按行递归而不是按格子递归因为皇后攻击范围包括整行整列。如果按格子递归你需要在每个格子判断它是否和前面的皇后冲突会复杂很多。相反“每一行只能放一个皇后”是问题的固有约束所以直接把行号作为递归深度每层只思考这一行放在第几列是最自然的解法。以n4为例搜索树大概是这样的思路第0行尝试第0列剩下的皇后只能从第1行开始放第1行可行列会被第0行的皇后限制住比如第0列不能选、第1列也不能选剩下几个候选列继续递归。像这样一层层往下走直到某一行没有任何可放列就回退到上一行换下一列继续尝试。这里的“回退”就是回溯这个名字的由来。画这棵树的时候行号就是递归参数row列号就是循环内枚举的col。树的深度是n每一层的分支数是“当前还剩多少列可用”所以整体复杂度远小于n的n次方。2.2 最简解法的完整代码与逐行注释先给出最朴实、最容易理解的一版代码。这版不一定是最快的但一定是面试时你能讲得最清楚的。from typing import List class Solution: def solveNQueens(self, n: int) - List[List[str]]: res [] # 棋盘用二维字符数组后面再转成字符串 board [[.] * n for _ in range(n)] # 三个标记数组分别记录列、主对角线、副对角线是否被占用 cols [False] * n diag1 [False] * (2 * n - 1) # row col diag2 [False] * (2 * n - 1) # row - col n - 1 def dfs(row: int) - None: if row n: # 找到一组解把每一行拼成字符串 res.append([.join(r) for r in board]) return for col in range(n): d1 row col d2 row - col n - 1 if cols[col] or diag1[d1] or diag2[d2]: continue # 做选择放皇后并标记占用 cols[col] diag1[d1] diag2[d2] True board[row][col] Q # 进入下一行 dfs(row 1) # 撤销选择恢复现场 board[row][col] . cols[col] diag1[d1] diag2[d2] False dfs(0) return res这段代码的核心逻辑其实只有三件事判断当前列能不能放能放就占住位置递归下一行返回后释放位置。我把判断冲突放在进入递归之前也就是“剪枝”。剪枝做得越早搜索树越瘦程序跑得越快。2.3 为什么回溯能枚举所有解而不是无限递归有人会问每次递归都从col0开始遍历为什么不会重复选择同一列因为cols数组在占用后会标记True递归返回后虽然恢复False但下一次选择发生在不同的row层前面行的皇后位置已经确定所以不会产生无限循环。回溯和普通DFS最大的区别就在于“恢复现场”。你可以把棋盘想象成试衣间进入递归之前你试了一件衣服占了位置递归返回之后你必须把衣服放回原位否则下一个选择会被这件“还留在试衣间”的衣服干扰。很多错误回溯代码漏掉恢复操作结果就是搜索过程中状态被污染要么少解要么得到一堆错误的棋盘。这个坑我后面会专门讲。3. 冲突判断里的数学两条对角线的高频出错点3.1 同一列最简单但别放错数组列冲突很好理解每一列只能有一个皇后。我们用一维布尔数组cols记录当在row行、col列放皇后时把cols[col]标记为True之后任何一行都不能再选这一列。这个逻辑几乎不会写错真正容易错的是对角线。3.2 主对角线和副对角线数字不变的规律先看主对角线也就是从左上到右下的斜线。棋盘上任意一个格子(row, col)它所在的主对角线可以用row - col唯一标识。比如(0,0)和(1,1)都在同一条主对角线上它们的row - col都等于0而(0,2)的row - col等于-2。为了把负下标变成非负我们统一加偏移量n - 1所以主对角线标记数组的下标是row - col n - 1。再看副对角线也就是从右上到左下的斜线。这条线上的所有格子满足row col是同一个常数。比如(0,3)、(1,2)、(2,1)、(3,0)的row col都等于3。row col的最小值是0最大值是2n - 2所以副对角线标记数组的长度是2n - 1下标直接用row col。这两个规律我建议你自己在草稿纸上验算一遍。比如n4时(0,0)和(2,2)是不是同一主对角线(0,3)和(2,1)是不是同一副对角线算完你会记得比任何口诀都牢。3.3 三种标记方案的对比我把常见的冲突判断方式整理成一张表方便你在写代码前想清楚冲突类型数学条件数据表示下标公式同列col相同一维数组长度ncol主对角线row - col相同一维数组长度2n-1row - col n - 1副对角线row col相同一维数组长度2n-1row col另一个常见的做法是每次放置时扫描前面所有已经放好的皇后逐个判断是否共列、共斜线。这样确实不用额外的标记数组但每次判断都是O(n)整体效率明显低。数组标记法用O(1)时间判断冲突代价只是多开两个长度2n-1的布尔数组。对于N皇后这个规模这点空间完全值得。4. 能用位运算打败时间吗优化版本的真实收益4.1 位运算版到底在优化什么常规解法用三个布尔数组记录状态每次判断冲突是常数时间已经很快了。但如果n变大到10、12、13搜索节点数以指数级增长常数时间的判断次数也随之暴增。位运算版本的核心思想是把三个布尔数组压缩成三个整数整数中的每一位表示某列或某条对角线是否被占用。这样可用位置的判断、标记和恢复都可以通过位操作一次完成。更重要的是布尔数组版每次循环需要做三次索引查找和三次布尔判断位运算版则是先把所有被占用的列、对角线合并成一个整数取反后一次性得到所有“当前还能放的列”。这个“取可用位置”的动作从for循环里逐个判断变成了一个位运算表达式。4.2 四个位运算操作逐个拆解位运算版代码不长但没有基础的话确实容易看不懂。我拆开讲。首先是可用位置的计算available full ~(cols | diag1 | diag2)这里full是低n位全为1的整数类似n个空位的掩码。cols | diag1 | diag2把三个占用状态合并任何一位为1都代表这个位置不能再放皇后。取反后原来为0的位置变成1也就是可用位置。为什么必须full ~(...)因为Python的~是对无限位取反如果不限制在n位内会多出一堆高位的1下一层的判断就全乱了。这一条是Python写位运算版最容易踩的坑。然后是取一个可用列pos available -available这是lowbit技巧取出available中最右侧的一个1也就是挑一个可用的列来尝试。再把它从可用集合里移除available ^ pos在available中pos所代表的那一位本来就是1异或之后变0其他的位不变。这里也可以写成available - pos因为pos是available中的一个1不存在借位问题。最后是递归传参也是最需要理解的dfs(row 1, cols | pos, (diag1 | pos) 1, (diag2 | pos) 1)当前行放了皇后下一行往下走时主对角线的影响整体左移一列副对角线的影响整体右移一列。这就是为什么diag1要左移、diag2要右移。左移或右移后可能会出现超出棋盘范围的1但由于下一层计算available时又用full ~(...)裁剪了多出来的高位不会影响结果。完整代码是这样的from typing import List class Solution: def solveNQueens(self, n: int) - List[List[str]]: res [] board [[.] * n for _ in range(n)] full (1 n) - 1 def dfs(row: int, cols: int, diag1: int, diag2: int) - None: if row n: res.append([.join(r) for r in board]) return available full ~(cols | diag1 | diag2) while available: pos available -available available ^ pos col pos.bit_length() - 1 board[row][col] Q dfs(row 1, cols | pos, (diag1 | pos) 1, (diag2 | pos) 1) board[row][col] . dfs(0, 0, 0, 0) return res4.3 实测数据与适用场景LeetCode上N皇后这题的官方n范围通常只到9也就是说普通回溯版已经能通过。那位运算版是不是没必要我的看法是如果只是为了AC普通版完全够用但位运算版能让你在本地测试时明显感受到常数优化的威力。我拿n9测过普通版解出352组答案大概要一两秒位运算版快很多当n到12时解的数量变成14200普通版会跑出明显卡顿感位运算版依然能在一轮咖啡不太凉之前出结果。当然时间和你本机环境关系很大重点不是具体数字而是位运算把“判断三个布尔数组”变成了“一条位运算指令”在递归节点数量爆炸时收益会被放大。面试里我不建议一上来就写位运算版因为容易写错讲解成本也高。更好的策略是先用普通版讲清楚思路如果面试官追问优化再把位运算版本亮出来。这样既有清晰的逻辑又有加分亮点。5. 提交LeetCode时容易踩的模板陷阱与边界坑5.1 n 1 到 n 3边界值最容易漏N皇后最容易被忽略的是小n特判。n1时棋盘只有一格答案应该是[[Q]]n2和n3没有合法解返回空列表[]。常规版代码其实不用特判因为dfs会自然地处理n2时第0行无论放哪一列第1行都会被冲突挡住搜索树走到尽头也没法到达rown所以不会记录任何解n3也一样。但很多人会把递归出口写成if row n而不是if row n这样会多算一层导致n1时进入错误状态。我自己调试时有个习惯每次写完N皇后先跑n1、n2、n3三个边界再跑n4确认答案是2组然后才去提交。这三个case能过滤掉八成低级错误。5.2 复制棋盘还是复制引用这是N皇后题里最典型的列表引用陷阱。如果你在记录答案时写成res.append(board)那么恭喜你你得到的不太可能是答案而是一堆全是“.”的空棋盘。因为res存的是board这个列表的引用后面回溯时会继续修改board把放好的Q全撤销掉。最终res里的每个元素都指向同一个被清空的棋盘。正确做法是复制一份快照常见两种res.append([.join(row) for row in board])或者res.append([row[:] for row in board])第一种把每行字符数组转成字符串天然创建了新对象也刚好符合题目的输出格式第二种是浅拷贝棋盘行。我推荐第一种少一次转换写起来也顺。还有一个相关的坑初始化棋盘时要用[[.] * n for _ in range(n)]不要用[[.] * n] * n。后者会让所有行指向同一个列表改一行等于改所有行代码跑起来画面会很“壮观”。5.3 我提交时真实踩过的三个坑第一个坑发生在标记数组长度上。主对角线和副对角线的下标范围都是0到2n-2数组长度必须是2n-1。我第一次写成n结果n4跑到一半IndexError。排查起来也不难在冲突判断前打印d1、d2的最大值就能发现它们早就超出数组边界了。第二个坑是恢复字段没做干净。我只恢复了cols和diag数组忘了把board[row][col]从Q恢复成.。结果搜索过程虽然能继续但已记录的解没有受影响可最终结果里出现了一些本不该存在的Q也就是没有把撤销动作做完整。回溯算法的原则很简单做过什么选择递归回来后就必须原样撤销。漏掉任何一个字段状态就不一致。第三个坑是位运算版运算符优先级。(diag1 | pos) 1和diag1 | (pos 1)是完全不同的含义。我第一次写成了后一种递归传参时对角线状态完全错乱跑出来的解怎么数都不对。所以位运算版里的括号一定要写清楚该加括号的地方一个都不能省。还有一个类级别的坑如果Solution类里有全局变量或类变量作为结果集多次调用同一个实例时结果会不断累加。稳妥做法是像前面的代码一样把结果集放在solveNQueens内部或者dfs的闭包里每次调用都是全新状态。6. 从N皇后到约束满足类题目的通用框架6.1 N皇后II从构造解到只计数N皇后II是LeetCode第52题要求和N皇后一样但不返回具体棋盘只返回解的数量。改造思路很简单既然不在乎是哪种摆法就不需要维护board数组也不需要把结果存下来只要在dfs到达最后一行时给计数器加1。class Solution: def totalNQueens(self, n: int) - int: cols [False] * n diag1 [False] * (2 * n - 1) diag2 [False] * (2 * n - 1) def dfs(row: int) - int: if row n: return 1 total 0 for col in range(n): d1 row col d2 row - col n - 1 if cols[col] or diag1[d1] or diag2[d2]: continue cols[col] diag1[d1] diag2[d2] True total dfs(row 1) cols[col] diag1[d1] diag2[d2] False return total return dfs(0)去掉了棋盘赋值和结果复制之后递归函数的返回值可以直接累加代码反而更清爽。这提醒我们一个优化思路当题目只关心数量、不关心具体方案时能少维护什么就少维护什么。6.2 数独、八皇后变种与回溯模板如果你把N皇后吃透再看数独求解会很容易。数独本质上也是约束满足问题每行每列每宫都只能出现1到9每个空格尝试一个数字递归填下一个空格冲突就剪枝填完就记录解。和N皇后唯一的不同是N皇后一行只放一个皇后数独每个空格都可能填多个数字需要更多层循环和更复杂的约束检查。我也遇到很多变种题比如只给定某些位置已放置皇后问还有多少种合法摆法或者把皇后换成国际象棋中的“国王”“骑士”攻击规则变了但回溯框架完全一样。处理这些变种时最好的方法不是死记题解而是先画搜索树想清楚当前层代表哪个决策选择列表是什么约束条件是什么。N皇后练的就是这套思考方式。我习惯把回溯框架概括成四句话进入递归前判断能否剪枝做选择并更新状态进入下一层递归返回后撤销状态。这个框架遇到任何约束满足题都能快速定位到自己卡在哪一步。6.3 面试现场怎么讲这道题才加分根据我自己面试和做面试官的经验N皇后这道题讲得好不好关键不在于代码一次写对而在于你愿不愿意展现思考过程。我会建议这样说先确认n的范围因为n的上限直接决定能不能跑位运算优化然后说“我打算按行枚举用三个布尔数组分别维护列和两条对角线的占用状态”顺手在纸上画一条对角线说明row - col和row col的规律接着写代码写完以后主动说“n4应该有两组解我可以手动验证n2和n3应该返回空”。这样一套动作下来面试官看到的是你把问题从抽象到具体完整拆解了一遍。复杂度部分也不要含糊。时间复杂度最坏是O(n!)因为第一层有n种选择第二层最多n-1种第三层最多n-2种但实际搜索时会因为剪枝提前收缩所以通常会好于阶乘空间复杂度来自递归深度和棋盘递归深度O(n)棋盘O(n^2)合起来是O(n^2)。位运算版可以把棋盘省掉额外空间降到O(n)但前提是你真能把它讲明白。我个人刷这道题最大的收获不是记住了代码而是后来遇到任何带“约束”的搜索题都会先停下来在纸上画一棵搜索树问自己三个问题这棵树每一层代表什么选择每个节点能不能剪枝递归回来以后需要还原哪些状态如果你也能养成这个习惯N皇后这题就算真正刷透了。