數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-四、八、N皇后問題

1、1計算機與軟件工程學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法-課程設(shè)計 課 程 代 碼: 106014389 題 目: 四、八、N 皇后問題 年級/專業(yè)/班: 學(xué) 生 姓 名: 學(xué) 號: 312012080611523 開 始 時 間: 年 月 日完 成 時 間: 年 月 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日八皇后問題2摘摘 要要 解決八皇后問題主要利用了遞歸法、回溯法,以及對 for 語句、數(shù)據(jù)結(jié)構(gòu)中樹的靈活運用、和對棧及數(shù)組的掌握。編程實現(xiàn)了在 8*8 的格的國際象棋上擺放八個

2、皇后，使其不能相互攻擊，即任意兩個皇后都不能處于同一列、同一行、或同一條斜線上面。編程實現(xiàn)了任意給定一個初始位置，輸出八皇后問題的一個布局。本次設(shè)計旨在學(xué)習(xí)各種算法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運用及變通能力，增強對算法的理解能力，提高軟件設(shè)計能力。在實踐中培養(yǎng)獨立分析問題和解決問題的作風(fēng)和能力。關(guān)鍵詞：關(guān)鍵詞：遞歸法; 回溯法; 順序棧；數(shù)組； 八皇后問題3目目 錄錄 1 需求分析需求分析.62 開發(fā)及運行平臺開發(fā)及運行平臺.73 概要設(shè)計概要設(shè)計.84 詳細設(shè)計詳細設(shè)計.105 調(diào)試分析調(diào)試分析.116 測試結(jié)果測試結(jié)果.126.16.1 遇到的問題遇到的問題.126.26.2 調(diào)試結(jié)果

3、調(diào)試結(jié)果.12.137 結(jié)論結(jié)論.14通過這次的課程設(shè)計，讓我了解了八皇后這一經(jīng)典的問題。同時讓我更好地掌握了棧思想以及一維通過這次的課程設(shè)計，讓我了解了八皇后這一經(jīng)典的問題。同時讓我更好地掌握了棧思想以及一維數(shù)組等等知識數(shù)組等等知識, ,以及一些書本上沒有的東西，這對我以后的學(xué)習(xí)生涯以及將來步入社會起到很大的以及一些書本上沒有的東西，這對我以后的學(xué)習(xí)生涯以及將來步入社會起到很大的幫助。這次課程設(shè)計雖然花了我很多時間和精力，但很值得幫助。這次課程設(shè)計雖然花了我很多時間和精力，但很值得, ,因為它對我能力提高起到很大幫助。因為它對我能力提高起到很大幫助。這次課程設(shè)計也提醒我以前知識的匱乏這次課程

4、設(shè)計也提醒我以前知識的匱乏, ,它給我敲響了警鐘它給我敲響了警鐘, ,讓我意識到自己基礎(chǔ)的不扎實讓我意識到自己基礎(chǔ)的不扎實. .當(dāng)然這當(dāng)然這次實驗還是有很多問題的。比如程序設(shè)計的界面不夠好，一些程序并非自己所寫次實驗還是有很多問題的。比如程序設(shè)計的界面不夠好，一些程序并非自己所寫, ,而是修改某些程而是修改某些程序而成序而成, ,但這些不該但這些不該, ,在下次課程設(shè)計時不會再發(fā)生。在下次課程設(shè)計時不會再發(fā)生。.14參考文獻參考文獻.15附附 錄錄.16八皇后問題41 需求分析八皇后問題是一個古老而著名的問題，該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯 1850年提出的,并作了部分解答。高斯在棋盤上放下

