文章目錄

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋且不会互相吃到对方;皇后棋可以吃掉任何它所在的那一列、那一行,以及那两个对角线(米字形)上的任何棋子。请写一个程序,读入一个值n表示棋盘的大小,然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明。这是广义的N后问题,因为所要求的是“所有”解答,而不单是其中的一组,对大多数会运用递归的人来说,这个题目反而容易做些。这一类型题目的揭发通常要用到回溯(Backtrack)的技巧–不管用递归还是不用递归都是如此,虽然会浪费时间,但多半会找到答案。

依据题意,写了一个递归的方法,判断是否能放置皇后时有点麻烦,应该有更简便的方法。

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
 import java.util.Arrays;

public class NQueens {
public static int totalNQueens(int n) {
boolean[][] board = new boolean[n][n];
return totalNQueens(0, n, board);
}
//check if queen can put on board[row][col]
private static boolean canPutCheck(int row, int col, int n, boolean[][] board) {
for (int i = 0; i < n; i++) {
if (board[row][i]) //row
return false;
if (board[i][col]) //col
return false;
}
//diagonal
int i = 0;
while (row + i < n && col + i < n) {
if (board[row + i][col +i])
return false;
i++;
}
i = 0;
while (row - i >= 0 && col - i >= 0) {
if (board[row - i][col - i])
return false;
i++;
}
//back diagonal
i = 0;
while (row + i < n && col - i >= 0) {
if (board[row + i][col - i])
return false;
i++;
}
i = 0;
while (row - i >= 0 && col + i < n) {
if (board[row - i][col + i])
return false;
i++;
}
return true;

}
private static int totalNQueens(int row, int n, boolean[][] board) {
if (row == n) {
return 1;
}
int count = 0;
for (int j = 0; j < n; j++) {
if (canPutCheck(row, j, n, board)) {
board[row][j] = true;
count += totalNQueens(row + 1, n, board);
board[row][j] = false; //backtrack
}
}
return count;

}
public static void main(String[] args) {
for (int i = 4; i < 10; i++)
System.out.println(i + " " + totalNQueens(i));
}
}

文章目錄