-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQueen.java
More file actions
86 lines (78 loc) · 1.62 KB
/
Queen.java
File metadata and controls
86 lines (78 loc) · 1.62 KB
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
/**
* 回溯法解决八皇后问题
*/
package backtracking;
import java.util.Arrays;
public class Queen
{
public static int num = 1; // 累计方案
public static final int MAXQUEEN = 8;
public static int[] cols = new int[MAXQUEEN]; //定义cols数组，表示8列皇后摆放的位置
/**
* @param n 填第n列的皇后
*/
public void getCount(int n)
{
boolean [] rows = new boolean[MAXQUEEN]; // 记录每个方格是否可以放皇后，默认为false
// 先确定哪些位置不能放皇后
for (int m=0; m<n; m++)
{
rows[cols[m]] = true; // 这一列的cols[m]位置已经放置了一个皇后,不能再放
int d = n-m; // 斜对角
// 正斜方向 /
if (cols[m]-d >= 0)
{
rows[cols[m]-d] = true; // 不能填皇后
}
// 反斜方向 \
if (cols[m] + d < 8)
{
rows[cols[m] + d] = true; // 不能放皇后
}
}
for (int i=0; i<MAXQUEEN; i++)
{
if (rows[i])
{
// 不能放
continue;
}
cols[n] = i;
// 还没排到第7列
if (n <MAXQUEEN-1)
{
getCount(n+1); // 可能无法执行完，意味着排到后面没位置了
}
else
{
System.out.println("方案："+ num + " " +Arrays.toString(cols));
printQueen(num);
num++;
}
// 下面可能仍有合适的位置（回溯）
}
}
private void printQueen(int num)
{
System.out.println("第" + num +"种方案");
for (int i=0; i<MAXQUEEN; i++)
{
for (int j=0; j<MAXQUEEN; j++)
{
if (i==cols[j]) {
System.out.print("0 ");
}
else
{
System.out.print("* ");
}
}
System.out.println();
}
}
public static void main(String[] args)
{
Queen queen = new Queen();
queen.getCount(0);
}
}