-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueen.java
More file actions
executable file
·89 lines (85 loc) · 2.27 KB
/
NQueen.java
File metadata and controls
executable file
·89 lines (85 loc) · 2.27 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
87
88
89
package array;
import java.util.Random;
/**
* Created by Administrator on 2018/3/29 0029.
*/
public class NQueen {
//可行解数组，从X[1]开始使用
private static int[] X={0,0,0,0,0} ;
//X数组的长度
private static int nn=5 ;
//记录可行解数目
private static int sum=0;
/**
* 迭代算法
*/
public void iteration(int n){
int k=1;
while(k>0){
X[k]++;
while(X[k]<n&&!place(k)){
X[k]++;
}
if(X[k]<n){
if(k==n-1){
print();
}
else{
k++;
X[k]=0;
}
}else k--;
}
}
/**
* 递归算法
*/
public void recursion(int p){
if(p==nn) print();
for(X[p]=0;X[p]<nn;X[p]++){
if(place(p)&&p<nn){
//递归调用
recursion(1+p);
}
}
}
//是否可以放置？
public boolean place(int t){
for(int i=1;i<t;i++){
if(Math.abs(i-t)==Math.abs(X[i]-X[t])||X[i]==X[t])
return false;
}
return true;
}
//创建一个随机长度(5~8)的数组
public static int[] createArray(){
nn =new Random().nextInt(3)+5;
int[] a = new int[nn];
for(int i =0;i<nn;i++)
a[i]=0;
return a;
}
//打印函数
public void print(){
sum++;
System.out.println("可行解"+sum);
for(int j=1;j<X.length;j++)
System.out.print(X[j]+" ");
System.out.println();
}
/**
* 主函数
* @param args
*/
public static void main(String[] args) {
//X=createArray();
//System.out.println(X);
System.out.println("迭代回溯算法求得"+(X.length-1)+"皇后的可行解为:");
new NQueen().iteration(X.length);
System.out.println("可行解的个数是:"+sum);
sum=0;
System.out.println("递归算法求得"+(X.length)+"皇后的可行解为:");
new NQueen().recursion(0);
System.out.println("可行解的个数是:"+sum);
}
}