欢迎来到天天文库
浏览记录
ID:12059247
大小:76.00 KB
页数:6页
时间:2018-07-15
《八个皇后 java,c实现》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、FromGossip@caterpillarAlgorithmGossip:八個皇后 說明西洋棋中的皇后可以直線前進,吃掉遇到的所有棋子,如果棋盤上有八個皇后,則這八個皇后如何相安無事的放置在棋盤上,1970年與1971年,E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。解法關於棋盤的問題,都可以用遞迴求解,然而如何減少遞迴的次數?在八個皇后的問題中,不必要所有的格子都檢查過,例如若某列檢查過,該該列的其它格子就不用再檢查了,這個方法稱為分支修剪。所以檢查時,先判斷是否在已放置皇后的可行進方向上,如果沒有再行放置下一個皇后,如此就
2、可大大減少遞迴的次數,例如以下為修剪過後的遞迴檢查行進路徑:八個皇后的話,會有92個解答,如果考慮棋盤的旋轉,則旋轉後扣去對稱的,會有12組基本解。 實作·C#include#include#defineN8intcolumn[N+1];//同欄是否有皇后,1表示有intrup[2*N+1];//右上至左下是否有皇后intlup[2*N+1];//左上至右下是否有皇后intqueen[N+1]={0};intnum;//解答編號voidbacktrack(int);//遞迴求解intmain(void){inti;num
3、=0;for(i=1;i<=N;i++)column[i]=1;for(i=1;i<=2*N;i++)rup[i]=lup[i]=1;backtrack(1);return0;}voidshowAnswer(){intx,y;printf("解答%d",++num);for(y=1;y<=N;y++){for(x=1;x<=N;x++){if(queen[y]==x){printf("Q");}else{printf(".");}}printf("");}}voidbacktrack(inti){intj;if(i>N){showAnswer()
4、;}else{for(j=1;j<=N;j++){if(column[j]==1&&rup[i+j]==1&&lup[i-j+N]==1){queen[i]=j;//設定為佔用column[j]=rup[i+j]=lup[i-j+N]=0;backtrack(i+1);column[j]=rup[i+j]=lup[i-j+N]=1;}}}}·JavapublicclassQueen{//同欄是否有皇后,1表示有privateint[]column;//右上至左下是否有皇后privateint[]rup;//左上至右下是否有皇后privateint[]lup;
5、//解答privateint[]queen;//解答編號privateintnum;publicQueen(){column=newint[8+1];rup=newint[2*8+1];lup=newint[2*8+1];for(inti=1;i<=8;i++)column[i]=1;for(inti=1;i<=2*8;i++)rup[i]=lup[i]=1;queen=newint[8+1];}publicvoidbacktrack(inti){if(i>8){showAnswer();}else{for(intj=1;j<=8;j++){if(colum
6、n[j]==1&&rup[i+j]==1&&lup[i-j+8]==1){queen[i]=j;//設定為佔用column[j]=rup[i+j]=lup[i-j+8]=0;backtrack(i+1);column[j]=rup[i+j]=lup[i-j+8]=1;}}}}protectedvoidshowAnswer(){num++;System.out.println("解答"+num);for(inty=1;y<=8;y++){for(intx=1;x<=8;x++){if(queen[y]==x){System.out.print("Q");}
7、else{System.out.print(".");}}System.out.println();}}publicstaticvoidmain(String[]args){Queenqueen=newQueen();queen.backtrack(1);}}
此文档下载收益归作者所有