0052. N-Queens II ================= 题目信息 -------- :题号: 0052. N 皇后 II :难度: Hard :主题: 数组、回溯、约束状态、位掩码 :原题: `LeetCode 0052 `_ :重点: 从完整枚举棋盘转为叶子计数,再把列与对角线约束压缩进位掩码 题目重述 -------- 给定整数 ``n``,统计在 ``n × n`` 棋盘上放置 ``n`` 个皇后的不同方案数。任意两个皇后都不能位于 同一行、同一列或同一条对角线上。本题只返回方案数量,不需要返回每个棋盘。 约束为 ``1 <= n <= 9``。 自建示例 -------- .. code-block:: text 输入:n = 4 输出:2 解释:两个合法列序列为 [1, 3, 0, 2] 和 [2, 0, 3, 1]。 .. code-block:: text 输入:n = 3 输出:0 解释:无论第一行选择哪一列,后续某一行都会失去全部合法位置。 .. code-block:: text 输入:n = 1 输出:1 解释:唯一格子放置一个皇后即为完整方案。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: bool conflictsWithPrevious( const std::vector& 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& 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 placement(n, -1); return scanDfs(n, 0, placement); } int occupancyDfs( int n, int row, std::vector& columns, std::vector& downDiagonals, std::vector& 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 columns(n, false); std::vector downDiagonals(2 * n - 1, false); std::vector 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)`` 时,只需与此前各行比较: .. code-block:: text previousColumn == column 同列冲突 previousRow - previousColumn == row - column 同一条 \ 对角线 previousRow + previousColumn == row + column 同一条 / 对角线 同行冲突已由逐行搜索消除。``scanPreviousRows`` 直接按照定义检查候选,能够作为正确基线;代价是每次判断 都要重新扫描此前皇后。 占用状态缓存 ~~~~~~~~~~~~ 候选是否合法只依赖三类线路是否已经出现皇后: .. code-block:: text 列编号: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``。否则每个合法列都产生一个新的子状态: .. code-block:: text count(row, state) = 所有合法 column 的 count(row + 1, newState) 之和 不同列分支在当前行已经不同,不可能生成同一个棋盘。任意合法棋盘又有唯一的逐行列序列,因此所有叶子可以直接 相加,每个合法方案恰好计数一次。 位掩码压缩 ~~~~~~~~~~ 由于 ``n <= 9``,一个无符号整数的低 ``n`` 位足以表示一整行。第 ``column`` 位对应同名列, ``full`` 的低 ``n`` 位全部为 ``1``: .. code-block:: text full = (1 << n) - 1 三个掩码分别表示: .. code-block:: text columns 已经放过皇后的列 downAttacks 当前行受到 \ 对角线攻击的列 upAttacks 当前行受到 / 对角线攻击的列 当前行全部合法列可一次得到: .. code-block:: text available = full & ~(columns | downAttacks | upAttacks) 与 ``full`` 相与会清除取反后棋盘范围外的高位。``available`` 中每个置位都对应一个合法候选。 对角线状态转移 ~~~~~~~~~~~~~~ 当前行选择第 ``column`` 位后,列攻击在下一行仍位于原列。两类对角线则发生水平移动: * ``\`` 对角线在下一行攻击 ``column + 1``,对应整体左移一位; * ``/`` 对角线在下一行攻击 ``column - 1``,对应整体右移一位。 因此下一层状态为: .. code-block:: text 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 列: .. code-block:: text 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²)`` 的 输出成本。