八皇后问题的高效解法-递归版

t/BxPT#\)Z Me(Y0class Queen8{

51Testing软件测试网"PDIr$L1ElC3[C
static final int QueenMax = 8;51Testing软件测试网6I ?#yOl ?
static int ōktimes = 0;
7j/Q.Z
k*s0static int chess[] = new int[QueenMax];//每一个Queen的放置位置51Testing软件测试网SJg RP(Z
A!I+lK

OX:]3PD\GK051Testing软件测试网;wk\3ne3T
public static void main(String args[]){51Testing软件测试网a#H
oo4W-O4X
for (int i=0;i<QueenMax;i++)chess[i]=-1; 51Testing软件测试网Pqu'T:Z4I#U
placequeen(0);
0e7A6_:zuS)OLS0System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");51Testing软件测试网UY"Fn(k#n#p
}51Testing软件测试网q4zZ^LL!Sq

51Testing软件测试网-zS+F(RI
public static void placequeen(int num){ //num 为现在要放置的行数51Testing软件测试网.``9IfD
int i=0;
7H bCij(x*J0boolean qsave[] = new boolean[QueenMax];51Testing软件测试网^d![8oJo"_
for(;i<QueenMax;i++) qsave[i]=true;
t5J+Sxp6kXN
KZP0
%]H~jg[+o@'| n0//下面先把安全位数组完成
i{:j#Ta$sTJ0i=0;//i 是现在要检查的数组值51Testing软件测试网+_Q5i?A"^mk
while (i<num){51Testing软件测试网*H%ULs'T(| k/mS2D_
qsave[chess[i]]=false;51Testing软件测试网S+T G$B3l!aZ.kUF
int k=num-i;
U*[6KY1Jxr"Sr0if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
J{.uTo(K/Q0if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
P w4CV4H.uT0i++;51Testing软件测试网6@|3y7hF;Me
}51Testing软件测试网Mi"N(ns]
//下面历遍安全位
D ?0b#_*vh)S&L0for(i=0;i<QueenMax;i++){
+uf~ fY1d%L0if (qsave[i]==false)continue;51Testing软件测试网P{&X{ d@U
if (num<QueenMax-1){
f6smo9h"Bn0chess[num]=i;51Testing软件测试网'e/I,`-{2MH%W+T
placequeen(num+1);51Testing软件测试网W@7YY,[2d4W7Jx
}
T+T8j3H-Z+A"Z)H0else{ //num is last one51Testing软件测试网6Ty!oa4h#I5[M??
chess[num]=i;51Testing软件测试网PtAv,^TOhs
oktimes++;
nuO@`!U#mu0fty0System.out.println("这是第"+oktimes+"个解法 如下:");
;Wqnw~?F%~-P
H0System.out.println("第n行: 1 2 3 4 5 6 7 8");51Testing软件测试网-M \HhwbY[W

"y^;il3e1_0for (i=0;i<QueenMax;i++){
Do+xQi/zc0String row="第"+(i+1)+"行: ";51Testing软件测试网MN3A}8E,F
if (chess[i]==0);
"x7gU9Iwp(u-s0else 51Testing软件测试网I'eyJ?5q-lY
for(int j=0;j<chess[i];j++) row+="--";51Testing软件测试网qNZ1L;NA.`
row+="++";51Testing软件测试网J6LK?)|
int j = chess[i];
7Ae7_v;M
ZSE*wcm8E0while(j<QueenMax-1){row+="--";j++;}
r v5Ko\v{ T9DH0System.out.println(row);51Testing软件测试网%kdq M[7lB!?1d
}51Testing软件测试网_*ic6c-B)r
s B.UV^K
}
C }z:ku9OE0}51Testing软件测试网 X+[%r;KxOV'A
//历遍完成就停止51Testing软件测试网6^:g~9yaMwR
}51Testing软件测试网kn/v&`W;f#lP
}
eUl4p"h*O _Q0