友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
|
|
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

公众号的微信号是: jikerizhi。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
N 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 N 皇后问题 的解决方案。
每一种解法包含一个不同的 N 皇后问题 的棋子放置方案,该方案中 Q 和 . 分别代表了皇后和空位。
示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1 输出:[["Q"]]
提示:
-
1 <= n <= 9
思路分析
八皇后问题是回溯思想的经典题目。
当在棋盘上放置了一个皇后后,立即排除当前行,列和对应的两个对角线。这里有一点可以优化:我们从上向下进行尝试,所以,只需要判断当前行以上的相关节点是否冲突即可。另外,先检查再渐进点,合适之后,再向前走,可以做到有效地剪枝。
这里有个知识点需要注意:
对于所有的主对角线有 行号 + 列号 = 常数;
对于所有的次对角线有 行号 - 列号 = 常数。
如下图所示:
利用回溯解题时,只回溯一半,然后将每个解反转即可求得另外一般解。这里有个细节需要注意:如果长度是奇数,而且第一行中间是合法位置,则在回溯过程中已经产生了对称解法。就不需要再反转了。。
-
一刷
-
二刷
-
三刷
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
* Runtime: 4 ms, faster than 64.59% of Java online submissions for N-Queens.
* Memory Usage: 41.3 MB, less than 5.41% of Java online submissions for N-Queens.
*/
public List<List<String>> solveNQueens(int n) {
int[][] matrix = new int[n][n];
List<List<String>> result = new ArrayList<>();
backtrack(matrix, 0, 0, result);
int size = result.size();
if (size == 0) {
return result;
}
for (int i = 0; i < size; i++) {
List<String> om = result.get(i);
// 如果长度是奇数,而且第一行中间是合法位置,则在回溯过程中已经产生了对称解法。
if (!(n % 2 == 1 && om.get(0).charAt(getMid(n)) == 'Q')) {
List<String> nm = reverseMatrix(om);
result.add(nm);
}
}
return result;
}
private List<String> reverseMatrix(List<String> matrix) {
List<String> result = new ArrayList<>(matrix.size());
for (String s : matrix) {
StringBuilder sb = new StringBuilder(s);
result.add(sb.reverse().toString());
}
return result;
}
private void backtrack(int[][] matrix, int y, int step, List<List<String>> result) {
int length = matrix.length;
if (step == length) {
result.add(matrixToList(matrix));
return;
}
for (int xi = 0; xi < length; xi++) {
if (y == 0) {
int mid = getMid(length);
if (mid < xi) {
break;
}
}
if (isValid(matrix, y, xi)) {
matrix[y][xi] = 1;
backtrack(matrix, y + 1, step + 1, result);
matrix[y][xi] = 0;
}
}
}
private int getMid(int length) {
return length % 2 == 0 ? length / 2 - 1 : length / 2;
}
private List<String> matrixToList(int[][] matrix) {
List<String> result = new ArrayList<>(matrix.length);
for (int y = 0; y < matrix.length; y++) {
StringBuilder sb = new StringBuilder();
for (int x = 0; x < matrix[0].length; x++) {
if (matrix[y][x] == 0) {
sb.append(".");
} else {
sb.append("Q");
}
}
result.add(sb.toString());
}
return result;
}
private boolean isValid(int[][] matrix, int y, int x) {
int len = matrix.length;
// 同列
for (int i = 0; i < y; i++) {
if (matrix[i][x] == 1) {
return false;
}
}
// // 同行
// for (int i = 0; i < len; i++) {
// if (i != x && matrix[y][i] == 1) {
// return false;
// }
// }
// 左上角
for (int i = 1; i < len && y - i >= 0 && x - i >= 0; i++) {
if (matrix[y - i][x - i] == 1) {
return false;
}
}
// 右上角:从右上角到最下角的对角线,他们 "行号 + 列号 = 常数"
int sum = x + y;
for (int yi = y - 1; yi >= 0 && 0 <= sum - yi && sum - yi < len; yi--) {
if (matrix[yi][sum - yi] == 1) {
return false;
}
}
return true;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
* 自己实现
*/
public List<List<String>> solveNQueens(int n) {
if (n <= 0) {
return Collections.emptyList();
}
int[][] board = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], 0);
}
List<List<String>> result = new ArrayList<>();
backtrack(result, board, 0, 0);
return result;
}
private void backtrack(List<List<String>> result, int[][] board, int index, int count) {
int length = board.length;
printMatrix(board);
if (length < count) {
return;
}
if (length == count) {
List<String> r = new ArrayList<>(length);
for (int[] ints : board) {
StringBuilder sb = new StringBuilder();
for (int n : ints) {
if (n == 1) {
sb.append("Q");
} else {
sb.append(".");
}
}
r.add(sb.toString());
}
result.add(r);
}
for (int i = index; i < length * length; i++) {
int row = i / length;
int col = i % length;
if (!isValid(board, row, col)) {
continue;
}
board[row][col] = 1;
backtrack(result, board, i, count + 1);
board[row][col] = 0;
}
}
private boolean isValid(int[][] board, int row, int col) {
int length = board.length;
for (int i = 0; i < length; i++) {
if (board[i][col] == 1) {
return false;
}
if (board[row][i] == 1) {
return false;
}
}
for (int i = 0; i < length; i++) {
if (0 <= row - i && 0 <= col - i
&& board[row - i][col - i] == 1) {
return false;
}
if (row + i < length && col + i < length
&& board[row + i][col + i] == 1) {
return false;
}
if (0 <= row - i && col + i < length
&& board[row - i][col + i] == 1) {
return false;
}
if (row + i < length && 0 <= col - i
&& board[row + i][col - i] == 1) {
return false;
}
}
return true;
}
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
58
59
60
61
62
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-11-09 22:12:06
*/
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] chars : board) {
Arrays.fill(chars, '.');
}
List<List<String>> result = new ArrayList<>();
backtrack(result, board, 0);
return result;
}
private void backtrack(List<List<String>> result, char[][] board, int row) {
int n = board.length;
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] chars : board) {
list.add(new String(chars));
}
result.add(list);
return;
}
for (int i = 0; i < n; i++) {
if (!isValid(board, row, i)) {
continue;
}
board[row][i] = 'Q';
backtrack(result, board, row + 1);
board[row][i] = '.';
}
}
private boolean isValid(char[][] board, int row, int col) {
int length = board.length;
for (int i = 0; i < length; i++) {
// 行
if (board[row][i] == 'Q') {
return false;
}
// 列
if (board[i][col] == 'Q') {
return false;
}
// 正对角线
if (row - i - 1 >= 0 && col - i - 1 >= 0 && board[row - i - 1][col - i - 1] == 'Q') {
return false;
}
if (row + i + 1 < length && col + i + 1 < length && board[row + i + 1][col + i + 1] == 'Q') {
return false;
}
// 反对角线
if (row - i - 1 >= 0 && col + i + 1 < length && board[row - i - 1][col + i + 1] == 'Q') {
return false;
}
if (row + i + 1 < length && col - i - 1 >= 0 && board[row + i + 1][col - i - 1] == 'Q') {
return false;
}
}
return true;
}

