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;

        } 
    }
}