德国开元华人社区 开元周游
标题:
[原创]八皇后问题的递归写法
[打印本页]
作者:
gm_jwl
时间:
1.10.2003 19:35
<!--emo&:d--><img src='https://www.kaiyuan.info/modules/ipboard/html/emoticons/teeth_smile.gif' border='0' style='vertical-align:middle' alt='teeth_smile.gif' /><!--endemo--> <!--emo&:d--><img src='https://www.kaiyuan.info/modules/ipboard/html/emoticons/teeth_smile.gif' border='0' style='vertical-align:middle' alt='teeth_smile.gif' /><!--endemo--> <br>--------------<br>public class Queen{<br> private int[][] checkerboard=new int[8][8]; <br> private int[] local=new int[8]; <span style='color:blue'>//save the queens' locations everytimes</span><br>int nummer=0;<br> public void queenSearch(){<br> rekQueen(0);<br> }<br> void prt(){<br> System.out.println("\nStart");<br> for(int i=0;i<8;i++){<br> for(int j=0;j<8;j++){<br> if(local
!=j) System.out.print("- ");<br> else System.out.print("Q ");<br> }<br> System.out.println();<br> }<br> System.out.println("End\n");<br> }<br><span style='color:blue'>//Rekursion</span><br> <span style='font-size:12pt;line-height:100%'><span style='color:red'>void rekQueen(int horizontal){<br> int k=horizontal;<br> int[][] backup=new int[8][8];<br> for(int i=0;i<checkerboard.length;i++){<br> if(checkerboard[k]
==0){<br>local[k]=i;<br> if(k==7){<br> checkerboard[7]
=2;<br> prt();<br> nummer++;<br> continue;<br> }<br> arrayCopy(checkerboard,backup); <span style='color:blue'>//make a backup</span><br> remark(checkerboard,k,i);<br> rekQueen(k+1);<br> arrayCopy(backup,checkerboard);<br> }<br> }<br> local[k]=-1;<br> return; <br> } </span></span> <br>void arrayCopy(int[][] a1,int[][] a2){<br> for(int i=0;i<a1.length;i++){<br> for(int j=0;j<a1
.length;j++) a2
[j]=a1
[j];<br> }<br> }<br> void remark(int[][] array,int i,int j){<br> array
[j]=2;<br> if(i<array.length-1){ <span style='color:blue'>// asure that the horizon between 0-6</span> <br> int m=i,l=j,n=l;<br> while(++m<array.length){<br> array[m][j]=1;<br> <span style='color:blue'>//make vertical as unavailable</span><br> if(--l>=0) array[m][l]=1; <br><span style='color:blue'>//left tilted</span><br> if(++n<array.length) array[m][n]=1; <span style='color:blue'>//right tilted</span><br> }<br> }<br> } <br> public static void main(String[] args){<br> Queen q=new Queen();<br> long time1=System.currentTimeMillis();<br> q.queenSearch();<br> long time2=System.currentTimeMillis();<br>System.out.println("nnInsgesamt gibt's "+nummer+" Loesungen.");<br> System.out.println("nDie Durchlaufzeit betraegt "+(time2-time1)+" ms.");<br> }<br>}<br>-------------
欢迎光临 德国开元华人社区 开元周游 (https://bbs.kaiyuan.cn/)
Powered by Discuz! X3.2