51.N 皇后

题目描述

原题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
img
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。
示例:
1
输入:4
2
输出:[
3
[".Q..", // 解法 1
4
"...Q",
5
"Q...",
6
"..Q."],
7
8
["..Q.", // 解法 2
9
"Q...",
10
"...Q",
11
".Q.."]
12
]
13
解释: 4 皇后问题存在两个不同的解法。
Copied!
提示:
    皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

题解

1
class Solution {
2
/**
3
* 数组索引是行号,数组元素是列号
4
*/
5
int[] cols;
6
List<List<String>> lists = new ArrayList<>();
7
public List<List<String>> solveNQueens(int n) {
8
if (n < 1) return null;
9
cols = new int[n];
10
place(0);
11
return lists;
12
}
13
/**
14
* 从第row行开始摆放皇后
15
* @param row
16
*/
17
void place(int row) {
18
if(row == cols.length){
19
lists.add(show());
20
return;
21
}
22
for (int col = 0; col < cols.length; col++) {
23
if (isValid(row, col)) {
24
// 在第row行第col列摆放皇后
25
cols[row] = col;
26
place(row + 1);
27
}
28
}
29
}
30
/**
31
* 判断第row行第col列是否可以摆放皇后
32
*/
33
boolean isValid(int row, int col) {
34
//遍历每一行
35
for (int i = 0; i < row; i++) {
36
// 第col列已经有皇后
37
if (cols[i] == col) {
38
return false;
39
}
40
// 第i行的皇后跟第row行第col列格子处在同一斜线上
41
if (row - i == Math.abs(col - cols[i])) {
42
return false;
43
}
44
}
45
// System.out.println("[" + row + "][" + col + "]=true");
46
return true;
47
}
48
List<String> show() {
49
List<String> list = new ArrayList<>();
50
for (int row = 0; row < cols.length; row++) {
51
StringBuilder sb = new StringBuilder();
52
for (int col = 0; col < cols.length; col++) {
53
if (cols[row] == col) {
54
sb.append("Q");
55
} else {
56
sb.append(".");
57
}
58
}
59
list.add(sb.toString());
60
}
61
return list;
62
}
63
}
Copied!
最近更新 4mo ago
复制链接