LeetCode52-N皇后II

题目链接

英文链接:https://leetcode.com/problems/n-queens-ii/

中文链接:https://leetcode-cn.com/problems/n-queens-ii/

题目详述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

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

题目详解

  • N 皇后问题。
  • LeetCode51-N皇后 是求解决方案,本题是求解决方案的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class LeetCode_00052 {

public int totalNQueens(int n) {
boolean[] col = new boolean[n]; // 当前列
boolean[] dia1 = new boolean[2 * n - 1]; // 对角线 1 横纵坐标相加为定值
boolean[] dia2 = new boolean[2 * n - 1]; // 对角线 2 横纵坐标相减为定值
return dfs(n, 0, col, dia1, dia2);
}

private int dfs(int n, int r, boolean[] col, boolean[] dia1, boolean[] dia2) {
if (r == n) {
return 1;
}
int res = 0;
for (int i = 0; i < n; ++i) {
if (!col[i] && !dia1[r + i] && !dia2[r - i + n - 1]) {
col[i] = true;
dia1[r + i] = true;
dia2[r - i + n - 1] = true;
res += dfs(n, r + 1, col, dia1, dia2);
col[i] = false;
dia1[r + i] = false;
dia2[r - i + n - 1] = false;
}
}
return res;
}
}