1、數據結構課程設計課題：“八皇后”棋盤問題 組員：卜文婷 郭倩 屈雪 耿艷課題時間：7月1號7月5號人員分工 卜文婷（組長）：編排內容進行整體布局 屈雪：演講文稿，進行答辯 耿艷：資料查找 郭倩：ppt的制作及處理 關于編程部分的實現由成員一起完成八皇后規則在一個88國際象棋盤上，有8個皇后，每個皇后占一格；要求皇后間不會出現相互“攻擊”的現象，即不能有兩個皇后處在同一行、同一列或同一對角線上。 課題意義到了現代，隨著計算機技術的飛速發展，這一古老而有趣的數學游戲問題也自然而然的被搬到了計算機上。運用所學計算機知識來試著解決這個問題是個鍛煉和提高我自己編程能力和獨立解決問題能力的好機會，可以使我

2、們增強信心。構想來源設置為大型游戲中的闖關小游戲。大型游戲，如仙劍情節中會加入小的闖關游戲。仙劍三景天給龍葵找廣袖流仙裙。仙劍4里的拼圖闖關。依照八皇后原則選擇正確的路線通關。或作為益智小游戲初步構想1、建立合適的數據類型表示皇后在棋盤上所處的位置。 2、以8*8規格畫出棋盤形式，在上面動態的標注其行走的過程。 3 、當玩家走一步時，將顯示玩家所在的位置，并顯示是否正確，若出現錯誤，就清除所有步數重新開始，重復次數為三，若仍不正確，則游戲闖關失敗。以下算法是我們初步的一個構想，我們將用遞歸實現玩家的行走步驟，完善我們的算法。int ok(int i)/*遞歸判斷第i行的落子可行性*/（通過橫縱

3、向及斜向判斷）int wdown(int i,int j)玩家輸入位置int output()/*輸出棋盤狀態*/clock();/*計算時間*/ void show()；玩家若走不出，可選擇顯示答案算法#include #include #include int cells64;/*存儲擺放方案，一維數組視為二維棋盤*/int num=0;/*記錄嘗試次數*/int output()/*輸出棋盤狀態*/ static int count=0;/*靜態變量計錄本次輸出的編號*/ int t=0,m,n;/*輔助計算黑白格的選取*/ count+; printf(方案%d：rn,count);

4、for(m=0;m8;m+) for(n=0;n8;n+) t+; if(cellsn+m*8=0)/*沒有皇后*/ t%2?printf():printf();/*根據奇偶與否決定輸出格子黑白*/ else/*有皇后*/ printf(); t+;/*偏移，使黑白格交錯*/ printf(rn); if(count=30|count=60)system(pause); return 0; int ok(int i)/*遞歸判斷第i行的落子可行性*/ int k,j,t1,t2,r;/*臨時變量，作用隨機*/ for(k=0;k8;k+)/*從行首開始向后輪流判斷*/ r=0;num+;/*r

5、存儲是否存在沖突，非0則為沖突*/ for(j=0;j8;j+)/*清空該行可能的棋子，避免由子過程返回后產生的沖突。*/ cellsj+i*8=0; for(j=0;j=0)/*斜線上仍有格子*/ if(cellst1)r=1;break;/*斜向存在沖突*/ t1-=9;/*繼續移動*/ t2-=7;/*同理*/ while(t2%8!=0&t2=0) if(cellst2)r=1;break; t2-=7; if(!r)/*沒有發生沖突*/ cellsk+i*8=1;/*確認落子*/ if(i7)/*沒有落完八個皇后*/ ok(i+1);/*繼續在下一行尋找方案*/ else/*落子成功

6、結束*/ output();/*輸出棋盤狀況*/ return 0;int main()/*應用程序入口，不解釋*/ int i;/*臨時變量，用于初始化棋盤*/ double a,b,c;/*計時用*/ printf(Q); printf(“答案rn); for(i=0;i64;i+)/*棋盤初始化*/ cellsi=0; a=clock();/*開始時間*/ ok(0);/*運算*/ b=clock();/*結束時間*/ printf(rn回答完畢！rn); c=(double)(b-a)/CLOCKS_PER_SEC;/*計算時間間隔*/ return 0; 預期結果 在游戲界面中作為闖關的一項，當玩 家在進行下一游戲之前，將進入此項環節，即必須在規定時間內完成八皇后的破解(共走八步，只要符合