Concise JAVA solution based on DFS


  • 5

    Explanation

    The basic idea is to check possible columns row by row based on DFS: If the column is already used or the column is on 45° /135° diagonals with the placed queens, then ignore it, otherwise place a queen on it and keep DFS procedure. As the following:

    public List<List<String>> solveNQueens(int n) {
    	List<List<String>> res = new LinkedList<List<String>>();
    	int[] usedCols = new int[n];// usedCols[i]: Column of the queen in row i
    	Arrays.fill(usedCols, -1);
    	DFS(usedCols, 0, res);
    	return res;
    }    
    
    void DFS(int[] usedCols, int row, List<List<String>> res) {
    	int n = usedCols.length;
    	if (row == n) {
    		res.add(drawGrids(usedCols));
    		return;
    	}     	
    
    	// Check Possible columns for the inputed row.
    	for (int col = 0; col < n; col++) {
    		if (isValid(usedCols, row, col)) {
    			usedCols[row] = col;
    			DFS(usedCols, row + 1, res);// Move on to the next row	
    		}
    	}
    }
    
    // Check if the column is valid to place queen for the row.
    boolean isValid(int[] usedCols, int row, int col) {
    	for (int i = 0; i < row; i++) {
    		// Excludes used columns and diagonal positions 
    		// (x2-x1)/(y2-y1) == 1 or -1
    		if (usedCols[i] == col || row - i == Math.abs(col - usedCols[i]))    			
    			return false;
    	}
    	return true;
    }
    
    List<String> drawGrids(int[] usedCols) {
    	List<String>res = new LinkedList<String>();
    	for (int i : usedCols) {
        	char[] line = new char[usedCols.length];
        	Arrays.fill(line, '.');	    	
        	line[i] = 'Q'; 
        	res.add(String.valueOf(line));
    	}    	
    	return res;
    }

Log in to reply
 

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