Java Solution using Backtracking


  • 0
    Y

    Using one dimensional array pos[row] , row=0,1,...,n-1 to save the column position for that row.

    class Solution {
        
        private int count=0;
        
        public int totalNQueens(int n) {
            
            // save the col position of queens
            int[] pos = new int[n];
            NQueenHelper(pos, 0, n);
            return count;
            
        }
        
        private void NQueenHelper(int[] pos, int row, int n) {
            
            if (row == n) {
                count++;
                return;
            }
            for (int col=0; col<n; col++) {
                if (isValid(pos, row, col, n)) {
                    pos[row] = col;
                    NQueenHelper(pos, row+1, n);
                    pos[row] = 0;
                }
            }
            
        }
        
        private boolean isValid(int[] pos, int row, int col, int n) {
            
            // any row has a queen in this col
            for (int i=0; i<row; i++) {
                if (pos[i] == col) {
                    return false;
                }
            }
            // any queen in the 45 diagonal direction
            for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
                if (pos[i] == j) {
                    return false;
                }
            }
            // any queen in the 135 diagonal direction
            for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
                if (pos[i] == j) {
                    return false;
                }
            }
            return true;
            
        }
        
    }
    

Log in to reply
 

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