设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

输入：4
输出：[[".Q..","…Q","Q…","..Q."],["..Q.","Q…","…Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "…Q",
  "Q…",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q…",
  "…Q",
  ".Q.."]
]

class Solution {
    public static List<List<String>> solveNQueens(int n) {
        int[] arr = new int[n];
        List<List<String>> res = new ArrayList<>();

        check(0, n, arr, res);
        return res;
    }

    public static void check(int num, int max, int[] arr, List<List<String>> res) {
        if(num == max) {
            List<String> list = print(arr);
            res.add(list);
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[num] = i;
            if (judge(num, arr)) {
                check(num+1, max, arr, res);
            }
        }
    }

    public static boolean judge(int num, int[] arr) {
        for (int i = 0; i < num; i++) {
            if (arr[i] == arr[num] || (i + arr[i])==(num+arr[num]) || (i-arr[i])==(num-arr[num])) {
                return false;
            }
        }
        return true;
    }

    public static List<String> print(int[] arr) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            String str = "";
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == j) {
                    str += "Q";
                } else {
                    str += ".";
                }
            }
            list.add(str);
        }
        return list;
    }
}

执行用时：4 ms, 在所有 Java 提交中击败了39.50%的用户

内存消耗：42.3 MB, 在所有 Java 提交中击败了13.65%的用户