The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the&nbsp;n-queens puzzle.

&nbsp;
Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.


Example 2:

Input: n = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= n &lt;= 9


class Solution:
    def totalNQueens(self, n: int) -> int:
        res=0
        #用于存放结果
        pdia=set()
        ndia=set()
        col=set()

        def backtrack(r):
            #利用r作为一种计数，表示目前所在的行数
            if r==n:
            #判断已经完成棋盘，返回结果
                nonlocal res
                res+=1
                return
            for c in range(n):
                #对于n行n列的棋盘，每次在每一行我们尝试n种选择，
                #即每个岔路口有n条路线
                if (r+c) in pdia or (r-c) in ndia or c in col:
                    #如果在同一对角线，或同一列，则不符合要求
                    continue
                col.add(c)
                pdia.add(r+c)
                ndia.add(r-c)
                
                backtrack(r+1)
                
                col.remove(c)
                pdia.remove(r+c)
                ndia.remove(r-c)

        backtrack(0)
        return res
class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        boolean col[] = new boolean[n];
        boolean diag[] = new boolean[2*n-1];
        boolean rdiag[] = new boolean[2*n-1];

        countSolution(n,col, diag, rdiag, 0);
        return count;

    }
    void countSolution(int n, boolean[] col, boolean[] diag, boolean[] rdiag, int r ){
        if (r == n ){
            count++;
            return;
        }

        for(int c = 0 ; c < n; c++){
            if(col[c] == false && diag[r+c] == false && rdiag[r-c+n-1] == false){
                col[c] = true;
                diag[r+c] = true;
                rdiag[r-c+n-1] = true;
                countSolution(n, col, diag, rdiag, r+1);
                col[c] = false;
                diag[r+c] = false;
                rdiag[r-c+n-1] = false;
            }
        }

    }
}
class Solution {
public:
    int totalNQueens(int n) {
    vector<bool> col(n), diag(2*n-1), anti_diag(2*n-1);
    return solve(col, diag, anti_diag, 0);
}

int solve(vector<bool>& col, vector<bool>& diag, vector<bool>& anti_diag, int row) {
    int n = size(col), count = 0;
    if(row == n) return 1;
    for(int column = 0; column < n; column++)
        if(!col[column] && !diag[row + column] && !anti_diag[row - column + n - 1]){
            col[column] = diag[row + column] = anti_diag[row - column + n - 1] = true;
            count += solve(col, diag, anti_diag, row + 1);
            col[column] = diag[row + column] = anti_diag[row - column + n - 1] = false;
        }
    return count;
}
};
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
	// Keep track of columns with queens
    const cols = new Set();
	// Keep track of positive slope diagonal by storing row number + column number
    const posDiag = new Set();
	// Keep track of negative slope diagonal by storing row number - column number
    const negDiag = new Set();
	// Count of valid boards
    let count = 0;
    
    const backtrack = function(r) {
		// Base case to end recursion, we have traversed board and found valid position in each row
        if(r === n) {
            count += 1;
            return;
        }
		// Loop through each column to see if you can place a queen
        for(let c = 0; c < n; c++) {
			// invalid position check, if position in set we cannot place queen here
            if(cols.has(c) || posDiag.has(r+c) || negDiag.has(r-c)) continue;
            
			// add new queen to sets
            cols.add(c);
            posDiag.add(r+c);
            negDiag.add(r-c);
            
			// backtrack
            backtrack(r+1);
            
			// remove current position from sets because backtracking for this position is complete
            cols.delete(c);
            posDiag.delete(r+c);
            negDiag.delete(r-c);
        }
    }
    
    backtrack(0);
    return count;
};
N-Queens II