0051. N-Queens
===============
题目信息
--------
:题号: 0051. N 皇后
:难度: Hard
:主题: 数组、回溯、约束传播、位掩码
:原题: `LeetCode 0051 `_
:重点: 从逐行扫描已有皇后,推导到持续维护列与两类对角线的占用状态
题目重述
--------
给定整数 ``n``,在 ``n × n`` 棋盘上放置 ``n`` 个皇后,使任意两个皇后都不在同一行、同一列或
同一条对角线上。返回所有不同的合法棋盘,答案顺序不限。
每个棋盘由 ``n`` 个长度为 ``n`` 的字符串组成:``'Q'`` 表示皇后,``'.'`` 表示空位置。
约束为 ``1 <= n <= 9``。
自建示例
--------
.. code-block:: text
输入:n = 4
输出:
[
[".Q..", "...Q", "Q...", "..Q."],
["..Q.", "Q...", "...Q", ".Q.."]
]
第一块棋盘的皇后列序列为 ``[1,3,0,2]``。每行恰有一个皇后,四个列号互不相同,两类对角线
编号也都互不相同。
.. code-block:: text
输入:n = 1
输出:[["Q"]]
单个格子本身就是唯一合法棋盘。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::vector buildBoard(const std::vector& placement) {
const int n = static_cast(placement.size());
std::vector board(n, std::string(n, '.'));
for (int row = 0; row < n; ++row) {
board[row][placement[row]] = 'Q';
}
return board;
}
bool isSafeByScanning(
const std::vector& placement,
int row,
int column
) {
for (int previousRow = 0; previousRow < row; ++previousRow) {
int previousColumn = placement[previousRow];
if (previousColumn == column) return false;
if (std::abs(previousRow - row) ==
std::abs(previousColumn - column)) {
return false;
}
}
return true;
}
void scanDfs(
int row,
std::vector& placement,
std::vector>& result
) {
const int n = static_cast(placement.size());
if (row == n) {
result.push_back(buildBoard(placement));
return;
}
for (int column = 0; column < n; ++column) {
if (!isSafeByScanning(placement, row, column)) continue;
placement[row] = column;
scanDfs(row + 1, placement, result);
}
}
std::vector> scanPreviousQueens(int n) {
std::vector> result;
std::vector placement(n, -1);
scanDfs(0, placement, result);
return result;
}
void occupancyDfs(
int row,
std::vector& placement,
std::vector& columns,
std::vector& mainDiagonals,
std::vector& antiDiagonals,
std::vector>& result
) {
const int n = static_cast(placement.size());
if (row == n) {
result.push_back(buildBoard(placement));
return;
}
for (int column = 0; column < n; ++column) {
int main = row - column + n - 1;
int anti = row + column;
if (columns[column] || mainDiagonals[main] ||
antiDiagonals[anti]) {
continue;
}
placement[row] = column;
columns[column] = true;
mainDiagonals[main] = true;
antiDiagonals[anti] = true;
occupancyDfs(
row + 1,
placement,
columns,
mainDiagonals,
antiDiagonals,
result
);
columns[column] = false;
mainDiagonals[main] = false;
antiDiagonals[anti] = false;
}
}
std::vector> occupancyArrays(int n) {
std::vector> result;
std::vector placement(n, -1);
std::vector columns(n, false);
std::vector mainDiagonals(2 * n - 1, false);
std::vector antiDiagonals(2 * n - 1, false);
occupancyDfs(
0,
placement,
columns,
mainDiagonals,
antiDiagonals,
result
);
return result;
}
int columnOfBit(int bit) {
int column = 0;
while ((1 << column) != bit) ++column;
return column;
}
void bitmaskDfs(
int row,
int fullMask,
int columns,
int mainAttacks,
int antiAttacks,
std::vector& placement,
std::vector>& result
) {
const int n = static_cast(placement.size());
if (row == n) {
result.push_back(buildBoard(placement));
return;
}
int available = fullMask &
~(columns | mainAttacks | antiAttacks);
while (available != 0) {
int bit = available & -available;
available -= bit;
placement[row] = columnOfBit(bit);
bitmaskDfs(
row + 1,
fullMask,
columns | bit,
((mainAttacks | bit) << 1) & fullMask,
(antiAttacks | bit) >> 1,
placement,
result
);
}
}
std::vector> bitMasks(int n) {
std::vector> result;
std::vector placement(n, -1);
int fullMask = (1 << n) - 1;
bitmaskDfs(0, fullMask, 0, 0, 0, placement, result);
return result;
}
public:
std::vector> solveNQueens(int n) {
return occupancyArrays(n);
}
};
题解
----
逐行搜索基线
~~~~~~~~~~~~
若对每个格子分别决定是否放皇后,搜索会产生大量已经违反行约束的状态。合法棋盘有 ``n`` 个皇后和
``n`` 行,同一行又不能放两个皇后,因此每一行必须恰好放一个皇后。
令递归层 ``row`` 表示当前要确定的行,并用:
.. code-block:: text
placement[row] = column
记录该行皇后的列号。进入第 ``row`` 层时,前 ``row`` 行已经各放置一个互不攻击的皇后;本层枚举
全部列,只保留与此前皇后不冲突的位置。到达 ``row == n`` 时,列序列已经唯一确定一块完整棋盘。
``scanPreviousQueens`` 直接回看前面各行。候选 ``(row,column)`` 与
``(previousRow,previousColumn)`` 冲突,当且仅当:
.. code-block:: text
previousColumn == column
abs(previousRow - row) == abs(previousColumn - column)
同行冲突由逐行搜索自动消除。该方法严格对应题意,但每个候选都要扫描此前最多 ``row`` 个皇后。
三类占用编号
~~~~~~~~~~~~
冲突判断只依赖候选所在的列和两类对角线:
.. code-block:: text
列:column
主对角线 \:row - column
副对角线 /:row + column
同一条 ``\`` 对角线上的 ``row-column`` 相同,同一条 ``/`` 对角线上的 ``row+column`` 相同。
其中 ``row-column`` 的范围为 ``[-(n-1),n-1]``,加上 ``n-1`` 后可作为
``[0,2n-2]`` 内的数组下标;``row+column`` 本身也处于这个范围。
因此只需维护:
.. code-block:: text
columns[column]
mainDiagonals[row - column + n - 1]
antiDiagonals[row + column]
三次数组查询即可判断候选是否合法,不再回看具体皇后坐标。
逐行占用不变量
~~~~~~~~~~~~~~
``occupancyDfs`` 进入第 ``row`` 层时保持:
* ``placement[0..row-1]`` 是当前已经放置的皇后列序列;
* 三张占用表恰好记录这些皇后占据的列和对角线;
* 前 ``row`` 行中的皇后两两不攻击。
选择 ``(row,column)`` 时,三个对应位置必须都未占用。写入 ``placement`` 并标记三条线路后,
不变量扩展到下一行。递归返回时撤销同一组三个标记,兄弟分支便重新获得完全相同的父状态。
对 ``n = 4`` 的一条成功路径:
.. list-table::
:header-rows: 1
* - 行
- 列
- 主对角线编号
- 副对角线编号
* - 0
- 1
- 2
- 1
* - 1
- 3
- 1
- 4
* - 2
- 0
- 5
- 2
* - 3
- 2
- 4
- 5
三组编号分别互不重复,所以列序列 ``[1,3,0,2]`` 构成合法棋盘。
任意合法棋盘在每一行都有唯一列号。算法逐行枚举所有列,只删除与当前前缀冲突的候选,因此该棋盘的
列序列不会被遗漏。任何到达叶子的路径又满足行、列和两类对角线约束,所以一定是合法解。不同列序列
至少在一行不同,构造出的棋盘也不同。
位掩码状态转移
~~~~~~~~~~~~~~
当 ``n <= 9`` 时,一个整数的低 ``n`` 位可以表示一行中的全部列。``columns``、``mainAttacks`` 和
``antiAttacks`` 的置位分别表示当前行已被列或对角线攻击的位置:
.. code-block:: text
available = fullMask & ~(columns | mainAttacks | antiAttacks)
``available`` 中的每个置位都是当前行的合法列。``available & -available`` 每次取出最低置位,
从而只遍历合法候选。
放置 ``bit`` 后,列攻击在下一行保持原列。``\`` 对角线在下一行向右移动一列,所以左移一位;
``/`` 对角线向左移动一列,所以右移一位:
.. code-block:: text
nextColumns = columns | bit
nextMain = ((mainAttacks | bit) << 1) & fullMask
nextAnti = (antiAttacks | bit) >> 1
位掩码法与占用数组法展开同一棵逐行搜索树,只把三张布尔表和逐列检查改写成整数位运算。
公开入口采用占用数组法,它已经把候选判断降为常数时间,并保留了最直观的约束含义。
边界处理
~~~~~~~~
``n = 1`` 时,根层唯一候选立即形成答案。``n = 2`` 和 ``n = 3`` 的每条路径都会在放满所有行前
失去合法候选,因此自然返回空结果,不需要特殊分支。
复杂度分析
~~~~~~~~~~
忽略对角线剪枝,逐行选择不同列的搜索规模以 ``n!`` 为上界量级。扫描法每次候选检查还需回看
``O(n)`` 个皇后,可写成 ``O(n² · n!)`` 的宽松上界。
占用数组法每个搜索节点扫描 ``n`` 列,搜索部分为 ``O(n · n!)`` 的宽松上界。位掩码法只枚举当前
合法位,状态转移数以 ``O(n!)`` 为上界量级。若合法棋盘数为 ``S``,构造输出还必须写入
``S · n²`` 个字符。
不计返回结果,三种方法的递归深度和列序列均为 ``O(n)``。占用数组使用 ``O(n)`` 额外状态,
位掩码只保存常数个整数和递归栈。