class Solution {
    public List<List<String>> solveNQueens(int n) {
                final List<List<String>> lists = new ArrayList<>();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = Integer.MIN_VALUE;
        }
        queen(lists, nums, 0);
        return lists;
    }

    public void queen(List<List<String>> lists, int[] nums, int cur){
        if(cur == nums.length){
            List<String> list = new ArrayList<>();
            StringBuilder sb ;
            for(int i = 0; i < nums.length; i++){
                sb = new StringBuilder();
                for(int j = 0; j < nums.length; j++){
                    if(j == nums[i]){
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                list.add(sb.toString());
            }
            lists.add(list);
            return ;
        }
        for(int col = 0; col < nums.length; col++){
            nums[cur] = col;
            boolean flag = true;
            for(int row = 0; row < cur; row++){
                if(nums[row] == col || Math.abs(col - nums[row]) == cur - row){
                    flag =false;
                    break;
                }
            }
            if(flag){
                queen(lists, nums, cur+1);
            }
        }
    }
}