Eight Queens: Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column, or diagonal. In this case, “diagonal” means all diagonals, not just the two that bisect the board.
Hints: #308, #350, #371
解法1
在一个8x8的棋盘里，放8个皇后，使得每个皇后都不在其他皇后的同行、同列、同斜线上。其实就是说放8个皇后，这8个皇后谁都没法吃谁，因为国际象棋里皇后可以衡走、竖走、斜走，且每步的长度无限。
- 保证新放的皇后没法被前面的皇后吃掉。
- 保证不会产生重复结果，也就是知道什么时候可以停止计算了。
根据皇后的吃子规则可知，每行只能有一个皇后，我们可以先在第一行放一个皇后，然后在下一行放一皇后。那么下一行放的皇后的位置必定不能在其左下一格、下方一格、右下一格，其他列都可以放。当放到第8行的时候就知道结束了。
代码：
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
|
public List<int[][]> queens8() {
List<int[][]> result = new ArrayList<>();
int[][] board = new int[8][8];
queens8(board, int row, int col, result)
return result;
}
public void queens8(int[][] board, int row, int col, List<int[][]> result) {
if (row > 7) {
// 出界
return;
}
if (isConflict(board, row, col)) {
// 和其他皇后冲突
return;
}
if (row == 7) {
// 不冲突不出界，最后一个
board[row][col] = 1;
result.add(clone(board));
return;
}
board[row][col] = 1; // 放皇后
for (int i = 0; i < 8; i++) {
if (i == col - 1 || i == col || i == col + 1) {
// 不在下一行的左下、下、右下放皇后
continue;
}
queens8(board, row + 1, i, result); // 右马步
}
board[row][col] = 0; // 不论是否成功、失败都把皇后清掉
}
public boolean isConflict(int[][] board, int row, int col) {
for (int i = 0; i < 8; i++) {
if (board[row][i] == 1) {
// 行冲突
return true;
}
if (board[i][col] == 1) {
// 列冲突
return true;
}
}
for (int i = 1; i <= 8; i++) {
int upperRightRow = row - i;
int upperRightCol = col + i;
int upperLeftRow = row - i;
int upperLeftCol = col - i;
int lowerRightRow = row + i;
int lowerRightCol = col + i;
int lowerLeftRow = row + i;
int lowerLeftCol = col - i;
if (upperRightRow < 8 && upperRightCol < 8
&& board[upperRightRow][upperRightCol] == 1) {
// 和右上斜线皇后冲突
return true;
}
if (upperLeftRow < 8 && upperLeftCol < 8
&& board[upperLeftRow][upperLeftCol] == 1) {
// 和左上斜线皇后冲突
return true;
}
if (lowerRightRow < 8 && lowerRightCol < 8
&& board[lowerRightRow][lowerRightCol] == 1) {
// 和右下斜线皇后冲突
return true;
}
if (lowerLeftRow < 8 && lowerLeftCol < 8
&& board[lowerLeftRow][lowerLeftCol] == 1) {
// 和左下斜线皇后冲突
return true;
}
}
return false;
}
|
可能可以做的优化：对于一种8皇后解法来说，它的镜像肯定也是一个解，那么是否是说只第一行只需要尝试1-4列就行了呢？
解法2（更好）
因为每行放一个皇后，所以不需要int[][] borad来记录位置，只需要int[] cols就行了。比如cols[0]就是第一行皇后所处的列。
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
|
public List<int[]> queens8() {
int[] cols = new int[] {-1, -1, -1, -1, -1, -1, -1, -1};
List<int[]> result = new ArrayList<>();
queens8(cols, 0, result);
return result;
}
public void queens8(int[] cols, int row, List<int[]> result) {
if (row == 8) {
result.add(cols.clone());
return;
}
for (int col = 0; col < 8; i++) {
if (!isConflict(row, col, cols)) {
cols[row] = col;
queens8(cols, row + 1, result);
}
}
}
// 判断本
private boolean isConflict(int row, int col, int[] cols) {
// 只和前面的行比较
for (int i = 0; i < row; i++) {
// 判断和前面的皇后是否处于相同列
if (col[i] == col) {
return true;
}
// 判断是否处于前面皇后的斜线上
int rightDownCol = col[i] + (row - i); // 右下方斜线在本行的列数
if (col == rightDownCol) {
return true;
}
int leftDownCol = col[i] - (row - i); // 左下方斜线在本行的列数
if (col == leftDownCol) {
return true;
}
}
return false;
}
|
评论