0051. N-Queens

题目信息

题号:
  1. N 皇后

难度:

Hard

主题:

数组、回溯、约束传播、位掩码

原题:

LeetCode 0051

重点:

从逐行扫描已有皇后,推导到持续维护列与两类对角线的占用状态

题目重述

给定整数 n,在 n × n 棋盘上放置 n 个皇后,使任意两个皇后都不在同一行、同一列或 同一条对角线上。返回所有不同的合法棋盘,答案顺序不限。

每个棋盘由 n 个长度为 n 的字符串组成:'Q' 表示皇后,'.' 表示空位置。

约束为 1 <= n <= 9。

自建示例

输入:n = 4
输出:
[
  [".Q..", "...Q", "Q...", "..Q."],
  ["..Q.", "Q...", "...Q", ".Q.."]
]

第一块棋盘的皇后列序列为 [1,3,0,2]。每行恰有一个皇后,四个列号互不相同,两类对角线 编号也都互不相同。

输入:n = 1
输出:[["Q"]]

单个格子本身就是唯一合法棋盘。

C++ 实现

#include <cstdlib>
#include <string>
#include <vector>

class Solution {
private:
    std::vector<std::string> buildBoard(const std::vector<int>& placement) {
        const int n = static_cast<int>(placement.size());
        std::vector<std::string> board(n, std::string(n, '.'));
        for (int row = 0; row < n; ++row) {
            board[row][placement[row]] = 'Q';
        }
        return board;
    }

    bool isSafeByScanning(
        const std::vector<int>& 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<int>& placement,
        std::vector<std::vector<std::string>>& result
    ) {
        const int n = static_cast<int>(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<std::vector<std::string>> scanPreviousQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<int> placement(n, -1);
        scanDfs(0, placement, result);
        return result;
    }

    void occupancyDfs(
        int row,
        std::vector<int>& placement,
        std::vector<char>& columns,
        std::vector<char>& mainDiagonals,
        std::vector<char>& antiDiagonals,
        std::vector<std::vector<std::string>>& result
    ) {
        const int n = static_cast<int>(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<std::vector<std::string>> occupancyArrays(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<int> placement(n, -1);
        std::vector<char> columns(n, false);
        std::vector<char> mainDiagonals(2 * n - 1, false);
        std::vector<char> 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<int>& placement,
        std::vector<std::vector<std::string>>& result
    ) {
        const int n = static_cast<int>(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<std::vector<std::string>> bitMasks(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<int> placement(n, -1);
        int fullMask = (1 << n) - 1;
        bitmaskDfs(0, fullMask, 0, 0, 0, placement, result);
        return result;
    }

public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        return occupancyArrays(n);
    }
};

题解

逐行搜索基线

若对每个格子分别决定是否放皇后,搜索会产生大量已经违反行约束的状态。合法棋盘有 n 个皇后和 n 行,同一行又不能放两个皇后,因此每一行必须恰好放一个皇后。

令递归层 row 表示当前要确定的行,并用:

placement[row] = column

记录该行皇后的列号。进入第 row 层时,前 row 行已经各放置一个互不攻击的皇后;本层枚举 全部列,只保留与此前皇后不冲突的位置。到达 row == n 时,列序列已经唯一确定一块完整棋盘。

scanPreviousQueens 直接回看前面各行。候选 (row,column) 与 (previousRow,previousColumn) 冲突,当且仅当:

previousColumn == column
abs(previousRow - row) == abs(previousColumn - column)

同行冲突由逐行搜索自动消除。该方法严格对应题意,但每个候选都要扫描此前最多 row 个皇后。

三类占用编号

冲突判断只依赖候选所在的列和两类对角线:

列:column
主对角线 \:row - column
副对角线 /:row + column

同一条 \ 对角线上的 row-column 相同,同一条 / 对角线上的 row+column 相同。 其中 row-column 的范围为 [-(n-1),n-1],加上 n-1 后可作为 [0,2n-2] 内的数组下标;row+column 本身也处于这个范围。

因此只需维护:

columns[column]
mainDiagonals[row - column + n - 1]
antiDiagonals[row + column]

三次数组查询即可判断候选是否合法,不再回看具体皇后坐标。

逐行占用不变量

occupancyDfs 进入第 row 层时保持:

  • placement[0..row-1] 是当前已经放置的皇后列序列;

  • 三张占用表恰好记录这些皇后占据的列和对角线;

  • 前 row 行中的皇后两两不攻击。

选择 (row,column) 时,三个对应位置必须都未占用。写入 placement 并标记三条线路后, 不变量扩展到下一行。递归返回时撤销同一组三个标记,兄弟分支便重新获得完全相同的父状态。

对 n = 4 的一条成功路径:

行

列

主对角线编号

副对角线编号

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 的置位分别表示当前行已被列或对角线攻击的位置:

available = fullMask & ~(columns | mainAttacks | antiAttacks)

available 中的每个置位都是当前行的合法列。available & -available 每次取出最低置位, 从而只遍历合法候选。

放置 bit 后,列攻击在下一行保持原列。\ 对角线在下一行向右移动一列,所以左移一位; / 对角线向左移动一列,所以右移一位:

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) 额外状态, 位掩码只保存常数个整数和递归栈。