class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        if (n == 0) return ans;
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                board[i][j] = '.';
            }
        }

        dfs(board, n, 0, ans);

        return ans;
    }

    private void dfs(char[][] board, int n, int col, List<List<String>> ans){
        if (col == n){
            ans.add(construct(board));
            return;
        }

        for (int row = 0; row < n; row++){
            if (valid(board, row, col)){
                board[row][col] = 'Q';
                dfs(board, n, col + 1, ans);
                board[row][col] = '.';
            }
        }
    }

    private boolean valid(char[][] board, int row, int col){
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < col; j++){
                if (board[i][j] == 'Q' && (i == row || i + col == j + row || i + j == row + col) ) return false;
            }
        }

        return true;
    }

    private List<String> construct(char[][] board){
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < board.length; i++){
            String str = new String(board[i]);
            ans.add(str);
        }

        return ans;
    }
}