My Java solution using Backtracking


  • 1
    J
    public class Solution {
        private List<List<String>> result;
        private int N;
        private int[] cols; // record the columns for each row's queen
    
        public List<List<String>> solveNQueens(int n) {
            result = new ArrayList<>();
            N = n;
            cols = new int[N];
            solve(0);
            return result;
        }
    
        private void solve(int row) {
            for (int col = 0; col < N; col++) {  // try each column 
                cols[row] = col;
                if (isPromising(row)) {    
                    if (row == N - 1)
                        result.add(generateBoard());
                    else
                        solve(row + 1);
                }
            }
        }
    
        private boolean isPromising(int row) {
            for (int prevRow = 0; prevRow < row; prevRow++) {
                if (cols[prevRow] == cols[row] // check vertical
                    || Math.abs(cols[prevRow] - cols[row]) == row - prevRow) // check diagonal
                    return false;
            }
            return true;
        }
    
        private List<String> generateBoard() {
            List<String> board = new ArrayList<>();
    
            for (int row = 0; row < N; row++) {
                StringBuilder builder = new StringBuilder();
                for (int col = 0; col < N; col++) {
                    if (col == cols[row]) builder.append("Q");
                    else builder.append(".");
                }
                board.add(builder.toString());
            }
            return board;
        }
    }
    

Log in to reply
 

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