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
| public class QueenSolve {
int queensize; //皇后的数量
ArrayList<Queen> queens; //皇后数组，数组中的索引值表示是第几行的皇后
Bord bord; //新建个棋盘
int numSolutions; //总共解法的次数
public QueenSolve(int size) { //解法初始化的类
queensize=size;
queens=new ArrayList<>();
for(int i=0;i<queensize;i++) //新建皇后，并放进去
queens.add(new Queen());
bord=new Bord(queensize); //棋盘
numSolutions=0; //初始化次数
}
/*主类*/
public static void main(String[] args) {
// TODO Auto-generated method stub
QueenSolve queenSolve=new QueenSolve(8); //初始化，然后调用解法
queenSolve.solve();
}
public void solve(){
System.out.println("Start solve...."); //解题在下面方法完成，所以只会输出一次
putQueen(0); //开始，调用
}
private void putQueen(int index){
int row=index;
for(int col=0;col<queensize;col++){ //从当前行的第一个位置开始
/*如果位置为0，则有效，把该行的皇后放进去*/
if(bord.getA()[row][col]==0){
queens.get(row).setPosition(col); //设置该行皇后位置
/*下面是把本次循环无效位置设置为0，因为不会再在上面摆了，所以只要把下面的设置为1就行了
这不影响我们打印因为，每个皇后的位置已经保存过了*/
for (int i = row + 1; i < bord.getSize(); i++) {
bord.getA()[i][col] ++; //皇后位置所在的那一列，一个循环往下设置一个，直到结束全部设置完成
if (row + col - i >= 0) { //如果往左的对角线元素存在，把他设置为1
bord.getA()[i][row + col - i] ++;
}
if (i + col - row < bord.getSize()) {//如果往右的对角线元素存在，把他设置为1
bord.getA()[i][i + col - row] ++;
}
}
if (row == bord.getSize()-1) { //如果已经是最后一行了，就说明解题结束，次数加1在打印
numSolutions++;
printSolution(numSolutions);
}else {
putQueen(row+1);//执行到这里，就是这一行已经摆好位置了，换下一行去处理
}
//上面一句执行，如果下一行每一行都为1，说明这一行走错了，把这一行的操作退回去，这个col是错误的，
//执行完退回操作，回到上面继续下一个col
for (int i = row + 1; i < bord.getSize(); i++) {
bord.getA()[i][col] --;
if (row + col - i >= 0) {
bord.getA()[i][row + col - i] --;
}
if (i + col - row < bord.getSize()) {
bord.getA()[i][i + col - row] --;
}
}
}
}
}
private void printSolution(int i){
System.out.println("The "+i+ " solution is:");
for (int j = 0; j < bord.getSize(); j++) {
for (int k = 0; k < bord.getSize(); k++) {
//是那个位置的话输出*，不是输出-
System.out.print(queens.get(j).getPosition() == k ? " * ":" - ");
}
System.out.println();
}
System.out.println();
}
}
|