Java easy to understand solution 5ms


  • 0
    W
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new ArrayList<>();
            char[][] board = new char[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    board[i][j] = '.';
                }
            }
            backtracking(res, board, 0, n);
            return res;
        }
        
        public void backtracking(List<List<String>> res, char[][] board, int curCol, int n) {
            if (curCol == n) {
                List<String> sol = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    sol.add(new String(board[i]));
                }
                res.add(sol);
                return;
            }
    
            for (int row = 0; row < n; row++) {
                if (isValid(board, row, curCol, n)) {
                    placeQueen(board, row, curCol);
                    backtracking(res, board, curCol + 1, n);
                    removeQueen(board, row, curCol);
                }
            }
        }
        
        public boolean isValid(char[][] board, int row, int col, int n) {
            for (int i = 0; i < col; i++) {
                if (board[row][i] == 'Q') return false;
            }
            int startRow = row, startCol = col;
            while (--startRow >= 0 && --startCol >= 0) {
                if (board[startRow][startCol] == 'Q') return false;
            }
            startRow = row;
            startCol = col;
            while (++startRow < n && --startCol >= 0) {
                if (board[startRow][startCol] == 'Q') return false;
            }
            return true;
        }
        
        public void placeQueen(char[][] board, int row, int col) {
            board[row][col] = 'Q';
        }
        
        public void removeQueen(char[][] board, int row, int col) {
            board[row][col] = '.';
        }
    }

Log in to reply
 

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