51. N 皇后 (Hard)
专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/n-queens/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行、同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n x n 的棋盘上，并且使皇后彼此之间不能互相攻击。
给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
题目详细分析
数据范围含义：
n <= 9：回溯搜索空间为 n!（每行选一列，且不能同列和对角线），最坏 9! = 362880，完全可接受。
核心约束——三个不能攻击条件：
- 不能同列：任意两个皇后不能在同一列。
- 不能同主对角线：主对角线特征
row - col为常数。 - 不能同副对角线：副对角线特征
row + col为常数。
问题本质：
- 由于每行只能放一个皇后（否则同行攻击），问题转化为：在 n 行中，每行选一个列位置，使得所有选择的 (row, col) 满足列不重复、对角线不重复。
- 这实际上是全排列的加强版——在排列的基础上增加了对角线约束。
小白版直白理解
就像在 chess 棋盘上放 n 个”王后”，要求她们不能互相”吃”到对方。王后可以横着走、竖着走、斜着走，所以在同一行、同一列、同一斜线上都不能有两个王后。
你可以这样想：因为一行只能放一个王后，所以问题就变成了”第一行放哪一列，第二行放哪一列……”每行选一列，并且不能和之前放的王后在同一列或同一斜线上。
n=4 的一种摆法：
. Q . .
. . . Q
Q . . .
. . Q .
检查：每行一个 Q，每列一个 Q，主对角线（左上-右下）都没有冲突，副对角线（右上-左下）也都没有冲突。
解题思路
思路一：回溯 + 列/对角线的集合标记（推荐）
核心思想： 逐行放置皇后。用三个集合分别记录”已被占用的列”、“已被占用的主对角线（row - col）”、“已被占用的副对角线（row + col）“。每行在可选列中选择，放置后递归下一行。
决策树可视化（n=4 时逐行放置）：
第0行: 0'Q' 1'Q' 2'Q' 3'Q'
/ / \ \
第1行: 2,3都行 0,3可行 0,1可行 0,2都行
... ... ... ...
对角线特征解释：
- 主对角线（左上→右下）：
row - col为常数。同一主对角线上: (0,0)→(1,1)→(2,2): row-col=0 (0,1)→(1,2)→(2,3): row-col=-1 - 副对角线（右上→左下）：
row + col为常数。同一副对角线上: (0,3)→(1,2)→(2,1): row+col=3 (0,2)→(1,1)→(2,0): row+col=2
def solveNQueens(n):
res = []
cols = set() # 已被占用的列
diag1 = set() # 已被占用的主对角线 (row - col)
diag2 = set() # 已被占用的副对角线 (row + col)
def backtrack(row, path):
# 所有行都放置完毕，记录结果
if row == n:
res.append([''.join(r) for r in path])
return
for col in range(n):
# 检查是否有冲突
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# 做选择
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# 构建当前行的棋盘字符串
row_str = ['Q' if c == col else '.' for c in range(n)]
path.append(row_str)
backtrack(row + 1, path) # 递归下一行
# 撤销选择
path.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0, [])
return res思路二：利用数组代替集合（位运算优化版）
核心思想： 用三个数组代替集合，通过位运算加速冲突检查。适合 n 较大或追求极致性能的场景。
def solveNQueens(n):
res = []
cols = [False] * n
diag1 = [False] * (2 * n - 1) # row - col 范围: -(n-1) 到 (n-1)
diag2 = [False] * (2 * n - 1) # row + col 范围: 0 到 2n-2
def backtrack(row, path):
if row == n:
res.append([''.join(r) for r in path])
return
for col in range(n):
d1 = row - col + n - 1 # 偏移到 [0, 2n-2]
d2 = row + col
if cols[col] or diag1[d1] or diag2[d2]:
continue
cols[col] = diag1[d1] = diag2[d2] = True
row_str = ['Q' if c == col else '.' for c in range(n)]
path.append(row_str)
backtrack(row + 1, path)
path.pop()
cols[col] = diag1[d1] = diag2[d2] = False
backtrack(0, [])
return res时间复杂度： O(n!)，最坏情况 n=9 时约 362880 次尝试。 空间复杂度： O(n)，递归栈深度为 n，加上三个 O(n) 的标记集合。
易错点
- 对角线公式混淆：主对角线是
row - col（常数），副对角线是row + col（常数）。把两个搞混会导致错误的冲突判断。 - 负数索引问题：在集合版本中
row - col可能是负数，但 Python 的 set 可以存储负数，这是集合版本比数组版本简单的地方。数组版本需要加偏移row - col + n - 1。 - 路径拷贝：
res.append([''.join(r) for r in path])中path的每一行是列表，需要转换为字符串并创建新列表，避免后续被修改。 - n=1 边界：只有一个格子，放一个皇后，结果是
[["Q"]]。代码应正确处理。 - 对称性未利用：n 皇后问题的解通常有对称性，但标准解法不需要利用这个性质。面试时提到这一点可以加分。
框架提炼
棋盘回溯模板：
def solve(board_size):
res = []
列标记 = set()
主对角线标记 = set() # row - col
副对角线标记 = set() # row + col
def backtrack(row, path):
if row == board_size:
记录结果
return
for col in range(board_size):
if 冲突(列, 主对角线, 副对角线):
continue
标记(row, col)
构建当前行 → path
backtrack(row + 1, path)
撤销标记
backtrack(0, [])
return resN 皇后问题的问题本质：
- 这是”排列 + 约束”问题的经典代表。
- 每行选一列 = 对 [0, n-1] 做排列。
- 附加约束：对角线不能重复。
- 相比标准全排列，多了两个约束条件的剪枝。
冲突检查优化：
- 集合 O(1) 检查 vs 数组 O(1) 检查，性能相近。
- 集合版写起来更简单（无需处理负索引偏移）。
- 数组版用位运算（bitset）可以进一步优化到 O(1) 空间。