企业官网建设流程全解析

刷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皇后是按行递归，而不是按格子递归？

因为皇后攻击范围包括整行整列。如果按格子递归，你需要在每个格子判断它是否和前面的皇后冲突，会复杂很多。相反，“每一行只能放一个皇后”是问题的固有约束，所以直接把行号作为递归深度，每层只思考这一行放在第几列，是最自然的解法。

以n=4为例，搜索树大概是这样的思路：第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 为什么回溯能枚举所有解，而不是无限递归

有人会问：每次递归都从col=0开始遍历，为什么不会重复选择同一列？因为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。

这两个规律我建议你自己在草稿纸上验算一遍。比如n=4时，(0,0)和(2,2)是不是同一主对角线？(0,3)和(2,1)是不是同一副对角线？算完你会记得比任何口诀都牢。

3.3 三种标记方案的对比

我把常见的冲突判断方式整理成一张表，方便你在写代码前想清楚：

另一个常见的做法是每次放置时扫描前面所有已经放好的皇后，逐个判断是否共列、共斜线。这样确实不用额外的标记数组，但每次判断都是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 res

4.3 实测数据与适用场景

LeetCode上N皇后这题的官方n范围通常只到9，也就是说普通回溯版已经能通过。那位运算版是不是没必要？我的看法是，如果只是为了AC，普通版完全够用；但位运算版能让你在本地测试时明显感受到常数优化的威力。

我拿n=9测过，普通版解出352组答案大概要一两秒，位运算版快很多；当n到12时，解的数量变成14200，普通版会跑出明显卡顿感，位运算版依然能在一轮咖啡不太凉之前出结果。当然，时间和你本机环境关系很大，重点不是具体数字，而是位运算把“判断三个布尔数组”变成了“一条位运算指令”，在递归节点数量爆炸时，收益会被放大。

面试里我不建议一上来就写位运算版，因为容易写错，讲解成本也高。更好的策略是先用普通版讲清楚思路，如果面试官追问优化，再把位运算版本亮出来。这样既有清晰的逻辑，又有加分亮点。

5. 提交LeetCode时容易踩的模板陷阱与边界坑

5.1 n = 1 到 n = 3：边界值最容易漏

N皇后最容易被忽略的是小n特判。n=1时棋盘只有一格，答案应该是[["Q"]]；n=2和n=3没有合法解，返回空列表[]。

常规版代码其实不用特判，因为dfs会自然地处理：n=2时第0行无论放哪一列，第1行都会被冲突挡住，搜索树走到尽头也没法到达row==n，所以不会记录任何解；n=3也一样。但很多人会把递归出口写成if row > n而不是if row == n，这样会多算一层，导致n=1时进入错误状态。

我自己调试时有个习惯：每次写完N皇后，先跑n=1、n=2、n=3三个边界，再跑n=4确认答案是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，结果n=4跑到一半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的规律；接着写代码，写完以后主动说“n=4应该有两组解，我可以手动验证；n=2和n=3应该返回空”。这样一套动作下来，面试官看到的是你把问题从抽象到具体完整拆解了一遍。

复杂度部分也不要含糊。时间复杂度最坏是O(n!)，因为第一层有n种选择，第二层最多n-1种，第三层最多n-2种，但实际搜索时会因为剪枝提前收缩，所以通常会好于阶乘；空间复杂度来自递归深度和棋盘，递归深度O(n)，棋盘O(n^2)，合起来是O(n^2)。位运算版可以把棋盘省掉，额外空间降到O(n)，但前提是你真能把它讲明白。

我个人刷这道题最大的收获，不是记住了代码，而是后来遇到任何带“约束”的搜索题，都会先停下来在纸上画一棵搜索树，问自己三个问题：这棵树每一层代表什么选择？每个节点能不能剪枝？递归回来以后需要还原哪些状态？如果你也能养成这个习惯，N皇后这题就算真正刷透了。