n皇后问题

如果按列从左向右放置皇后，需要用三个数组记录之前已经用过的行，主对角线，次对角线。

可以用状态压缩的方法简化问题。用三个数的二进制表示已经用过的行和两条对角线，

LC52. N-Queens II 输出n皇后解的个数

class Solution {
public:
    int cnt = 0;
    int n;
    void dfs(int dep, int r, int s1, int s2) {
        if (dep == n) {
            cnt++;
            return;
        }
        for (int i = 0; i < n; ++i) {
            int j = 1 << i;
            if ((j & r) || (j & s1) || (j & s2)) continue;
            dfs(dep + 1, j | r, (j | s1) << 1, (j | s2) >> 1);
        }
    }
    int totalNQueens(int n) {
        cnt = 0;
        this -> n = n;
        dfs(0, 0, 0, 0);
        return cnt;
    }
};

LC51. N-QueensLC 输出n皇后所有的解

class Solution {
public:
    int n;
    vector<string> g;
    vector<vector<string>> res;
    void dfs(int dep, int r, int s1, int s2) {
        if (dep == n) {
            res.push_back(g);
            return;
        }
        for (int i = 0; i < n; ++i) {
            int j = 1 << i;
            if ((r & j) || (s1 & j) || (s2 & j)) continue;
            g[i][dep] = 'Q';
            dfs(dep + 1, r | j, (s1 | j) << 1, (s2 | j) >> 1);
            g[i][dep] = '.';
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        this -> n = n;
        g.assign(n, string(n, '.'));
        dfs(0, 0, 0, 0);
        return res;
    }
};