八皇后問題的解決完整文檔

1、 淮陰工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目設(shè)計(jì)題目： 八 皇 后 2008年 6 月 25 日設(shè)計(jì)任務(wù)書設(shè)計(jì)任務(wù)書課題課題名稱名稱 八 皇 后設(shè)計(jì)設(shè)計(jì)目的目的1.用 c+語言平臺將一個(gè)的棋盤上放上個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的 92 種結(jié)構(gòu)予以實(shí)現(xiàn)2. 通過這次課程設(shè)計(jì),提高自己的編程能力,熟悉 c+的編程壞境,為以后的程序開發(fā)打下基礎(chǔ). 實(shí)驗(yàn)實(shí)驗(yàn)環(huán)境環(huán)境1） 系統(tǒng)要求：win98以上操作系統(tǒng)； 2） 語言平臺：tc+或vc+6.0； 3） 執(zhí)行文件：八皇后.exe任務(wù)任務(wù)要求要求試編寫程序?qū)崿F(xiàn)將八個(gè)皇后放置在國際象棋棋盤的無沖突的位

2、置上的算法，并給出所有的解。工作進(jìn)度計(jì)劃工作進(jìn)度計(jì)劃序號序號起止日期起止日期工工 作作 內(nèi)內(nèi) 容容12008.6.232008.6.24查閱相關(guān)內(nèi)容22008.6.242008.6.25編寫代碼及實(shí)習(xí)報(bào)告32008.6.252008.6.26完善課程設(shè)計(jì)報(bào)告42008.6.262008.6.27答辯指導(dǎo)教師（簽章）：指導(dǎo)教師（簽章）： 2008 年年 6 月月 30 日日 摘要： 八皇后問題要求在一個(gè)的棋盤上放上個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊按照國際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子因此，八皇后問題等于要求八個(gè)皇

3、后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上。 而本課程設(shè)計(jì)本人的目的也是通過用c+語言平臺將一個(gè)的棋盤上放上個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn) 使用遞歸方法最終將其問題變得一目了然，更加易懂。關(guān)鍵詞： 八皇后 ; c+ ; 遞歸法 目目 錄錄1. 課題綜述課題綜述.11. 1 課題的來源及意義 .11. 2 面對的問題.12. 需求分析需求分析.12. 1 涉及到的知識.12. 2 軟硬件的需求.12. 3 功能需求.23. 概要設(shè)計(jì)概要設(shè)計(jì).24. 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)詳細(xì)設(shè)計(jì)和實(shí)現(xiàn).24. 1 算法描述及詳細(xì)流程圖.24.1.1 算

4、法描述.34.1.2 算法流程圖.35. 代碼編寫及詳細(xì)注釋代碼編寫及詳細(xì)注釋.46. 程序調(diào)試程序調(diào)試.76. 1 調(diào)試過程、步驟及遇到的問題 .77. 運(yùn)行與測試運(yùn)行與測試.77.1 運(yùn)行演示.7總總 結(jié)結(jié).9致致 謝謝.10參考文獻(xiàn)參考文獻(xiàn).11. . 11. 課題綜述課題綜述1. 1 課題的來源及意義課題的來源及意義 八皇后問題是一個(gè)古老而著名的問題，該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850 年提出的。在國際象棋中，皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時(shí)，它就能把對方棋子吃掉。所以高斯提出了一個(gè)問題：在 8*8 的格的國際象棋上擺放八

5、個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。到了現(xiàn)代，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，這一古老而有趣的數(shù)學(xué)游戲問題也自然而然的被搬到了計(jì)算機(jī)上。運(yùn)用所學(xué)計(jì)算機(jī)知識來試著解決這個(gè)問題是個(gè)鍛煉和提高我自己編程能力和獨(dú)立解決問題能力的好機(jī)會，可以使我增強(qiáng)信心，為我以后的編程開個(gè)好頭，故我選擇了這個(gè)有趣的課題。1. 2 面對的問題面對的問題1） 解決沖突問題： 這個(gè)問題包括了行，列，兩條對角線； 列：規(guī)定每一列放一個(gè)皇后，不會造成列上的沖突； 行：當(dāng)?shù)?I 行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以 I 為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)

6、；2） 使用數(shù)據(jù)結(jié)構(gòu)的知識，用遞歸法解決問題。 2. 需求分析需求分析2. 1 涉及到的知識涉及到的知識 本次課程設(shè)計(jì)中，用到的主要知識有：遞歸法的運(yùn)用，for 語句的靈活運(yùn)用，數(shù)據(jù)結(jié)構(gòu)中樹知識的靈活運(yùn)用、棧及數(shù)組的掌握。2. 2 軟硬件的需求軟硬件的需求 21）系統(tǒng)要求：win98 以上操作系統(tǒng)； 2) 語言平臺：tc+或 vc+6.0； 2. 3 功能需求功能需求 當(dāng)運(yùn)行程序時(shí)，在屏幕上顯示每一種方法八個(gè)皇后的相對位置，要用比較直觀 的界面顯示。3. 概要設(shè)計(jì)概要設(shè)計(jì)本課件學(xué)生是用循環(huán)遞歸循環(huán)來實(shí)現(xiàn)的，分別一一測試了每一種擺法，并把它擁有的 92 種變化表現(xiàn)出來。在這個(gè)程序中，我的主要思路

