51. N-Queens

Leetcode link

前言

这是一道经典的 hard 题目

题目给我们一个整数 n，表示一个 n * n 的棋盘，我们的目标在于将 n 个皇后放进这个棋盘中

放置的规则就是：皇不见皇（皇后不能在彼此的同一行、同一列、同一斜线上）

暴力破解显然是不可行的，我们考虑回溯的办法

首先我们需要一个数组 queens 来记录皇后在每一行的坐标

然后我们依次在每一行放一个皇后，每个皇后的位置都要符合皇不见皇的原则

直到放到最后一行的时候，我们就能找出其中一个解了

为了要让放置的每一个皇后都能快速判断是否符合皇不见皇原则，我们有两种方法

详情见下方解题思路

解题思路——集合

• TC: O(n!)
• SC: O(n)，其中保存皇后信息的空间复杂度是 O(n)

对每一个新行来说，有三种可能会不符合皇不见皇原则：

• 跟之前的皇后在同一列上
• 跟之前的皇后在同一斜线（右上 - 左下）上
• 跟之前的皇后在同一反斜线（左上 - 右下）上

所以我们可以通过三个集合来记录这三种可能：

• col：记录之前皇后放置的列
• slash：记录之前皇后放置的行减列的差（因为在同一斜线上这个值是一样的）
• backslash：记录之前皇后放置的行与列的和（同理，在同一反斜线上这个值是一样的）

C++

class Solution {
public:


    vector<vector<string>> solveNQueens(int n) {
        // 存放最后的所有结果
        vector<vector<string>> result;
        // 存放其中一种结果
        vector<int> queens(n, -1);
        // 存放已经被其他 queen 占用的列
        unordered_set<int> col;
        // 存放已经被其他 queen 占用的斜线（右上 - 左下）
        unordered_set<int> slash;
        // 存放已经被其他 queen 占用的反斜线（左上 - 右下）
        unordered_set<int> backslash;
        backtrack(n, 0, result, queens, col, slash, backslash);

        return result;
    }

    // 回溯法找到可以符合要求的排列
    void backtrack(int n, int row, vector<vector<string>> &result, vector<int> &queens, unordered_set<int> &col, unordered_set<int> &slash, unordered_set<int> &backslash) {
        if(row == n) {
            // 表示找到了其中一种
            vector<string> board = generateBoard(queens, n);
            result.push_back(board);
        } else {
            // 遍历第 row 行的所有列
            for(int i=0;i<n;i++) {
                if(col.find(i) != col.end()) {
                    // 如果遍历到已经被占用的列
                    continue;
                }
                // 如果是在同一条反斜线（左上-右下）上，行减去列的差是一样的
                int diff = row - i;
                if(backslash.find(diff) != backslash.end()) {
                    continue;
                }
                // 如果是在同一条斜线（右上-左下）上，行与列的和是一样的
                int sum = row + i;
                if(slash.find(sum) != slash.end()) {
                    continue;
                }

                queens[row] = i;
                col.insert(i);
                slash.insert(sum);
                backslash.insert(diff);

                backtrack(n, row+1, result, queens, col, slash, backslash);

                queens[row] = -1;
                col.erase(i);
                slash.erase(sum);
                backslash.erase(diff);
            }
        }
    }

    // 根据找到的排列构造返回结果
    vector<string> generateBoard(vector<int> &queens, int n) {
        vector<string> board;
        for(int i=0;i<n;i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

解题思路——位运算

• TC: O(n!)
• SC: O(n)，其中保存皇后信息的空间复杂度是 O(1)

上一个解法使用了三个集合，用了 O(n) 的空间复杂度，这个解法我们用位运算来把这部分复杂度减少到 O(1)

我们这次使用三个整数 col、slash、backslash，这三个整数的 n 个二进制位代表了可不可以放置新的皇后

如果可以放置皇后则为 0，不可以则为 1.

举个例子：

假设我们今天在第 i 行把皇后放在了第 j 列，那么这个时候我们可以先将这三个整数的第 j 位设为1

然后进入到第 i + 1 行，我们要先做三件事：

• col 不变
• slash 左移一位
• backslash 右移一位

这样我们要放置新皇后的时候，就可以用 来获取可用的位置

C++

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        // 存放最后的所有结果
        vector<vector<string>> result;
        // 存放其中一种结果
        vector<int> queens(n, -1);

        backtrack(n, 0, result, queens, 0, 0, 0);

        return result;
    }

    void backtrack(int n, int row, vector<vector<string>> &result, vector<int> &queens, int col, int slash, int backslash) {
        if(n == row) {
            vector<string> board = generateBoard(queens, n);
            result.push_back(board);
        } else {
            int available =((1 << n) - 1) & (~(col | slash | backslash));
            while(available!=0) {
                // 取得最低位的 1
                int position = available & (-available);
                // 将最低位的 1 置 0
                available = available & (available - 1);
                // 取得 position 末尾 0 的个数，同时也是皇后可以放置的位置
                queens[row] = __builtin_ctz(position);

                backtrack(n, row+1, result, queens, col | position, (slash|position) << 1, (backslash | position) >>1);

                queens[row] = -1;
            }
        }
    }

    // 根据找到的排列构造返回结果
    vector<string> generateBoard(vector<int> &queens, int n) {
        vector<string> board;
        for(int i=0;i<n;i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};