题目
难度：困难
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
提示：
- 1 <= n <= 9
- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
思路
还是回溯算法，同 37. 解数独。
需要判断每个位置能否放一个皇后下去，每行每列只能有一个皇后，比较容易判断，关键在于斜着的一撇一捺。
把棋盘放在坐标系看，将撇和捺看作两条斜率为 1 的直线，也就是 y = kx + c（k = 1或-1）（小学知识？）
也就是： y + x = c 和 y - x = c
那么判断一个位置的斜向有没有其它皇后就很简单了：
只需要两个集合，分别把 y + x 和 y - x 放进去就好了，后边的位置判断集合中是否存在。
按行遍历，每行只能放一个皇后，再需要一个集合记录已使用的列，就可以了。
代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| class Solution {
Set<Integer> col = new HashSet<>();
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
public List<List<String>> solveNQueens(int n) {
List<List<String>> resList = new ArrayList<>();
int[] queens = new int[n];
Arrays.fill(queens, -1);
solve(n, 0, queens, resList);
return resList;
}
private void solve(int n, int row, int[] queens, List<List<String>> resList) {
if (row == n) {
List<String> res = generate(queens, n);
resList.add(res);
}
for (int i = 0; i < n; i++) {
if (!col.contains(i) && !pie.contains(i + row) && !na.contains(i - row)) {
queens[row] = i;
col.add(i);
pie.add(i + row);
na.add(i - row);
solve(n, row + 1, queens, resList);
queens[row] = -1;
col.remove(i);
pie.remove(i + row);
na.remove(i - row);
}
}
}
public List<String> generate(int[] queens, int n) {
List<String> res = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
res.add(new String(row));
}
return res;
}
}
|
作者：prik
永久链接： https://trzoey.github.io/blog-prik/algorithmic/51.n-queens/
转载请注明出处，谢谢合作💓。