设计一种算法,打印 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%的用户
Comments | 1 条评论