5、了八個互不攻擊的皇后，他還認為可能有 76 種不同的放法，這就是有名的“八皇后”問題。 在國際象棋中，皇后是最有權(quán)利的一個棋子；只要別的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時，它就能把對方棋子吃掉。所以高斯提出了一個問題：在 8*8 的格的國際象棋上擺放八個皇后，使其不能相互攻擊，即任意兩個皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法?，F(xiàn)在我們已經(jīng)知道八皇后問題有 92 個解答。本次課設(shè)要求指定任一初始位置，即可輸出八皇后問題的所有行列布局。拓展完成四皇后問題。八皇后問題52 開發(fā)及運行平臺運行平臺：Windos98/2000 以上開發(fā)平臺：Microso

6、ft Visual C+ 6.0八皇后問題63 概要設(shè)計3.13.1 結(jié)構(gòu)設(shè)計理念結(jié)構(gòu)設(shè)計理念（1）從 n 列開始擺放第 n 個皇后（因為這樣便可以符合每一豎列一個皇后 的要求），先測試當(dāng)前位置（n，m）是否等于 0（未被占領(lǐng)）。如果是，擺放第 n 個皇后，并宣布占領(lǐng)，接著進行遞歸；如果不是，測試下一個位置（n，m+1），但是如果當(dāng)n8 時，便打印出結(jié)果。3.23.2 類設(shè)計類設(shè)計類定義：class 類名細節(jié)（數(shù)據(jù)成員，成員函數(shù)）；類函數(shù)定義：返回類型 類名：函數(shù)名（形參表）函數(shù)體；設(shè)計類 eightqueen，利用類的成員函數(shù) Find 求解。用數(shù)據(jù) s1.8表示順序棧，棧的下標(biāo)表示皇后所在

7、的行號，棧的內(nèi)容表示所在列號。用 aj,bi+j,ci-j三個布爾數(shù)組（初值為真）檢查皇后是否在列、主對角線、從對角線上沖突。aj=0,bi+j=0,ci-j=0 表示未沖突。aj=1 表示 j 列沖突（范圍 1-8），bi+j=1 表示第 i+j 條對角線沖突（范圍-7-7），若 ci-j=1 表示第i-j 條對角線沖突（范圍 2-16）。如在（i，j）上放置皇后，若滿足 aj&bi+j&ci-j,則安全。八皇后問題7這個程序主要由 4 個模塊組成，分別是畫棋盤模塊，畫皇后模塊，輸出皇后擺法模塊，和解決如何擺置皇后模塊。這 4 個模塊隸屬于主函數(shù)模塊。輸出當(dāng)前布局開始開始放第

8、一行的皇后檢查是否放滿未放滿放置新皇后檢測是否沖突不沖突，繼續(xù)放下一行皇后沖突，移走剛才放置的皇后放滿八皇后問題84 詳細設(shè)計Find 將實現(xiàn)算法：置當(dāng)前行、列均為 1；While（當(dāng)前行號=8）檢查當(dāng)前行，從當(dāng)前列起逐列試探，尋找安全列號：If（找到安全列）放置皇后，列號記入棧中，并將下一行當(dāng)作當(dāng)前行，第一列當(dāng)當(dāng)前列；else退?；厮莸缴弦恍?，移去該行已放置的皇后，以該皇后所在列的下一列為當(dāng)前列；Class eightqueenPrivate：Int a9,b17,c17;int s9;Public:Void print();/輸出結(jié)果Void find();/求一個解八皇后問題95 調(diào)試分

9、析在完整程序調(diào)試時由于太急于求成導(dǎo)致程序進行循環(huán)時出現(xiàn)無法運行的問題，邏輯錯誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分，后經(jīng)細心改正后才把調(diào)試工作做完。做程序真的不是三兩下就能完美的做好的，正應(yīng)了那句話“心急吃不了熱豆腐啊”。 但對于這個程序我由于 c+語言學(xué)的不到位以至于有些摻雜了 c 語言的有關(guān)算法，要是都用 c+來編寫就再好不過了。 在編寫代碼時，我希望能隨機選擇一數(shù) X(192)后，能輸出該種情況所對應(yīng)的八個皇后的擺放方式和每個皇后所在的位置，但想了好久，就是無法實現(xiàn)。而且，當(dāng) 92種情況都輸出時，前面的幾十種情況無法看到，要想讓擺放皇后的圖形和所在具體的位置一起輸出，就得修改程序讓使她們