7、以及思想是這樣的： 1）解決沖突問題： 這個(gè)問題包括了行，列，兩條對角線； 列：規(guī)定每一列放一個(gè)皇后，不會造成列上的沖突； 行：當(dāng)?shù)?I 行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以 I 為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)； 對角線：對角線有兩個(gè)方向。在這我把這兩條對角線稱為：主對角線和從對角線。在同一對角線上的所有點(diǎn)（設(shè)下標(biāo)為(i,j)） ，要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當(dāng)?shù)?I 個(gè)皇后占領(lǐng)了第 J 列后，要同時(shí)把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。 2）數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn) 而對于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，學(xué)生則是著重于: 數(shù)組 aI：a I表示第 I 個(gè)皇后

8、放置的列；I 的范圍：1.8; 對角線數(shù)組：bj(主對角線),cj（從對角線） ，根據(jù)程序的運(yùn)行，去決定主從對角線是否放入皇后；4. 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)4. 1 算法描述及詳細(xì)流程圖算法描述及詳細(xì)流程圖 34.1.1 算法描述算法描述A、 數(shù)據(jù)初始化。B、 從 n 列開始擺放第 n 個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求） ，先測試當(dāng)前位置（n，m）是否等于 0（未被占領(lǐng)） 。如果是，擺放第 n 個(gè)皇后，并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置） ，接著進(jìn)行遞歸；如果不是，測試下一個(gè)位置（n，m+1） ，但是如果當(dāng) n8 時(shí)，便打印出結(jié)果。E、輸出函數(shù)我使用 printf 輸

9、出，運(yùn)行形式為：第 m 種方法為：* * * * * * * * 4.1.2 算法流程圖算法流程圖 45. 代碼編寫及詳細(xì)注釋代碼編寫及詳細(xì)注釋#include #include #include #include #include #define QUEENS 8int iCount = 0; /!記錄解的序號的全局變量。int SiteQUEENS; /!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。 5void Queen(int n); /!遞歸求解的函數(shù)。void Output();/!輸出一個(gè)解。int IsValid(int n); /!判斷第 n 個(gè)皇后放上去之后，是否有沖突。void

10、 main() /*-Main：主函數(shù)。-*/ system(title 葉青-遞歸算法八皇后問題 );cout 八皇后的解法：endl;cout -endl; Queen(0); /!從第 0 行開始遞歸試探。 getch();/!按任意鍵返回。 void Queen(int n) /*-Queen：遞歸放置第 n 個(gè)皇后，程序的核心!-*/ int i; if(n = QUEENS) /!參數(shù) n 從 0 開始，等于 8 時(shí)便試出了一個(gè)解，將它輸出并回溯。 Output(); return; for(i = 1 ; i = QUEENS ; i+) /!n 還沒到 8，在第 n 行的各個(gè)行

