Java easy-understanding solution using backtracking.


  • 1
    Y
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        placeQueens(0, new Integer[n], result, n);
        
        return result;
    }
    
    private void placeQueens(int row, Integer[] columns, List<List<String>> result, int n) {
        if(row == n) result.add(construct(columns));
        for(int col = 0; col < n; col++) {
            if(checkValid(columns, row, col)) {
                columns[row] = col;
                placeQueens(row + 1, columns, result, n);
            }
        }
    }
    
    private boolean checkValid(Integer[] columns, int row1, int col1) {
        for(int row2 = 0; row2 < row1; row2++) {
            int col2 = columns[row2];
            
            if(col1 == col2) return false;
            
            int colDis = Math.abs(col2 - col1);
            
            int rowDis = row1 - row2;
            if(colDis == rowDis) return false;
        }
        return true;
    }
    
    private List<String> construct(Integer[] columns) {
        List<String> rst = new ArrayList<>();
        for(int row = 0; row < columns.length; row++) {
            int col = columns[row];
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < columns.length; i++) {
                if(i == col) sb.append('Q');
                else sb.append('.');
            }
            rst.add(sb.toString());
        }
        return rst;
    }

  • 0
    S

    well done!!!!!!!!


Log in to reply
 

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