0052. N-Queens II¶
题目信息¶
- 题号:
N 皇后 II
- 难度:
Hard
- 主题:
数组、回溯、约束状态、位掩码
- 原题:
- 重点:
从完整枚举棋盘转为叶子计数,再把列与对角线约束压缩进位掩码
题目重述¶
给定整数 n,统计在 n × n 棋盘上放置 n 个皇后的不同方案数。任意两个皇后都不能位于
同一行、同一列或同一条对角线上。本题只返回方案数量,不需要返回每个棋盘。
约束为 1 <= n <= 9。
自建示例¶
输入:n = 4
输出:2
解释:两个合法列序列为 [1, 3, 0, 2] 和 [2, 0, 3, 1]。
输入:n = 3
输出:0
解释:无论第一行选择哪一列,后续某一行都会失去全部合法位置。
输入:n = 1
输出:1
解释:唯一格子放置一个皇后即为完整方案。
C++ 实现¶
#include <vector>
class Solution {
private:
bool conflictsWithPrevious(
const std::vector<int>& placement,
int row,
int column
) {
for (int previousRow = 0; previousRow < row; ++previousRow) {
const int previousColumn = placement[previousRow];
if (previousColumn == column) {
return true;
}
if (previousRow - previousColumn == row - column) {
return true;
}
if (previousRow + previousColumn == row + column) {
return true;
}
}
return false;
}
int scanDfs(int n, int row, std::vector<int>& placement) {
if (row == n) {
return 1;
}
int total = 0;
for (int column = 0; column < n; ++column) {
if (conflictsWithPrevious(placement, row, column)) {
continue;
}
placement[row] = column;
total += scanDfs(n, row + 1, placement);
}
return total;
}
int scanPreviousRows(int n) {
std::vector<int> placement(n, -1);
return scanDfs(n, 0, placement);
}
int occupancyDfs(
int n,
int row,
std::vector<char>& columns,
std::vector<char>& downDiagonals,
std::vector<char>& upDiagonals
) {
if (row == n) {
return 1;
}
int total = 0;
for (int column = 0; column < n; ++column) {
const int down = row - column + n - 1;
const int up = row + column;
if (columns[column] ||
downDiagonals[down] ||
upDiagonals[up]) {
continue;
}
columns[column] = true;
downDiagonals[down] = true;
upDiagonals[up] = true;
total += occupancyDfs(
n,
row + 1,
columns,
downDiagonals,
upDiagonals
);
columns[column] = false;
downDiagonals[down] = false;
upDiagonals[up] = false;
}
return total;
}
int occupancyArrays(int n) {
std::vector<char> columns(n, false);
std::vector<char> downDiagonals(2 * n - 1, false);
std::vector<char> upDiagonals(2 * n - 1, false);
return occupancyDfs(
n,
0,
columns,
downDiagonals,
upDiagonals
);
}
int bitDfs(
unsigned int full,
unsigned int columns,
unsigned int downAttacks,
unsigned int upAttacks
) {
if (columns == full) {
return 1;
}
unsigned int available =
full & ~(columns | downAttacks | upAttacks);
int total = 0;
while (available != 0U) {
const unsigned int bit =
available & (~available + 1U);
available ^= bit;
total += bitDfs(
full,
columns | bit,
((downAttacks | bit) << 1) & full,
(upAttacks | bit) >> 1
);
}
return total;
}
int bitMasks(int n) {
const unsigned int full = (1U << n) - 1U;
return bitDfs(full, 0U, 0U, 0U);
}
public:
int totalNQueens(int n) {
return bitMasks(n);
}
};
题解¶
逐行计数模型¶
合法棋盘共有 n 个皇后,同一行不能出现两个皇后,而棋盘也恰好有 n 行。因此每一行必须恰好
放置一个皇后。
递归层 row 直接表示当前要决定的行,本层只枚举皇后列号。到达 row == n 时,一条完整且合法的
列序列已经形成。本题不需要构造棋盘,只返回 1 表示发现一个方案;父节点把所有子分支的计数相加。
这与 0051 使用同一搜索树,区别只在叶子处理:0051 保存棋盘,0052 累加叶子数量。
扫描已有皇后¶
placement[row] 保存第 row 行的皇后列。尝试 (row, column) 时,只需与此前各行比较:
previousColumn == column
同列冲突
previousRow - previousColumn == row - column
同一条 \ 对角线
previousRow + previousColumn == row + column
同一条 / 对角线
同行冲突已由逐行搜索消除。scanPreviousRows 直接按照定义检查候选,能够作为正确基线;代价是每次判断
都要重新扫描此前皇后。
占用状态缓存¶
候选是否合法只依赖三类线路是否已经出现皇后:
列编号:column
\ 对角线编号:row - column + n - 1
/ 对角线编号:row + column
row - column 的范围是 [-(n - 1), n - 1],平移 n - 1 后与 row + column 一样,
都落在 [0, 2n - 2]。因此一张长度为 n 的列数组和两张长度为 2n - 1 的对角线数组
足以保存全部冲突状态。
选择一个候选时设置对应的三个标记,递归返回后撤销同一组三个标记。进入任意递归层时始终保持:
三张占用表恰好描述当前路径中的皇后;
当前行之前每行恰有一个皇后;
当前路径内部不存在列或对角线冲突。
所以候选只需三次数组查询即可判断。撤销保证兄弟分支从相同父状态开始,不会受到已经退出路径的皇后影响。
计数递推不变量¶
设 count(row, state) 表示在当前占用状态下,从第 row 行继续放置能够得到的合法方案数。
若 row == n,当前路径已放满所有行,贡献 1。否则每个合法列都产生一个新的子状态:
count(row, state)
= 所有合法 column 的 count(row + 1, newState) 之和
不同列分支在当前行已经不同,不可能生成同一个棋盘。任意合法棋盘又有唯一的逐行列序列,因此所有叶子可以直接 相加,每个合法方案恰好计数一次。
位掩码压缩¶
由于 n <= 9,一个无符号整数的低 n 位足以表示一整行。第 column 位对应同名列,
full 的低 n 位全部为 1:
full = (1 << n) - 1
三个掩码分别表示:
columns 已经放过皇后的列
downAttacks 当前行受到 \ 对角线攻击的列
upAttacks 当前行受到 / 对角线攻击的列
当前行全部合法列可一次得到:
available = full & ~(columns | downAttacks | upAttacks)
与 full 相与会清除取反后棋盘范围外的高位。available 中每个置位都对应一个合法候选。
对角线状态转移¶
当前行选择第 column 位后,列攻击在下一行仍位于原列。两类对角线则发生水平移动:
\对角线在下一行攻击column + 1,对应整体左移一位;/对角线在下一行攻击column - 1,对应整体右移一位。
因此下一层状态为:
columns' = columns | bit
downAttacks' = ((downAttacks | bit) << 1) & full
upAttacks' = (upAttacks | bit) >> 1
表达式 available & (~available + 1U) 提取最低置位,available ^= bit 再删除它。循环会把当前行
每个合法列恰好枚举一次。
位掩码版本不必显式传递 row。每层恰好选择一个此前未占用的列,所以 columns 中置位数量就是已放置
皇后数,也就是已处理行数。当 columns == full 时,全部 n 列均已使用,当前路径恰好完成 n 行,
返回 1。
状态演化¶
对 n = 4,初始 full = 1111,第一行所有列都可选。若第一行选择第 1 列:
bit = 0010
columns = 0010
downAttacks = 0100
upAttacks = 0001
available = 1111 & ~(0010 | 0100 | 0001)
= 1000
第二行只剩第 3 列可选。若某层 available 为零,该路径没有合法完成方式,返回的计数自然为零;递归随后
回到上一层尝试其他候选。
代码演进¶
scanPreviousRows 保存列序列,并为每个候选重新扫描已有皇后。
occupancyArrays 把重复冲突检查缓存为列和两类对角线占用表,使候选判断降为常数时间。
bitMasks 进一步把三张表压缩为整数,并一次计算当前行全部合法列。公开入口采用该方法,因为它只保留计数所需的
约束状态,不构造列序列或棋盘。
复杂度分析¶
忽略对角线剪枝,逐行选择互不相同的列形成的搜索树以 O(n!) 为上界量级。扫描方法的候选检查还需回看
O(n) 个皇后,可写成 O(n · n!) 的宽松上界;占用数组与位掩码方法对每个候选只做常数状态操作,
搜索上界为 O(n!)。
三种方法递归深度均为 O(n)。扫描方法保存 O(n) 的列序列,占用数组额外保存总长度 O(n) 的
布尔状态;位掩码除递归栈外只携带固定数量整数。本题不构造棋盘,因此没有 0051 中每个方案 O(n²) 的
输出成本。