N 皇后
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：在 n×n 的每个格子里决定放或不放皇后，共 2^{n²} 种状态，再过滤出恰好 n 个皇后且互不攻击的——思路对，但状态空间巨大。
2. 第一个剪枝：每行必须恰好一个皇后（否则某行空着或有两个，都不合法），问题变成「为每一行选一个列」，至多 n^n 种排列。
3. 重复在哪里？按行放置时，子问题变成「前 row 行已放好，第 row 行该放哪一列？」——很多列选法会与已有皇后同列或同斜线冲突，却还要把后面所有行试完。
4. 关键转化：用 cols、diag1(row-col)、diag2(row+col) 三个集合 O(1) 判断冲突；DFS 逐行枚举列，能放就递归下一行，子树走不通立刻撤销换列。
5. 手推 n=4：第 0 行试 col=0 会一路走到死路；col=1 得解 ".Q.."/"...Q"/"Q..."/"..Q."；继续搜索还能找到对称解。n≤9，回溯深度 ≤ 9，完全可行。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
queens | int[n] | 定义：queens[row] 表示第 row 行皇后所在的列号维护：每行恰好放一个皇后，用一维数组即可完整描述当前部分解 更新：在 row 行尝试列 col 时令 queens[row]=col；回溯返回后该位置会被下一列覆盖 |
cols | set<int> | 定义：已被占用的列号集合 维护：任意时刻，已放置的皇后两两不同列 更新：在 (row,col) 放皇后前查 col not in cols；放入时 add(col)，回溯时 remove(col) |
diag1 | set<int> | 定义：主对角线标识 row - col 的已占用集合（↘ 方向同线相等）维护：同一主对角线上任意两格 row-col 相同更新：放皇后前查 (row-col) not in diag1；放入/撤销与 cols 同步 |
diag2 | set<int> | 定义：副对角线标识 row + col 的已占用集合（↗ 方向同线相等）维护：同一副对角线上任意两格 row+col 相同更新：放皇后前查 (row+col) not in diag2；放入/撤销与 cols 同步 |
row | int | 定义：当前待放置皇后的行号（从 0 到 n-1） 维护：DFS 逐行向下推进，每行只尝试合法列 更新：初始为 0；每成功放一行后 row+1 递归；row==n 时收集完整解 |
ans | list<list<str>> | 定义：所有合法棋盘的字符串表示 维护：仅当 row==n 时，按 queens 构造 n 行字符串并加入更新：每到达叶子层追加一次；构造时第 r 行在 queens[r] 处放 'Q'，其余为 '.' |
落码步骤
1. 初始化 ans = []、queens = [0]*n，以及空集合 cols, diag1, diag2
2. 定义 DFS backtrack(row)：若 row == n，按 queens 构造 n 行字符串加入 ans 并返回
3. 对 col 从 0 到 n-1：若 col in cols 或 (row-col) in diag1 或 (row+col) in diag2，跳过
4. 否则：登记三个集合、queens[row]=col，递归 backtrack(row+1)
5. 回溯：从三个集合中移除本次登记，继续尝试下一列
6. 从 backtrack(0) 启动，返回 ans
代码实现
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans: list[list[str]] = []
queens = [0] * n
cols: set[int] = set()
diag1: set[int] = set() # row - col
diag2: set[int] = set() # row + col
def backtrack(row: int) -> None:
if row == n:
board = []
for r in range(n):
line = ['.'] * n
line[queens[r]] = 'Q'
board.append(''.join(line))
ans.append(board)
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)
queens[row] = col
backtrack(row + 1)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return ansclass Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<int> queens(n, 0);
unordered_set<int> cols, diag1, diag2;
function<void(int)> backtrack = [&](int row) {
if (row == n) {
vector<string> board(n, string(n, '.'));
for (int r = 0; r < n; ++r)
board[r][queens[r]] = 'Q';
ans.push_back(move(board));
return;
}
for (int col = 0; col < n; ++col) {
if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col))
continue;
cols.insert(col);
diag1.insert(row - col);
diag2.insert(row + col);
queens[row] = col;
backtrack(row + 1);
cols.erase(col);
diag1.erase(row - col);
diag2.erase(row + col);
}
};
backtrack(0);
return ans;
}
};
// 时间 O(n!)，空间 O(n)（递归栈 + 集合，不计输出）复杂度分析
O(n!)（剪枝后远好于 n^n 全枚举）
O(n)（递归栈 + 冲突集合，不计输出）
常见坑
回溯不撤销：放入皇后后递归返回，必须从 cols/diag1/diag2 中移除本次登记，否则污染兄弟分支。
斜线判断写错：主对角线是 row - col 相同，副对角线是 row + col 相同；不要混用或漏判其中一种。
输出格式：每行是长度为 n 的字符串，'Q' 与 '.' 组成；不是坐标列表，也不是二维字符数组的嵌套列表混用 int。
必测边界 Case
n = 1 → [["Q"]]（唯一一格放皇后）
n = 2 → []，n = 3 → []（小棋盘不存在合法放置，应返回空列表）
n = 4 → 2 种棋盘（经典样例，注意两种解互为镜像/旋转）
n = 9（题目上限，回溯深度 9，需依赖剪枝）