回溯-N皇后问题

状态：已经填好的行数，每一行填在了哪些位置

选择: 最多N种选择

路径：放置了Queue的位置的列表；

结果集：列表的列表

结束条件： 已经把所有的行数填写完；

class Solution {
public:
    int res;
    int Nqueen(int n) {
        res = 0;
        dfs(0, n, 0, 0, 0);
        return res;
    }

    void dfs(int u, int n, int col, int pie, int na) {
        if (u == n) {
            res++;
            return;
        }

        for (int j = 0; j < n; ++j) {
            //用位运算来记录状态
            //注意对角线的技巧
            //左上 y = x + b;  b = (y - x) 来表现一条线，y - x有可能是负数，为了简化，统一加上n，所以b = (n + u - j)
            //右下 y = -x + b; b = (y + x) 来表现一条线！！
            if ((col & 1 << j) || (pie & (1 << (n + u - j))) || (na & (1 << (u + j))))
                continue;
            //col，pie，na都是局部变量，不用保存现场
            dfs(u + 1, n, col | (1 << j), pie | (1 << (n + u - j)), na  | (1 << (u + j)));
        }
    }
};