N皇后

思路

1. 列，对角线，斜对角线是否可放棋子分别用二进制数表示
2. 每次枚举可放棋子的列，使用lowbit运算

参考链接

https://zhuanlan.zhihu.com/p/22846106

class Solution {
private:
    int cnt = 0;
    int col;
    int dg;
    int udg;
    map<int, int> mp;
public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int lowbit(int x){
        return x & -x;
    }

    void dfs(int x, int &n){
        int avail = col & (dg >> x) & (udg >> (n-x));
        for(int y=avail;y;y -= lowbit(y)){
            if(x == n-1) cnt++;
            else{
                int t = mp[lowbit(y)];
                col -= 1 << t;
                dg -= 1 << (x + t);
                udg -= 1 << (t - x + n);
                dfs(x+1, n);
                col += 1 << t;
                dg += 1 << (x + t);
                udg += 1 << (t - x + n);
            }
        }
    }

    int Nqueen(int n) {
        for(int i=0;i<n;i++) mp[1 << i] = i;
        col = (1 << n) - 1;
        dg = udg = (1 << (2*n)) - 1;
        dfs(0, n);
        return cnt;
    }
};