LeetCode 52. N 皇后 II
题目描述
题意分析
在
n × n棋盘上放置n个皇后，任意两个不能同行、同列或处于同一条对角线上，只返回合法摆法的数量。每行至多放一个皇后，而总共要放
n个，因此每行必须恰好放一个。可以按行递归，只选择当前行放在哪一列；此前皇后占用的列和它们对当前行的对角线攻击位置，用整数的二进制位表示。
解法：位运算回溯
核心思路
[!blue]
第
c位对应第c列。columns的置位表示已经有皇后占用的列；diagonals1、diagonals2的置位分别表示两类对角线在当前row行攻击到的列。它们记录的是当前行的封锁位置，不是固定不变的对角线编号。三个掩码按位或，得到所有不可选列；取反得到未被攻击的位置，再与
mask = (1 << n) - 1相与，限制在棋盘的低n位中。这就是available。如果它为零，当前行无处可放，这个分支没有方案，自然返回初值为零的count。用
position = available & -available取出最低的置位，也就是一个合法列。负数的补码性质使这个按位与只保留最低的1，而available -= position会清除这一位，所以循环会把合法列各枚举一次，既不重复也不遗漏。放入皇后后，先将
position并入三个掩码。进入下一行时，占用列不变；两类斜线攻击的位置则分别移动到列号加一和减一的位置，因此对角线掩码分别左移一位、右移一位。必须先合并再移位，才能同时移动新皇后产生的攻击位置。移出棋盘的位会在下一层计算available时被mask排除。这些掩码都是按值传递的整数，递归中的修改不会影响父层或兄弟分支，无需手动撤销。到达
row == n时，前面每行都放了一个不冲突的皇后，得到一个完整方案，返回1。每个方案都有唯一的逐行列选择序列，递归遍历所有合法序列并把返回值相加，得到的就是方案总数。
解题步骤
- 从第零行和三个空封锁集合开始递归。
- 达到第
n行时返回一，表示一个完整方案。- 计算低
n位内未被列和对角线封锁的位置。- 提取最低的一作为当前选择，并从候选集中移除。
- 合并新皇后，平移对角线后递归下一行，将各分支数量相加。
题目限制
1 <= n <= 9，这里的位移和计数都在int范围内。n == 1时唯一合法位置形成一个完整方案；无解时，每条分支都会在某一行遇到空候选集合，最终总数为零。镜像摆法只要位置不同就是不同方案，不需要额外合并。
代码实现
class Solution {
public int totalNQueens(int n) {
return backtrack(n, 0, 0, 0, 0);
}
// 三个掩码记录已有皇后对当前行的封锁，返回补完剩余行的方案数。
private int backtrack(int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
return 1;
}
// 只保留棋盘内的低位，取反产生的棋盘外位置不可选择。
int mask = (1 << n) - 1;
int available = mask & ~(columns | diagonals1 | diagonals2);
int count = 0;
while (available != 0) {
// 每次提取并移除最低可用位，让每个合法列只展开一次。
int position = available & -available;
available -= position;
// 先加入新皇后，再平移到下一行；整数按值传递，无需手动撤销。
count +=
backtrack(
n,
row + 1,
columns | position,
(diagonals1 | position) << 1,
(diagonals2 | position) >> 1);
}
return count;
}
}
func totalNQueens(n int) int {
var backtrack func(int, int, int, int) int
// 三个掩码记录已有皇后对当前行的封锁，返回补完剩余行的方案数。
backtrack = func(row int, columns int, diagonals1 int, diagonals2 int) int {
if row == n {
return 1
}
// 只保留棋盘内的低位，取反产生的棋盘外位置不可选择。
mask := (1 << n) - 1
available := mask & ^(columns | diagonals1 | diagonals2)
count := 0
for available != 0 {
// 每次提取并移除最低可用位，让每个合法列只展开一次。
position := available & -available
available -= position
// 先加入新皇后，再平移到下一行；整数按值传递，无需手动撤销。
count += backtrack(row+1, columns|position, (diagonals1|position)<<1, (diagonals2|position)>>1)
}
return count
}
return backtrack(0, 0, 0, 0)
}
复杂度分析
- 时间复杂度：$O(n!)$ 上界，每行占用不同列，合法前缀不超过排列型搜索树；位运算只枚举当前可用列。
- 空间复杂度：$O(n)$，来自最多
n层递归，各层只保存常数个整数。
关键点总结
[!green]
- 按行递归自动满足每行一个皇后，掩码负责列和对角线冲突。
- 对角线表示当前行的封锁位置，前进一行时要平移。
available & -available提取最低的一，减去它才会推进候选枚举。- 参数按值传递，各分支互不修改父层状态。
易错点总结
[!yellow]
- 先移位再加入新皇后，会把它的对角线攻击位置留在错误列上。
- 漏掉低位掩码，会把棋盘外位置误认为合法候选。
- 不移除已选候选，循环会一直重复同一分支。
- 完整方案应返回一，否则上层无法正确累计数量。
- 本题只要数量，不需要为每个解生成棋盘。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 51. N 皇后 | 困难 | 约束相同，原题构造所有棋盘，本题只累计完成方案数，可省去输出棋盘的复制。 |
| 37. 解数独 | 困难 | 同样用约束快速排除候选，再通过回溯枚举剩余位置。 |