作为一个刷了LeetCode热题100的人，我可以负责任地说，第51题N皇后是整张清单里“看起来吓人、做起来过瘾”的一道题。它不涉及复杂的数据结构，也不考什么冷门算法，真正考验的是你对递归和回溯的理解是否到位。很多人在这个题上卡住，不是因为代码写不出来，而是因为压根没想明白“怎么表达皇后的攻击范围”“怎么在棋盘上合法落子”。这篇就把这个问题的全部门道拆开揉碎讲清楚，从暴力思路到标准回溯，再到位运算优化，一次说透。
1. 题目本身到底在问什么
N皇后问题的描述非常简练：在一个 n x n 的棋盘上放置 n 个皇后，使得它们两两之间不能互相攻击。国际象棋里皇后的攻击方式是横着、竖着、斜着都能走，不限格数，所以棋盘上任意两个皇后不能出现在同一行、同一列、同一条对角线上。
LeetCode 51这道题要求你返回所有不同的合法放置方案，输出格式是字符串列表，每一行用'.'表示空位、'Q'表示皇后。
听起来有点像数独，但比数独更纯粹，因为它没有一个提前填好的“已知数”，所有格子都是空的，完全靠摆放规则来约束。
这道题被收录进LeetCode热题100，几乎是必然的。回溯算法是面试里的高频考点，而N皇后又是回溯算法里最经典的“代表题型”，跟全排列、组合总和、子集这些题一样，属于刷题绕不开的核心题目。面试官也爱出这道题，因为它短时间内能考察你对递归树的构建、状态的记录、剪枝的意识、以及时间复杂度分析的能力，一道题能问出很多东西。
题目本身不要求你打印棋盘，只要求返回所有方案，所以最终结果是一个二维列表。很多初学者会在这里犯迷糊，返回值拿捏不准。先把这个确认好，后面写代码就需要时刻围绕这个目标组织数据。
注意：LeetCode上的N皇后通常有两个版本，第51题是“返回所有方案”，第52题是“返回方案总数”。本文以51题为准，但最后会提一句怎么改一行代码去适配52题。
2. 核心思路：为什么是回溯而不是别的
2.1 暴力枚举的复杂度有多恐怖
先想想最朴素的思路。要在 n x n 的棋盘上选 n 个格子放皇后，不考虑任何规则，那就是从 n^2 个位置里挑 n 个的组合数。比如 n=8 的时候，C(64, 8) 大约是 44亿，这已经很大了。再加上检查合法性，复杂度根本没法看。
所以必须利用规则来大幅缩小搜索空间。注意第 51 题默认的 n 最大是 9，但即便只有 9，暴力硬搜也一样会超时，必须用聪明的方法。
2.2 逐步固定行：把二维问题降维
皇后的攻击规则里有一条很关键：同一行只能放一个皇后。这个规则直接给了一个搜索顺序上的突破口。我们可以按行来处理，从第 0 行开始，每一行只尝试放置一个皇后，然后递归进入下一行。
这样做有一个巨大的好处：搜索树的层数就是棋盘的行数，每一层的分支数就是当前行可尝试的列数。我们不再需要同时考虑“行”这个维度的冲突，因为按行递归天然保证了不会有同行的皇后。
这就像你整理一个会议室的座位表，与其同时安排所有人的座位，不如一行一行排，每一排只决定一个座位，排完一行再去下一行。问题瞬间从“排列组合”变成了“逐行决策”。
2.3 列出所有冲突条件
按行递归之后，搜索过程中要随时判断某个位置能不能放皇后。当我们要在第 row 行、第 col 列放皇后时，需要考虑三种冲突：
- 列冲突：当前列是否已经有皇后
- 主对角线冲突：从左上到右下的那条对角线上是否已经有皇后
- 副对角线冲突：从右上到左下的那条对角线上是否已经有皇后
关键点在于：如何用坐标系把这两条对角线表示出来。
对于棋盘上的每个格子 (row, col)，主对角线上的所有格子都满足row - col是一个固定值，副对角线上的所有格子都满足row + col是一个固定值。这两条性质是整个N皇后问题里最核心的数学基础，理解了它，代码就顺理成章了。
打个比方，你站在一个方阵里，所有和你在同一条“右下方向”斜线上的队友，他们的“行号减列号”都等于同一个数。所有和你在同一条“左下方向”斜线上的队友，他们的“行号加列号”都等于同一个数。这就是判断对角线的本质。
2.4 回溯的框架：尝试、递归、撤销
回溯算法的本质是深度优先搜索一棵决策树。每到一个决策点，列出所有可能的选择，挨个尝试，一旦发现某个选择走不通，就退回到上一个抉择点，换下一条路继续走。
在N皇后里，决策树是这样构建的：
- 第 0 行有 n 列可选，尝试在第 col 列放皇后
- 记录这个选择对列、主对角线、副对角线的影响
- 递归进入第 1 行，再尝试放第二个皇后
- 如果中间某一行没有任何一个位置可以放皇后，直接回退
- 当递归深度到达第 n 行时，说明已经放完了 n 个皇后，记录此时棋盘的状态
这个“记录影响、递归、撤销影响”的三步操作，是所有回溯题的通用模板。你只要把模板记住，换成不同的题目条件，就能解决全排列、组合、子集、数独等一系列问题。
3. 标准回溯实现：从零写出一份能跑的代码
3.1 用三个数组记录冲突状态
明确了按行递归的思路之后，接下来就是选择数据结构来记录冲突。
对于列冲突，一个长度为 n 的布尔数组col_used就够用了。col_used[c]为 True 时，说明第 c 列已经有皇后。
对于主对角线，我们需要一个数组来标记“行号减列号对应的那条对角线”。row - col的取值范围是-(n-1)到(n-1)，为了不出现负数下标，统一加上一个偏移量n-1，也就是用row - col + n - 1作为下标。所以主对角线数组的长度是2*n - 1，用diag1[idx]来标记。
对于副对角线，用row + col来标识。它的取值范围是0到2n-2，天然非负，不需要偏移，直接作为下标就能用。副对角线数组的长度同样是2*n - 1，用diag2[idx]来标记。
很多新手在这一步会混淆：为什么主对角线要加偏移，副对角线不用？你动手列几个格子验证一下就明白了。比如 (0,0) 和 (1,1) 是同一条主对角线，row - col 都等于 0；但 (0,7) 这条主对角线 row - col 就是 -7，不加偏移就变成负数下标了。而副对角线 (0,7) 和 (1,6) 的 row + col 都等于 7，永远大于等于 0，自然不用偏移。
3.2 Python 参考实现
老规矩，先上可以直接跑的完整代码，再逐段讲。
def solveNQueens(n: int): # 记录每一行皇后放在哪一列，row_place[row] = col row_place = [-1] * n # 列是否已被占用 col_used = [False] * n # 主对角线是否已被占用，下标范围 0 ~ 2n-2 diag1 = [False] * (2 * n - 1) # 副对角线是否已被占用 diag2 = [False] * (2 * n - 1) res = [] def dfs(row: int): # 所有行都放完了，构造结果 if row == n: board = [] for c in row_place: line = ['.'] * n line[c] = 'Q' board.append(''.join(line)) res.append(board) return for col in range(n): d1 = row - col + n - 1 d2 = row + col if col_used[col] or diag1[d1] or diag2[d2]: continue # 尝试放置皇后 row_place[row] = col col_used[col] = True diag1[d1] = True diag2[d2] = True # 递归进入下一行 dfs(row + 1) # 回溯：撤销刚才的放置 row_place[row] = -1 col_used[col] = False diag1[d1] = False diag2[d2] = False dfs(0) return res3.3 逐段理解这段代码
row_place数组是核心。它记录的是每一行的皇后放在第几列，这样在递归到终点时，我们才能根据它来构造整个棋盘。这里用一维数组就完成了对所有皇后位置的记录，不需要维护一个二维的棋盘状态。
dfs(row)表示当前正在处理第 row 行。当row == n时，说明从第 0 行到第 n-1 行都已经成功放置了皇后，这就是一个合法解。构造棋盘时，每一行先生成 n 个'.'，再把对应列改成'Q'，然后拼接成字符串。
真正放皇后的循环里，先计算这个位置对应的两条对角线编号，然后做检查。只要列、主对角线、副对角线任意一个已经被占用，就直接跳过。这三个检查是并行的，没有优先级，只要有一个冲突就不能放。
检查通过之后，先把状态标记为占用，然后递归下一行。递归返回之后再把状态恢复原样，这一步就是“回溯”二字的来源。如果不恢复，之前尝试过的列会影响后续其他方案的选择，导致结果错误或者漏解。
提醒一下：递归结束后一定要撤销状态标记。我见过不少人第一次写回溯时忘记撤销，结果只得到一个方案，或者连方案都没有，因为所有列都被“假占用”了。
3.4 复杂度分析要会算也要会说
时间复杂度的精确计算是 O(n!)，但严格说起来不完全等于 n!。第 0 行有 n 个位置可以选，第 1 行最多有 n-1 个位置（去掉同一列），第 2 行最多 n-2 个位置……所以最坏情况下需要尝试的次数是n * (n-1) * (n-2) * ... * 1 = n!。再加上剪枝提前排除对角线冲突，实际运行次数比 n! 还要少。
空间复杂度方面，三个标记数组加上row_place数组，长度都是 O(n) 级别的，再加上递归调用栈深度是 n，所以总体空间复杂度是 O(n)。结果数组res不计入算法的空间复杂度，因为它属于输出部分。
面试时如果被问到这个复杂度，直接说“时间复杂度在最坏情况下是 O(n!)，但实际因为有对角线剪枝会远小于这个上界，空间复杂度 O(n)”就足够了。
4. 进阶优化：位运算剪枝的写法与原理
4.1 为什么要用位运算
LeetCode 51 的 n 最大到 9，用布尔数组的写法已经能轻松通过，运行时间一般不到 100ms。那为什么还要学位运算版本？两个原因。第一，位运算版本能让你对“状态压缩”有更直观的理解，这个技巧在状态压缩DP、图论算法里都会用到。第二，面试聊到优化的时候，能主动写出一份位运算版本，是一个明显的加分项。
位运算做法的核心思想非常简单：用一个整数的二进制位来表示“哪些列可以放皇后”。某一位为 1 表示可以放，为 0 表示不可用。列、主对角线、副对角线各用一个整数来维护，每次取三者可用位置的交集，就能快速找到当前行所有合法的列。
4.2 三个掩码的含义
对于第 row 行，我们维护三个整数：
col_mask：某一位为 1 表示该列已经被占用，不能再放diag1_mask：某一位为 1 表示该主对角线已经被占用，这里的“位”对应的不是棋盘列，而是对角线编号diag2_mask：某一位为 1 表示该副对角线已经被占用
每次进入新的一行时，diag1_mask需要左移一位，diag2_mask需要右移一位。为什么？因为主对角线索引是row - col + n - 1，当 row 增加 1 时，如果某个皇后的影响要投影到当前行，对应的列位置会向右移动一格，反映到位掩码上就是左移。副对角线索引是row + col，row 增加 1 时影响位置向左移动，也就是右移。
这个左移右移是位运算版N皇后里最容易让人困惑的地方，我刚开始学的时候也绕了很久。用一个具体例子来理解：假设 (0,0) 位置放了一个皇后，它所在的主对角线在 row=1 时对应的是列 1，在 row=2 时对应列 2。所以从第 0 行到第 1 行，这个对角线的影响从 bit0 变成了 bit1，也就是左移了 1 位。副对角线同理，只不过投影方向相反，所以是右移。
4.3 Python 位运算实现
def solveNQueens(n: int): res = [] # 存放每行皇后所在列，用于最终构造棋盘 queens = [-1] * n def dfs(row: int, col_mask: int, diag1_mask: int, diag2_mask: int): if row == n: board = [] for c in queens: line = ['.'] * n line[c] = 'Q' board.append(''.join(line)) res.append(board) return # 当前行所有可用的列位置 # 三个掩码的并集是“不可用”的位置，取反后与全1掩码做与运算 available = ((1 << n) - 1) & ~(col_mask | diag1_mask | diag2_mask) while available: # 取出最低位的 1 pos = available & (-available) # 将该位从 available 中移除 available &= available - 1 # 计算出 pos 对应的列号 col = bin(pos - 1).count('1') if pos else 0 queens[row] = col # 更新三个掩码 # diag1 左移：主对角线投影到下一行时右移一列，对应二进制左移一位 # diag2 右移：副对角线投影到下一行时左移一列，对应二进制右移一位 dfs( row + 1, col_mask | pos, (diag1_mask | pos) << 1, (diag2_mask | pos) >> 1, ) # 回溯时不需要显式恢复，因为当前行的掩码是通过参数传递的 queens[row] = -1 dfs(0, 0, 0, 0) return res这段代码里有几个小细节要解释一下。
available = ((1 << n) - 1) & ~(col_mask | diag1_mask | diag2_mask)这一行，是位运算版本的核心。col_mask | diag1_mask | diag2_mask得到所有“不可用”的位置，~按位取反后，原来为 0 的位变成 1，表示可用。但 Python 的~会把所有高位都变成 1，所以要用(1 << n) - 1截断到 n 位，只保留低 n 位。
pos = available & (-available)是取出最低位 1 的经典技巧。-available是 available 的补码形式，二者按位与之后，得到的结果只有最低位的那个 1 还保留着，其余位都是 0。这是位运算里非常常用的技巧，建议直接记住。
available &= available - 1的作用是把最低位的 1 清零。这行配合上一行，实现了“依次取出每个可用位置”的目的。因为我们在同一个 available 副本上操作，所以哪怕 while 循环里直接把 available 改了，也不影响后续回溯，这正是位运算版比数组版更简洁的原因之一。
col = bin(pos - 1).count('1')这行是为了把 bit 位置转换成列号。位掩码的第 i 位为 1，对应列号就是 i。因为 pos 只有一个 1 位，pos - 1 之后这一位右边的所有位都变成了 1，统计这些 1 的个数，就等于这一位原来的位置。例如 pos = 8（二进制 1000），pos - 1 = 7（二进制 0111），里面 1 的个数是 3，所以 pos 对应的是第 3 列。这个办法在 Python 里比较简单直接，面试时也可以用一个循环去找位位置，但这样写更简洁。
注意：
bin(pos-1).count('1')这个方法依赖 Python 语言的整数二进制特性，在 n 很小的情况下完全没问题。如果你追求更快的性能，可以预先维护一个字典，把 1 << i 映射到 i，查询时 O(1) 就能拿到列号。
4.4 位运算版本为什么不用显式回溯
你可能已经注意到了，位运算版本的递归函数把三个掩码作为参数传递，而不是像数组版本那样在递归前后做“标记、清除”。这是因为整数的按位或和移位操作都不会修改原变量，每次递归传入的是新计算出来的值，天然不会影响上一层状态。
打个比方，数组版本是“在一块白板上画一笔，画完再擦掉”，位运算版本是“每次递归都递过去一张新照片，拍照时把上一张照片里的内容叠加上去”。后者不需要“擦除”动作，因为原照片根本没有被修改。
这也是位运算在回溯题中的一个优势，它不是必须的，但能帮你减少出错的可能。你少写一行撤销代码，就少一个忘记撤销的隐患。
5. 实际运行、调试技巧与常见问题
5.1 小规模验证
写好代码之后，强烈建议先用 n=4 测试。4 皇后问题只有两个解，如果代码输出的结果数量和内容都对，那基本逻辑就稳了。
n=4 的两个解是：
.Q.. ...Q Q... ..Q.和
..Q. Q... ...Q .Q..你可以手动在草稿纸上画一画这两个棋盘，确认任意两个皇后都不在同一行、同一列、同一条对角线上，然后对照程序输出。这个验证过程能帮你发现很多隐性问题，尤其是对角线索引算错的情况。
5.2 输出格式的坑
LeetCode 要求返回的是List[List[str]]，每一行是一个字符串，里面只有'.'和'Q'。不要在中间把整行用列表存起来然后忘记 join，也不要画蛇添足在字符串里加空格。很多人提交报错不是算法问题，而是格式问题，返回的列表长得跟预期不一样。
构造棋盘时要注意，先创建一个全是'.'的列表，再把对应列改成'Q'。如果你的row_place记录的是[col0, col1, ...]，那就按行遍历它，依次生成字符串。
5.3 常见报错与排查思路
第一，递归没有退出条件，导致无限递归。检查dfs函数开头是否写了if row == n: return。漏掉这一行，程序会直接越界访问数组，报 IndexError。
第二，对角线索引越界。主对角线的偏移量容易写错，row - col + n - 1里的n-1不能少。如果不加偏移，row=0 且 col=n-1 时，row - col 就是负数。
第三，忘了撤销状态。如果输出的解数量偏多，多半是撤销没做干净；如果解数量偏少甚至为 0，也可能是撤销时机不对。建议在递归调用前后对称地写“标记”和“撤销”代码，一眼就能检查出来。
第四，位运算版本里available的高位问题。Python 整数长度不固定，如果不加((1 << n) - 1)做掩码截断，取反后高位全是 1，会导致 available 里出现一堆无效位，递归时把皇后放到棋盘外。
5.4 递归深度与性能的平衡
n 最大到 9，递归深度最深也就 9 层，完全不用担心 Python 的默认递归限制。但如果哪天你把 n 改得很大，比如 20 以上，数组版本就会很吃力，位运算版本也会明显变慢，因为 N 皇后问题的解空间本身就在快速膨胀。
LeetCode 的测试数据里 n 最大只到 9，所以不要过度优化。把数组版本写对、写清楚，比执着于位运算更实在。在面试场景中，我更建议先写数组版本，把思路讲清楚，然后提一句“还可以用位运算优化到 O(n) 空间且减少常数开销”，如果面试官追问，再写位运算版本。
5.5 一句代码适配第 52 题
第 52 题 N皇后II 只要求返回方案总数，不要求返回棋盘。最简单的改法是在找到解时，不构造棋盘，而是用一个计数器self.count += 1。或者沿用上面的代码，直接return len(solveNQueens(n))，虽然多了一些构造棋盘的开销，但对于 n=9 来说完全无压力。
6. 我对这道题的实操体会与扩展思路
N皇后这道题刷完之后，我对回溯的理解上了一个台阶。以前写全排列、组合总和的时候，总感觉回溯是个套路，背模板就行。但做完N皇后，我才真正理解了“状态”是怎么回事，知道一个问题的解空间长什么样，知道剪枝在哪个环节发挥作用。
我推荐按照这个顺序去练回溯相关的题目：先做全排列，再做组合总和，再做N皇后，最后做数独。全排列让你理解交换和撤销的最基础操作，组合总和让你学会剪枝，N皇后让你学会多维度的状态压缩，数独则是所有这些技巧的综合应用。
还有一个很实用的扩展思路：学会画决策树。第 51 题做完之后，你可以用 n=4 在纸上把整棵递归树画出来，标注哪些分支被剪掉了、为什么被剪掉。这一步做完，你对回溯的理解会非常扎实，以后再遇到类似题目，一眼就能识别出它的决策树长什么样。
如果想把代码写得更有工程感，可以把棋盘本身的绘制封装成一个函数，把冲突检测也单独提炼出来，这样代码结构更清晰，也方便扩展成其他变种题。比如你可以自己试着写一版“k 皇后”或者“带障碍物的皇后问题”，思路都是这套。
我在实际调试中发现一个特别实用的小窍门：当你怀疑自己的对角线索引写错了，不用去读代码，直接写一个 n=4 的测试用例，把每次递归时 row、col、d1、d2 的值全部打印出来，对照手画的棋盘逐一核对。这个排查速度比盯着代码猜快得多。调试回溯类算法，打印输出永远是第一利器。
最后送大家一个刷题习惯：每次提交通过之后，不要急着做下一题，花几分钟想一下能不能优化、能不能变形、能不能和之前做过的题联系起来。LeetCode热题100的价值不在于做完这一百道题，而在于通过这一百道题建立一个稳固的算法思维框架，N皇后就是框架里很重要的一块砖。
