Java AC solution without keeping track of the exact positions of the queens placed so far.


  • 0
    X
    public class Solution {
        public int totalNQueens(int n) {
            return totalNQueens(n, 0, new boolean[n], new boolean[2*n-1], new boolean[2*n-1]);
        }
    
        public int totalNQueens(int n, int row, boolean[] colHasQ, boolean[] diag1HasQ, boolean[] diag2HasQ) {
            if (row == n) {
                return 1;
            }
            int ret = 0;
            for (int i = 0; i < n; i++) {
                int diag1Index = i + row;           // in the set of left top to right bottom diagonal, from a1 to h8  
                int diag2Index = (n - 1 - i) + row; // in the set of left bottom to right top diagonal, from h1 to a8 
                if (!colHasQ[i] && !diag1HasQ[diag1Index] && !diag2HasQ[diag2Index]) {
                    colHasQ[i] = diag1HasQ[diag1Index] = diag2HasQ[diag2Index] = true;
                    ret += totalNQueens(n, row + 1, colHasQ, diag1HasQ, diag2HasQ);
                    colHasQ[i] = diag1HasQ[diag1Index] = diag2HasQ[diag2Index] = false;
                }
            }
            return ret;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.