八个皇后 java,c实现

《八个皇后 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);}}