N 皇后 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n，返回 n 皇后问题 不同的解决方案的数量。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：在 n×n 的每个格子里决定放或不放皇后，共 2^{n²} 种状态，再过滤出恰好 n 个皇后且互不攻击的——思路对，但状态空间巨大。
2. 第一个剪枝：每行必须恰好一个皇后，问题变成「为每一行选一个列」，至多 n^n 种排列。
3. 重复在哪里？按行放置时，很多列选法与已有皇后同列或同斜线冲突，却还要把后面所有行试完——和 #51 N 皇后完全相同的搜索树，只是本题不要求输出棋盘。
4. 关键转化：用 cols、diag1(row-col)、diag2(row+col) 三个集合 O(1) 判断冲突；DFS 逐行枚举列，能放就递归下一行，row==n 时 count+=1 即可，不必构造字符串棋盘。
5. 手推 n=4：搜索过程与 #51 一致，最终数到 2 种合法放置；n=2/3 时 count=0。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 时说明找到一种完整解 |
count | int | 定义：合法完整解的总数 维护：仅当 row==n 时加 1，无需构造棋盘字符串更新：每到达叶子层 count += 1；DFS 结束后返回 count |
落码步骤
1. 初始化 count = 0、queens = [0]*n，以及空集合 cols, diag1, diag2
2. 定义 DFS backtrack(row)：若 row == n，count += 1 并返回
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) 启动，返回 count
代码实现
class Solution:
def totalNQueens(self, n: int) -> int:
count = 0
queens = [0] * n
cols: set[int] = set()
diag1: set[int] = set() # row - col
diag2: set[int] = set() # row + col
def backtrack(row: int) -> None:
nonlocal count
if row == n:
count += 1
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 countclass Solution {
public:
int totalNQueens(int n) {
int count = 0;
vector<int> queens(n, 0);
unordered_set<int> cols, diag1, diag2;
function<void(int)> backtrack = [&](int row) {
if (row == n) {
++count;
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 count;
}
};
// 时间 O(n!)，空间 O(n)（递归栈 + 集合）复杂度分析
O(n!)（剪枝后远好于 n^n 全枚举）
O(n)（递归栈 + 冲突集合）
常见坑
回溯不撤销：放入皇后后递归返回，必须从 cols/diag1/diag2 中移除本次登记，否则污染兄弟分支、计数偏大。
斜线判断写错：主对角线是 row - col 相同，副对角线是 row + col 相同；不要混用或漏判其中一种。
本题只计数：到达 row==n 时 count+=1 即可，不要像 #51 那样构造棋盘字符串——多此一举且更慢。
必测边界 Case
n = 1 → 1（唯一一格放皇后，只有一种解）
n = 2 → 0，n = 3 → 0（小棋盘不存在合法放置）
n = 4 → 2（经典样例，与 #51 的解数一致）
n = 9（题目上限，回溯深度 9，需依赖剪枝）