10、一個一個地輸出，這樣顯然比較麻煩。倘若有一種既能把八皇后的所在位置和把皇后所有情況連續(xù)輸出，我感覺就應(yīng)該算是一個完美的程序了，這還需要我一致的探索發(fā)掘下去才行。 八皇后問題106 測試結(jié)果6.16.1 遇到的問題遇到的問題1）運行時有些函數(shù)的頭文件未定義，導(dǎo)致無法進行編譯；而且在調(diào)試時有些頭文件的使用范疇弄混淆了；2）如果將 92 種情形全部打印，則前面的幾十種情況將無法顯示出，要想看到前面的狀態(tài)，必須添加一個控制語句，使其能一個一個的輸出。6.26.2 調(diào)試結(jié)果調(diào)試結(jié)果八皇后問題結(jié)果如圖 1 所示：圖 1八皇后問題11四皇后問題結(jié)果如圖 2 所示：圖 2八皇后問題127 結(jié)論通過這次的課程設(shè)

11、計，讓我了解了八皇后這一經(jīng)典的問題。同時讓我更好地掌握了棧思想以及一維數(shù)組等等知識,以及一些書本上沒有的東西，這對我以后的學(xué)習(xí)生涯以及將來步入社會起到很大的幫助。這次課程設(shè)計雖然花了我很多時間和精力，但很值得,因為它對我能力提高起到很大幫助。這次課程設(shè)計也提醒我以前知識的匱乏,它給我敲響了警鐘,讓我意識到自己基礎(chǔ)的不扎實.當(dāng)然這次實驗還是有很多問題的。比如程序設(shè)計的界面不夠好，一些程序并非自己所寫,而是修改某些程序而成,但這些不該,在下次課程設(shè)計時不會再發(fā)生。八皇后問題13參考文獻1蘇仕華，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，機械工業(yè)出版社2王紅梅，數(shù)據(jù)結(jié)構(gòu)（C+版）第 2 版，清華大學(xué)出版社3楊秀金，數(shù)據(jù)結(jié)構(gòu)

12、（C+版），人民郵電出版社八皇后問題14附附 錄錄源程序清單如下：頭文件 queen.h#includeusing namespace std;class eightqueenprivate:int a9,b17,c17;/定義棋盤大小int s9;public:void print();void movequeen(int,int);void find();/定義成員函數(shù)void eightqueen:print()int k;static int num=0;coutn 行號： 1 2 3 4 5 6 7 8n;cout列號：;for(k=1;k=8;k+)cout.width(4);co

13、utsk;num=num+1;cout/解numendl;void eightqueen:movequeen(int i,int j)aj=1;bi+j=1;ci-j+9=1;/輸出一個解的成員函數(shù) print（）；void eightqueen:find()int i,j;for(i=2;i=2&i=1)/當(dāng) i=0 時終止循環(huán)八皇后問題15while(j=8)if(aj&bi+j&ci-j+9)break;/在當(dāng)前行 1 上找安全位置j+;if(j=1)j=si;movequeen(i,j);j+;源文件 queen.cpp#include queen.hvoid

14、main()eightqueen game;game.find();四、八、四、八、N N 皇后問題皇后問題#include#includevoid Queen(int i,int n,int *col,int *md,int *sd,int *q) for(int j=0;jn;j+) if(!colj&!mdn+i-j-1&!sdi+j) colj=mdn+i-j-1=sdi+j=1; qi=j;int time=0; if(i=n-1)for(int k=0;kn;k+)八皇后問題16 coutk, qk ; coutendl; else Queen(i+1,n,col,md,sd,q); colj=mdn+i-j-1=s