Share my very readable java solution


  • 0
    O
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            char[][] board = new char[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    board[i][j] = '.';
                }
            }
            boolean[] diagonal = new boolean[2 * n - 1];
            boolean[] antidiagonal = new boolean[2 * n - 1];
            boolean[] column = new boolean[n];
            List<List<String>> result = new ArrayList<>();
            
            dfs(result, 0, column, diagonal, antidiagonal, board);
            return result;
        }
        
        public void dfs(List<List<String>> result, int row, boolean[] column, boolean[] diagonal, boolean[] antidiagonal, char[][] board) {
            int len = column.length;
            if (row == len) {
                List<String> buffer = new ArrayList<>();
                for (char[] str : board) {
                    buffer.add(new String(str));
                }
                result.add(buffer);
                return;
            }
            
            for (int col = 0; col < len; ++col) {
                int diagIndex = col - row + len - 1;
                int antiIndex = col + row;
                if (!column[col] && !diagonal[diagIndex] && !antidiagonal[antiIndex]) {
                    board[row][col] = 'Q';
                    column[col] = diagonal[diagIndex] = antidiagonal[antiIndex] = true;
                    dfs(result, row + 1, column, diagonal, antidiagonal, board);
                    board[row][col] = '.';
                    column[col] = diagonal[diagIndex] = antidiagonal[antiIndex] = false;
                }
            }
        }
    }
    

Log in to reply
 

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