11、上依次試探。 6 Siten = i; /!在該行的第 i 行上放置皇后。 if(IsValid(n) /!如果放置沒有沖突，就開始下一行的試探。 Queen(n + 1); int IsValid(int n) /*-IsValid：判斷第 n 個(gè)皇后放上去之后，是否合法，即是否無沖突。-*/ int i; for(i = 0 ; i n ; i+) /!將第 n 個(gè)皇后的位置依次于前面 n1 個(gè)皇后的位置比較。 if(Sitei = Siten) /!兩個(gè)皇后在同一列上，返回 0。 return 0; if(abs(Sitei - Siten) = (n - i) /!兩個(gè)皇后在同一對角線

12、上，返回0。 return 0; return 1; /!沒有沖突，返回 1。 void Output()/*-Output：輸出一個(gè)解，即一種沒有沖突的放置方案。-*/ int i; printf(No.%-5d , +iCount); /!輸出序號。 7 for(i = 0 ; i QUEENS ; i+)/!依次輸出各個(gè)行上的皇后的位置，即所在的列數(shù)。 printf(%d , Sitei); printf(n); 6. 程序調(diào)試程序調(diào)試6. 1 調(diào)試過程、步驟及遇到的問題調(diào)試過程、步驟及遇到的問題在完整程序調(diào)試時(shí)遇到幾個(gè)小問題，后經(jīng)細(xì)心改正后才把調(diào)試工作做完。例如:當(dāng)用 printf 輸

13、出時(shí),出現(xiàn)了一些錯(cuò)誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來是缺少了 stdio.h這樣一個(gè)頭文件,添加了頭文件后, 還出現(xiàn)了一些問題,邏輯錯(cuò)誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時(shí)卻沒有錯(cuò)誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學(xué)的交流,發(fā)現(xiàn)是邏輯錯(cuò)誤,經(jīng)過改正后,程序終于可以運(yùn)行了.7. 運(yùn)行與測試運(yùn)行與測試 7.1 運(yùn)行演示運(yùn)行演示 8 9總 結(jié) 通過了 19 周這個(gè)星期的程序設(shè)計(jì)，我從中得到了許多的經(jīng)驗(yàn)以及軟件設(shè)計(jì)的一些新的思路；從這個(gè)八皇后問題設(shè)計(jì)以及分析中，本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對于計(jì)算機(jī)軟件設(shè)計(jì)的重要性，它的使用，可以改變一個(gè)軟件的運(yùn)行周期，也可以將軟件的思路從

14、繁化簡，并且都能夠通過數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴(kuò)充，發(fā)展；這也是在這次課程設(shè)計(jì)中我所掌握得到的。 但由于我的基本知識還不是那么扎實(shí)，也缺乏對軟件設(shè)計(jì)的經(jīng)驗(yàn)，在這過程中也出現(xiàn)了一些問題，如，八皇后在變成初期由于沒真正體會到數(shù)據(jù)結(jié)構(gòu)中“樹”在里面的運(yùn)用，將程序往大一時(shí) c 語言的方向發(fā)展，不自覺的采用了非遞歸的算法，結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個(gè)程序的時(shí)間復(fù)雜度變得更大；在后來學(xué)生對數(shù)據(jù)結(jié)構(gòu)的第六章進(jìn)行了比較深入的研讀，才發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)樹的實(shí)際運(yùn)用的空間是相當(dāng)?shù)拇?，并且，通過了重溫樹的回溯，以及二叉樹的遍歷，最終將程序進(jìn)行了一次較大的改造。并且通過思考，再將以前的數(shù)組

15、知識加以運(yùn)用才最終解決了這個(gè)問題，整個(gè)程序的算法的可看性也有了相當(dāng)?shù)母倪M(jìn)。 課程設(shè)計(jì)隨著時(shí)間的推移，也即將結(jié)束了，但這個(gè)學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義，它從一個(gè)程度上改變了我們的編程思想，如何將一個(gè)程序快速而又準(zhǔn)備的進(jìn)行編寫，進(jìn)行編譯，都成為了我們思考的重點(diǎn)，也通過這一個(gè)學(xué)期的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要的是平時(shí)多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。 課程設(shè)計(jì)已經(jīng)接近尾聲了，但它給我的不只是程序設(shè)計(jì)上的滿足，更重要的是對

16、自己編程思想的一次更新，以及對算法的一個(gè)全新的認(rèn)識！ 我覺得還可以考慮開發(fā) N 皇后問題,在主界面中添加一個(gè) int 型的變量,程序一開始要求輸入一個(gè)數(shù)(確定是幾皇后問題),輸入后按下 enter 后,輸出各種解.主程序與八皇后的求解大體相同. 10致 謝 在這次課程設(shè)計(jì)中,我遇到了不少問題,包括程序上的和課程設(shè)計(jì)的撰寫上的,同學(xué)曾給過我許多幫助,在此我表示對他們的忠心感謝。同時(shí)，指導(dǎo)老師和實(shí)驗(yàn)人員給了我很多上機(jī)的機(jī)會，給了我一個(gè)做課程設(shè)計(jì)的很好的條件，我才能夠順利的完成，在此，我僅以文字的形式表示忠心感謝，感謝他們這么多天對我的幫助。 11 參考文獻(xiàn)1 蘇仕華,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).-北京:機(jī)械

17、工業(yè)出版社,2005.52 于永彥,趙建洋.課程設(shè)計(jì)指導(dǎo)書.淮安：江蘇淮陰工學(xué)院 計(jì)算機(jī)工程系,20063 劉振安,劉燕君，孫忱. C+語言課程設(shè)計(jì).北京：高等教育出版社,20034 陳志泊, 張海燕, 王春玲. Visual C+程序設(shè)計(jì). 中國鐵道出版社 ,20055 呂鳳哲,C+語言程序設(shè)計(jì)（第二版）.北京：電子工業(yè)出版社,20056 殷人昆，陶永雷等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc C+ ）.北京:清華大學(xué)出版社，19997 嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)北京：清華大學(xué)出版社，19978 李春葆.數(shù)據(jù)結(jié)構(gòu)考研指導(dǎo).北京:清華大學(xué)出版社,20029 陳慧南數(shù)據(jù)結(jié)構(gòu)C+語言描述北京：人民郵電出版社，200503 12指導(dǎo)教師評語指導(dǎo)教師評語學(xué)號1061303127姓名葉 青班級信 息 106選題名稱八 皇 后序號評價(jià)內(nèi)