52. N-Queens II

T: O(n^n) without pruning, upper bound
S: O(n)

class Solution {
    public int totalNQueens(int n) {
        int[] queen = new int[n];
        boolean[] visitedCol = new boolean[n];
        boolean[] visitedSumDiagonal = new boolean[2*n-1];
        boolean[] visitedDiffDiagonal = new boolean[2*n-1];

        return dfs(n, queen, 0, visitedCol, visitedSumDiagonal, visitedDiffDiagonal);
    }
    private int dfs(int n, int[] queen, int row, boolean[] visitedCol, boolean[] visitedSumDiagonal, boolean[] visitedDiffDiagonal) {
        if (row == n) {
            return 1;
        }
        int count = 0;
        for (int col = 0; col < n; col++) {

            if (visitedCol[col]) {
                continue;
            }
            if (visitedSumDiagonal[row+col]) {
                continue;
            }
            if (visitedDiffDiagonal[col - row + n - 1]) {
                continue;
            }

            // queue[row] = col; actually no use in this problem, we only need count, no need to record the Q poistion
            visitedCol[col] = true;
            visitedSumDiagonal[row+col] = true;
            visitedDiffDiagonal[col - row + n - 1] = true;
            
            count += dfs(n, queen, row + 1, visitedCol, visitedSumDiagonal, visitedDiffDiagonal);

            visitedCol[col] = false;
            visitedSumDiagonal[row+col] = false;
            visitedDiffDiagonal[col - row + n - 1] = false;
        }
        return count;
    }
}


/***


00 01 02
10 11 12
20 21 22


-2 to 2
so add (n-1, 3 -1 = 2)

0 to 4
---------

this one utilize

queue[row] = col
to record the place we put 'Q' (no use in this problem, only need the result count)

so
when we place 'Q' in queue[row] = col
which also record for this row, col has put in col, anti-diagonal, diagonal position

visitedCol[col] = true;
and
visitedSumDiagonal[row+col] = true (means anti-diagonal poistion) (2n+1 space)
visitedDiffDiagonal[col - row + n - 1] (why? because col - row will have negtive number, so add n-1 make it positive)

ex: (2, 0), 0 - 2 = -2, (0,2) = 2   (range is -2 to 2), so add n-1 (3-1 =2 ) -> range become 0 to 4

in this way, we can use visitedCol[col], visitedSumDiagonal[row+col], visitedDiffDiagonal[col - row + n - 1]
to check is this row, col has put 'Q'

T: O(n^n) without pruning, upper bound
S: O(n)
 */