LeetCode62 - N 皇后 | 很多时候不懂事

📝 题目描述

题目链接：N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

示例 1：

1
2
3

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1 2	输入：n = 1 输出：[["Q"]]

提示：

1 <= n <= 9

💡 解题思路

方法一：基于集合的回溯

根据题目不难发现，答案的每行一定有且只有一个皇后，因此我们可以按行进行回溯。

确定了回溯方法，接下来思考如何判定每行的 n 个位置是否可以放置皇后棋子。

我们不需要还原整个棋盘的状态，只需要知道当前格子所在的列、主对角线和副对角线是否已经被之前的皇后占据即可。我们可以利用棋盘的坐标规律，使用三个一维数组来记录：

列（Column）：直接用 col 索引。
主对角线（Main Diagonal \）：观察坐标会发现，同一条主对角线上的格子，它们的 row - col 是一个常数。为了防止数组越界（出现负数），我们可以统一加上 n − 1，即 row - col + n - 1。
副对角线（Anti Diagonal /）：同一条副对角线上的格子，它们的 row + col 是一个常数。

通过这三个规律，我们只需要三个布尔数组就能在 $O(1)$ 时间内完成校验。

★方法二：基于位运算的回溯

方法一使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 $N$ 个元素，因此集合的空间复杂度是 $O(N)$ 。如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 $O(N)$ 降到 $O(1)$ 。

具体做法是，使用三个整数 $columns$ 、 $diagonals_1$ 和 $diagonals_2$ 分别记录每一列以及两个方向的每条斜线上是否有皇后，每个整数有 $N$ 个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。

那么如何根据每次放置的皇后更新三个整数的值呢？在说具体的计算方法之前，首先说一个例子。

棋盘的边长和皇后的数量 $N=8$ 。如果棋盘的前两行分别在第 $2$ 列和第 $4$ 列放置了皇后（下标从 $0$ 开始），则棋盘的前两行如下图所示。

如果要在下一行放置皇后，哪些位置不能放置呢？我们用 $0$ 代表可以放置皇后的位置， $1$ 代表不能放置皇后的位置。

新放置的皇后不能和任何一个已经放置的皇后在同一列，因此不能放置在第 $2$ 列和第 $4$ 列，对应 $columns=00010100_{(2)}$ 。

新放置的皇后不能和任何一个已经放置的皇后在同一条方向一（从左上到右下方向）的斜线上，因此不能放置在第 $4$ 列和第 $5$ 列，对应 $diagonals_1=00110000_{(2)}$ 。其中，第 $4$ 列为其前两行的第 $2$ 列的皇后往右下移动两步的位置，第 $5$ 列为其前一行的第 $4$ 列的皇后往右下移动一步的位置。

新放置的皇后不能和任何一个已经放置的皇后在同一条方向二（从右上到左下方向）的斜线上，因此不能放置在第 $0$ 列和第 $3$ 列，对应 $diagonals_2=00001001_{(2)}$ 。其中，第 $0$ 列为其前两行的第 $2$ 列的皇后往左下移动两步的位置，第 $3$ 列为其前一行的第 $4$ 列的皇后往左下移动一步的位置。

由此可以得到三个整数的计算方法：

初始时，三个整数的值都等于 $0$ ，表示没有放置任何皇后；
在当前行放置皇后，如果皇后放置在第 $i$ 列，则将三个整数的第 $i$ 个二进制位（指从低到高的第 $i$ 个二进制位）的值设为 $1$ ；
进入下一行时， $columns$ 的值保持不变， $diagonals_1$ 左移一位， $diagonals_2$ 右移一位，由于棋盘的最左列对应每个整数的最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反（对棋盘的移位操作方向是 $diagonals_1$ 右移一位， $diagonals_2$ 左移一位）。

参考分步链接：力扣题解。

每次放置皇后时，三个整数的按位或运算的结果即为不能放置皇后的位置，其余位置即为可以放置皇后的位置。可以通过 (2^n−1) & (∼(columns∣diagonals_1∣diagonals_2)) 得到可以放置皇后的位置（该结果的值为 $1$ 的位置表示可以放置皇后的位置），然后遍历这些位置，尝试放置皇后并得到可能的解。

