class Solution {
public:
    vector<int> path;  // 记录每一行第几个位置放皇后
    int res = 0;
    void dfs(int n, int x)
    {
        if(x == n) res ++; 
        for(int y = 0; y < n; y ++ ){
            bool flag = false;
            for(int i = 0; i < x; i ++ )  // 判断同一列
                if(path[i] == y) flag = true;
            if(flag) continue;
            for(int i = 0; i < x; i ++ ){  // 判断对角线
                if(path[i] - i == y - x) flag = true;
                if(i - path[i] == x - y) flag = true;
                if(path[i] + i == x + y) flag = true;
            }
            if(flag) continue;
            path.push_back(y);
            dfs(n, x + 1);
            path.pop_back();
        }
    }
    int totalNQueens(int n) {
        dfs(n, 0);
        return res;
    }
};