## 52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n× n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

``````Input:
4

Output: 2

Explanation:
There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
``````

Thoughts:

1. Backtracking:
1. Having 3 boolean vectors, col, diag, anti-diag to mark where there is a queen on the same column, same diagnal, or same anti-diagnal. for col, the level set is col; for diagnal: the level set is col - row + n; for antidiagnal: the level set is row + col.
2. for each row, expanding the cols and check where there is a queen in col, diag, and anti-diag, then recursively call the backtracking until the row reaches the end or did get in depth due to the disqualification of the results.

Code:

``````class Solution {
int count = 0;
public int totalNQueens(int n) {
boolean [] cols = new boolean[n], diag = new boolean[2*n], antiDiag = new boolean[2*n];
backtrack(0,n,cols,diag,antiDiag);
return count;
}

private void backtrack(int row, int n, boolean[] cols, boolean[]diag, boolean[]antiDiag){
if(row == n) count++;

for(int col = 0; col < n; col++){
int d = row - col + n;
int aD = row + col;
if(cols[col] || diag[d] || antiDiag[aD]) continue;

cols[col] = true; diag[d] = true; antiDiag[aD] = true;
backtrack(row + 1, n, cols, diag, antiDiag);
cols[col] = false; diag[d] = false; antiDiag[aD] = false;

}
}
}
``````