52

class Solution {
public:
    int ans;
    bool visd[30], visad[30], vis[30];

    int totalNQueens(int n) {
        backtrack(0, n);
        return ans;
    }

    void backtrack(int col, int n){
        if(col == n){
            ans++;
            return;
        }
        for(int row=0; row<n; row++){
            if(!vis[row] && !visd[row-col+n-1]  && !visad[row+col]){
                vis[row] = visd[row-col+n-1] = visad[row+col] = true;
                backtrack(col+1, n);
                vis[row] = visd[row-col+n-1] = visad[row+col] = false;
            }
        }
    }
};