1class Solution {2    public List<List<String>> solveNQueens(int n) {3        char[][] board = new char[n][n];4        for (char[] row : board) Arrays.fill(row, '.');5        List<List<String>> result = new ArrayList<>();6        search(0, board, new boolean[n], new boolean[2*n-1], new boolean[2*n-1], result);7        return result;8    }9    private void search(int row, char[][] board, boolean[] columns, boolean[] down, boolean[] up, List<List<String>> result) {10        int n = board.length;11        if (row == n) {12            List<String> solution = new ArrayList<>();13            for (char[] line : board) solution.add(new String(line));14            result.add(solution);15            return;16        }17        for (int col = 0; col < n; col++) {18            int d = row - col + n - 1, u = row + col;19            if (columns[col] || down[d] || up[u]) continue;20            board[row][col] = 'Q';21            columns[col] = down[d] = up[u] = true;22            search(row + 1, board, columns, down, up, result);23            board[row][col] = '.';24            columns[col] = down[d] = up[u] = false;25        }26    }27}