52. N-Queens II

Problem:

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

6/18/2018 update:
Using N-Queens code template

class Solution {
    int res;
    public int totalNQueens(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        dfs(queens, 0);
        return res;
    }
    
     private void dfs(int[] queens, int row) {
        if (row == queens.length) {
            res++;
            return;
        }
        
        for (int i = 0; i < queens.length; i++) {
            if (isValid(queens, row, i)) {            
                queens[row] = i;
                dfs(queens, row + 1);   
                queens[row] = -1;
            }
        }
    }
    
    private boolean isValid(int[] queens, int row, int col) {
        // i is row
        for (int i = 0; i < row; i++) {
            if (queens[i] == col)
                return false;
            else if (Math.abs(queens[i] - col) == Math.abs(row - i))
                return false;
        }
        return true;
    }
}

------------------------------------------------------------------------------------------------------------------------------------  
Analysis:

DFS, each level is a row. When checking the valid spot, no need to check row. If two queens are on the diagonal \, q1.col - q1.row == q2.col - q2.col. If they are on /, q1.col + q1.row == q2.col + q2.col.

Solution:

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] d1 = new boolean[2*n]; // \
        boolean[] d2 = new boolean[2*n]; // /
        helper(0, n, cols, d1, d2);
        return count;
    }

    private void helper(int row, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
        if (row == n) {
            count++;
        }

        for (int col = 0; col < n; col++) {
            int d1Index = col - row + n;
            int d2Index = col + row;
            if (cols[col] || d1[d1Index] || d2[d2Index]) continue;
            cols[col] = true; d1[d1Index] = true; d2[d2Index] = true;
            helper(row + 1, n, cols, d1, d2);
            cols[col] = false; d1[d1Index] = false; d2[d2Index] = false;
        }
    }
}