52. N 皇后 II
题目描述
皇后能攻击同一行、同一列以及两条对角线上的任意棋子。输入整数 n，在 n x n 的棋盘上摆 n 个皇后，要求任意两个皇后都互不攻击。
返回满足要求的不同摆法的总数。
示例 1
输入：n = 4 输出：2
解释：4 x 4 棋盘上只有 2 种合法摆法。
示例 2
输入：n = 1 输出：1
数据范围
1 <= n <= 9
解题思路：回溯 + 集合剪枝
逐行放置：第 r 行只放一个皇后，枚举它的列 c。用三个集合记录已占用的列、主对角线（r-c 相同）、副对角线（r+c 相同）。如果 (r,c) 不在任何一个集合中，就放下并递归到下一行，回来后撤销。放完第 n 行说明找到 1 种方案，把子问题的方案数加起来即可。
为什么正确
进入 dfs(r) 时，前 r 行各有一个皇后且互不攻击；三个集合恰好对应这 r 个皇后。
复杂度分析
时间约 O(n!)，空间 O(n)。
易错点
斜线要分两个方向：r-c 和 r+c。只记一个会把另一方向的冲突漏掉；r-c 可能为负，用数组时要加 n-1 偏移。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def totalNQueens(self, n: int) -> int:
cols, diag1, diag2 = set(), set(), set()
def dfs(r):
if r == n:
return 1
count = 0
for c in range(n):
if c in cols or r - c in diag1 or r + c in diag2:
continue
cols.add(c)
diag1.add(r - c)
diag2.add(r + c)
count += dfs(r + 1)
cols.remove(c)
diag1.remove(r - c)
diag2.remove(r + c)
return count
return dfs(0)class Solution {
int n;
Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
public int totalNQueens(int n) {
this.n = n;
return dfs(0);
}
int dfs(int r) {
if (r == n) {
return 1;
}
int count = 0;
for (int c = 0; c < n; c++) {
if (cols.contains(c) || diag1.contains(r - c) || diag2.contains(r + c)) {
continue;
}
cols.add(c);
diag1.add(r - c);
diag2.add(r + c);
count += dfs(r + 1);
cols.remove(c);
diag1.remove(r - c);
diag2.remove(r + c);
}
return count;
}
}class Solution {
public:
int totalNQueens(int n) {
unordered_set<int> cols, diag1, diag2;
function<int(int)> dfs = [&](int r) -> int {
if (r == n) {
return 1;
}
int count = 0;
for (int c = 0; c < n; c++) {
if (cols.count(c) || diag1.count(r - c) || diag2.count(r + c)) {
continue;
}
cols.insert(c);
diag1.insert(r - c);
diag2.insert(r + c);
count += dfs(r + 1);
cols.erase(c);
diag1.erase(r - c);
diag2.erase(r + c);
}
return count;
};
return dfs(0);
}
};func totalNQueens(n int) int {
cols, diag1, diag2 := map[int]bool{}, map[int]bool{}, map[int]bool{}
var dfs func(r int) int
dfs = func(r int) int {
if r == n {
return 1
}
count := 0
for c := 0; c < n; c++ {
if cols[c] || diag1[r-c] || diag2[r+c] {
continue
}
cols[c] = true
diag1[r-c] = true
diag2[r+c] = true
count += dfs(r + 1)
delete(cols, c)
delete(diag1, r-c)
delete(diag2, r+c)
}
return count
}
return dfs(0)
}var totalNQueens = function(n) {
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
const dfs = (r) => {
if (r === n) {
return 1;
}
let count = 0;
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag1.has(r - c) || diag2.has(r + c)) {
continue;
}
cols.add(c);
diag1.add(r - c);
diag2.add(r + c);
count += dfs(r + 1);
cols.delete(c);
diag1.delete(r - c);
diag2.delete(r + c);
}
return count;
};
return dfs(0);
};function totalNQueens(n: number): number {
const cols = new Set<number>(), diag1 = new Set<number>(), diag2 = new Set<number>();
const dfs = (r: number): number => {
if (r === n) {
return 1;
}
let count = 0;
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag1.has(r - c) || diag2.has(r + c)) {
continue;
}
cols.add(c);
diag1.add(r - c);
diag2.add(r + c);
count += dfs(r + 1);
cols.delete(c);
diag1.delete(r - c);
diag2.delete(r + c);
}
return count;
};
return dfs(0);
}其他解法
两者搜索树相同；集合版本便于理解，位运算版本省去哈希开销，是本题最快的写法。
解法 2：回溯 + 位运算 时间 O(n!)，空间 O(n)
用整数 cols、d1、d2 的二进制位分别记录被占用的列和两条对角线。当前行的候选位置是 full & ~(cols | d1 | d2)。每次用 avail & -avail 取出最低位放皇后，递归到下一行时 d1 左移、d2 右移。cols 等于 full 时说明 n 行都放好了，计数加一。
只需要计数，不用记录棋盘，所以位运算版本的优势更明显。冲突判断是 O(1) 的整数运算，常数远小于集合。
class Solution:
def totalNQueens(self, n: int) -> int:
full = (1 << n) - 1
def dfs(cols, d1, d2):
if cols == full:
return 1
count = 0
avail = full & ~(cols | d1 | d2)
while avail:
bit = avail & -avail
avail &= avail - 1
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
return count
return dfs(0, 0, 0)class Solution {
int full;
public int totalNQueens(int n) {
full = (1 << n) - 1;
return dfs(0, 0, 0);
}
int dfs(int cols, int d1, int d2) {
if (cols == full) return 1;
int count = 0;
int avail = full & ~(cols | d1 | d2);
while (avail != 0) {
int bit = avail & -avail;
avail &= avail - 1;
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}
}class Solution {
public:
int full;
int dfs(int cols, int d1, int d2) {
if (cols == full) return 1;
int count = 0;
int avail = full & ~(cols | d1 | d2);
while (avail) {
int bit = avail & -avail;
avail &= avail - 1;
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}
int totalNQueens(int n) {
full = (1 << n) - 1;
return dfs(0, 0, 0);
}
};func totalNQueens(n int) int {
full := (1 << n) - 1
var dfs func(cols, d1, d2 int) int
dfs = func(cols, d1, d2 int) int {
if cols == full {
return 1
}
count := 0
avail := full &^ (cols | d1 | d2)
for avail != 0 {
bit := avail & -avail
avail &= avail - 1
count += dfs(cols|bit, ((d1|bit)<<1)&full, (d2|bit)>>1)
}
return count
}
return dfs(0, 0, 0)
}var totalNQueens = function(n) {
const full = (1 << n) - 1;
const dfs = (cols, d1, d2) => {
if (cols === full) return 1;
let count = 0;
let avail = full & ~(cols | d1 | d2);
while (avail) {
const bit = avail & -avail;
avail &= avail - 1;
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
};
return dfs(0, 0, 0);
};function totalNQueens(n: number): number {
const full = (1 << n) - 1;
const dfs = (cols: number, d1: number, d2: number): number => {
if (cols === full) return 1;
let count = 0;
let avail = full & ~(cols | d1 | d2);
while (avail) {
const bit = avail & -avail;
avail &= avail - 1;
count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
};
return dfs(0, 0, 0);
}