N皇后--位运算解法

位运算

首先要熟悉位运算，定义整数row，cols，diag1和diag2来表示行，列、对角线的占用情况。cols的情况很简单，0000,0101最终到1111表示每一列是否有皇后占用。

关于对角线，就拿n=4的情况来举例说明，对角线实际上是有7条的，但对于我们遍历的每一行，只有4个格子 也就是对应了4条对角线而已。所以我们也只需计算4位数字，后面的左移 右移操作也跟这个有关。

先展示代码如下：

class NQueens {
public:
    vector> solveNQueens(int n) {
        vector> result;
        vector board(n, 0);  // 用来表示每行放在哪一列
        solve(result, board, 0, 0, 0, 0, n);
        return result;
    }

private:
    void solve(vector>& result, vector& board, int row, int cols, int diag1, int diag2, int n) {
        if (row == n) {
            // 找到一个解，构建棋盘并添加到结果
            vector boardStr(n, string(n, '.'));
            for (int i = 0; i < n; i++) {
                boardStr[i][board[i]] = 'Q';
            }
            result.push_back(boardStr);
            return;
        }

        int availablePositions = ~(cols | diag1 | diag2) & ((1 << n) - 1); // 可用位置
        while (availablePositions) {
            int pos = availablePositions & -availablePositions;  // 获取最低位的1
            availablePositions &= availablePositions - 1;  // 移除最低位的1
            int col = __builtin_ctz(pos);  // 获取最低位1的位置（即当前列）
            board[row] = col;
            solve(result, board, row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1, n);
        }
    }
};
                

位运算疑惑解答

1. availablePositions: 该部分表示当前行可以操作的列位置。通过将cols、diag1、diag2三者合并，并取反，我们能够识别出可以使用的位置。接着，& ((1 << n) - 1)部分是进行掩码操作，将其限制为n位。
2. while循环: 该循环用于处理所有可以操作的位置，直到availablePositions变为0000。我们从右往左处理每一个可操作的位置。
3. pos的获取: 通过availablePositions & -availablePositions，我们能够获取最低位的1，这样可以从最低位开始进行递归回溯。
4. 移除最低位的1: 一旦处理完最低位的1后，我们通过availablePositions &= availablePositions - 1来去除它，继续处理下一个位置。
5. col的计算: 使用__builtin_ctz(pos)来获取最低位1的位置，将其转化为十进制数。
6. 递归调用: 在递归中，cols、diag1、diag2会根据放置皇后的列和对角线进行更新。

补充说明: 当n非常大时，位运算的掩码能够显著提升计算效率，避免进行不必要的大整数运算。