Concise JAVA solution based on DFS


  • 0

    Explanation

    The basic solution is similar as N-Queens, the difference is using HashSet to validate column, instead of for loop. In this way, it will improve validation time complexity from O(n) to O(1). Another trick is diagonal checking: 1) 45° diagonal=>y1-y2=x1-x2=>y1-x1=y2-x2; 2) 135° diagonal=>y1-y2=-1*(x1-x2)=>y1+x1=y2+x2. Thanks for this great idea from Alex, DFS solution as the following:

    HashSet<Integer> cols = new HashSet<Integer>();	 // Used columns
    HashSet<Integer> diag1 = new HashSet<Integer>(); // 45° diagonal
    HashSet<Integer> diag2 = new HashSet<Integer>(); // 135° diagonal 
    
    public int totalNQueens(int n) {
       return DFS(0, 0, n);
    }	
    
    int DFS(int row, int count, int n) {
    	if (row == n) 
    		return count + 1;
    			
    	for (int col = 0; col < n; col++) {
    		if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) 
    			continue;
    		cols.add(col);
    		diag1.add(row - col); 
    		diag2.add(row + col);
    		count = DFS(row + 1, count, n);
    		cols.remove(col); 
    		diag1.remove(row - col); 
    		diag2.remove(row + col);
    	}
    	return count;
    }
    

Log in to reply
 

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