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

$Dj.[]%zEO!_0

class Queen8{

Mfr]X+_\'X0static final int QueenMax = 8;
HKId\0static int ōktimes = 0;51Testing软件测试网T)v6h1Y8u`W
static int chess[] = new int[QueenMax];//每一个Queen的放置位置

1d%r?i8R2D)\L'{/n0public static void main(String args[]){
;fP,[7OG0for (int i=0;i<QueenMax;i++)chess[i]=-1; 51Testing软件测试网^9yBKoY&k/Wu\v3L!F
placequeen(0);
(h6r/L+b:zs0System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");
gtOO tX4z0}51Testing软件测试网1Lgu"q:w JD3f3L

51Testing软件测试网/Qv2t,Da
public static void placequeen(int num){ //num 为现在要放置的行数
"Koq"L;Lq0int i=0;
(d([B.Cm%q`0boolean qsave[] = new boolean[QueenMax];51Testing软件测试网~]cylex$\!@;U
for(;i<QueenMax;i++) qsave[i]=true;
bBb(JC.`u051Testing软件测试网D |e?k!M;o$s7O2O
//下面先把安全位数组完成51Testing软件测试网;TS9S5m3IO5KU(rKf5v
i=0;//i 是现在要检查的数组值51Testing软件测试网-T6N4`|L\$\ d"f
g-[0g
while (i<num){
IC(RdK.U4a:V0qsave[chess[i]]=false;51Testing软件测试网.t7s m.sO6z(B
int k=num-i;
*Nd3`;v3Eu0if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;51Testing软件测试网.\w |1m?"_u3D
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
?~ }$GZ m0i++;51Testing软件测试网?}
ZhE
}
HlX)A~E G@1k3q0//下面历遍安全位
rx/C q^IE0for(i=0;i<QueenMax;i++){
)_+j-n;BM5_Px0if (qsave[i]==false)continue;51Testing软件测试网LxlQ)k
if (num<QueenMax-1){51Testing软件测试网)B W1SS5P8z^
chess[num]=i;
)M)M ugM0placequeen(num+1);51Testing软件测试网&{:ny;wOy5G-@$c
}
]S)C3Y3q)`8L2~0else{ //num is last one
_:ec P\T1Ab0chess[num]=i;
N.\,T.Ez,a0oktimes++;
4e8@.r%g
V W.g+~0System.out.println("这是第"+oktimes+"个解法 如下:");51Testing软件测试网;hd8J aF2s!z#I
System.out.println("第n行: 1 2 3 4 5 6 7 8");51Testing软件测试网/K6Xk]%|\)I[
51Testing软件测试网m;Y7ym1E4o8VW"O
for (i=0;i<QueenMax;i++){
-CCZ*@W2N4m0String row="第"+(i+1)+"行: ";
'[*N.u4FE0if (chess[i]==0);51Testing软件测试网2i;Q/`,}'C i[4qHD
else 51Testing软件测试网@y'ZXI*je
for(int j=0;j<chess[i];j++) row+="--";51Testing软件测试网%_Aw9tuf$b'? A\
row+="++";
G}R?D-KI+S.j0int j = chess[i];51Testing软件测试网5y9D;j@d:^#{
while(j<QueenMax-1){row+="--";j++;}
P"TR0p v0?]I:H9X0System.out.println(row);
9|O;X{5A,i,|'o5U0}
Wz_@G)I.a{i0}
^/te0\x6w#G7q0}
MA[\&XPjC!D3i0//历遍完成就停止51Testing软件测试网fc"PN-}L%qfn0A
}
)F${ I,Ss|"~6V0}
pOQ-yRM-t sJ051Testing软件测试网6r)\N!j#EL Dz