遍历可以放置皇后的位置时，可以利用以下两个按位与运算的性质：

x & (−x) 可以获得 $x$ 的二进制表示中的最低位的 $1$ 的位置；
x & (x−1) 可以将 $x$ 的二进制表示中的最低位的 $1$ 置成 $0$ 。

具体做法是，每次获得可以放置皇后的位置中的最低位，并将该位的值置成 $0$ ，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。

🔧 代码实现

1、基于集合的回溯

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        
        // 记录列、主对角线、副对角线是否被占用
        vector<bool> cols(n, false);
        vector<bool> diag1(2 * n - 1, false); // 主对角线: row - col + n - 1
        vector<bool> diag2(2 * n - 1, false); // 副对角线: row + col
        
        backtrack(res, board, 0, n, cols, diag1, diag2);
        return res;
    }
    
private:
    void backtrack(vector<vector<string>>& res, vector<string>& board, int row, int n, 
                   vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
        // 成功放置了 N 个皇后，记录结果
        if (row == n) {
            res.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            
            // 如果该位置的列或对角线已经被占用，则跳过
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue;
            }
            
            // 做选择 (放置皇后并标记占用)
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            
            // 进入下一行
            backtrack(res, board, row + 1, n, cols, diag1, diag2);
            
            // 撤销选择 (回溯)
            board[row][col] = '.';
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

2、基于位运算的回溯

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> queens(n, 0); // 记录每一行皇后放置的列索引
        backtrack(res, queens, n, 0, 0, 0, 0);
        return res;
    }

private:
    // row: 当前层数
    // col, diagonals1, diagonals2: 分别记录列、主对角线\、副对角线/的被攻击状态 (1代表被攻击，0代表安全)
    void backtrack(vector<vector<string>>& res, vector<int>& queens, int n, 
                   int row, int col, int diagonals1, int diagonals2) {
        if (row == n) {
            res.push_back(generateBoard(queens, n));
            return;
        }

        // 获取当前行所有可以放置皇后的位置 (将位设为 1 代表可以放置)
        int available = ((1 << n) - 1) & ~(col | diagonals1 | diagonals2);

        // 只要还有可以放置的位置，就不断提取出来尝试
        while (available != 0) {
            // 提取出最低位的 1 作为当前要放置的位置
            int position = available & (-available);
            
            // 将刚提取的 1 从 available 中消除
            available &= (available - 1);
            
            // 计算这个位对应的列索引 (末尾 0 的个数)
            int colIndex = __builtin_ctz(position);
            queens[row] = colIndex;

            // 递归进入下一行：
            // 列限制增加 position
            // diagonals1（主对角线\）限制增加 position 右移，对应数字的位运算是左移一位
            // diagonals2（副对角线/）限制增加 position 左移，对应数字的位运算是右移一位
            backtrack(res, queens, n, row + 1, 
                      col | position, 
                      (diagonals1 | position) >> 1, 
                      (diagonals2 | position) << 1);
        }
    }

    // 辅助函数：根据 queens 数组生成字符串棋盘
    vector<string> generateBoard(const vector<int>& queens, int n) {
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            board[i][queens[i]] = 'Q';
        }
        return board;
    }
};

📊 复杂度分析

1、基于集合的回溯

时间复杂度： $O(N!)$ ，其中 $N$ 是皇后数量。
空间复杂度： $O(N)$ ，其中 $N$ 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 $N$ ，数组的长度为 $N$ ，每个集合的元素个数都不会超过 $N$ 。

2、基于位运算的回溯

时间复杂度： $O(N!)$ ，其中 $N$ 是皇后数量。
空间复杂度： $O(N)$ ，其中 $N$ 是皇后数量。由于使用位运算表示，因此存储皇后信息的空间复杂度是 $O(1)$ ，空间复杂度主要取决于递归调用层数和记录每行放置的皇后的列下标的数组，递归调用层数不会超过 $N$ ，数组的长度为 $N$ 。

🎯 总结

核心思想：发现对角线的判定规律。