Most Elegant Java Simple Solution with Explanation


  • 0
    M

    Use an array named "colForRow[i]= j" , which represent put a queen at ith col and jth row (index starting from 0). Other explanations are in comments.

    public int totalNQueens(int n) {
    
    	int[] colForRow = new int[n];
    
    	return totalNQueensHelper(n, colForRow, 0);
    }
    
    // This method count the number of successful deploy.
    // Each time it tries every possible number from 0 to n to put in posth
    // position.
    // If this put does not violate rules, continue to pos+1 and accumulate
    // count.
    private int totalNQueensHelper(int n, int[] colForRow, int pos) {
    
    	if (pos == n)
    		return 1;
    	int count = 0;
    	for (int i = 0; i < n; i++) {
    		if (totalNQueenCheck(colForRow, pos, i)) {
    			colForRow[pos] = i;
    			count += totalNQueensHelper(n, colForRow, pos + 1);
    		}
    	}
    	return count;
    }
    
    // This method checks whether trying to put val in pos is a violation.
    private boolean totalNQueenCheck(int[] colForRow, int pos, int val) {
    
    	for (int i = 0; i < pos; i++) {
    		int diff = Math.abs(colForRow[i] - val);
    		if (diff == 0 || diff == pos - i)
    			return false;
    	}
    
    	return true;
    }

Log in to reply
 

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