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

淮陰工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：八皇 后系（院）：計(jì)算機(jī)工程系專業(yè)：信息安全班級：信息106學(xué)生姓名：葉青 學(xué)號：1061303127指導(dǎo)教師:張亞紅寇海洲胡榮林夏森學(xué)年學(xué)期:2007?2008學(xué)年第2學(xué)期2008年6月25日

設(shè)計(jì)任務(wù)書課題名稱八 皇 后設(shè)計(jì)目的用C++語言平臺(tái)將一個(gè)8*8的棋盤上放上8個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn).通過這次課程設(shè)計(jì)，提高自己的編程能力，熟悉C++的編程壞境，為以后的程序開發(fā)打下基礎(chǔ).實(shí)驗(yàn)環(huán)境1） 系統(tǒng)要求：win98以上操作系統(tǒng)；2） 語言平臺(tái)：tc++或VC++6.0；3） 執(zhí)行文件：八皇后.exe任務(wù)要求試編寫程序?qū)崿F(xiàn)將八個(gè)皇后放置在國際象棋棋盤的無沖突的位置上的算法，并給出所有的解。工作進(jìn)度計(jì)劃序號起止日期工作內(nèi)容12008.6.23?2008.6.24查閱相關(guān)內(nèi)容22008.6.24?2008.6.25編寫代碼及實(shí)習(xí)報(bào)告32008.6.25?2008.6.26完善課程設(shè)計(jì)報(bào)告42008.6.26?2008.6.27答辯指導(dǎo)教師（簽章）：2008年6月30日摘要:八皇后問題要求在一個(gè)8^8的棋盤上放上8個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊.按照國際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子.因此，八皇后問題等于要求八個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上。而本課程設(shè)計(jì)本人的目的也是通過用c++語言平臺(tái)將一個(gè)8大8的棋盤上放上8個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn).使用遞歸方法最終將其問題變得一目了然，更加易懂。關(guān)鍵詞：八皇后；c++；遞歸法TOC\o"1-5"\h\z\o"CurrentDocument"課題綜述 1\o"CurrentDocument"1.1課題的來源及意義 1\o"CurrentDocument"1.2面對的問題 1\o"CurrentDocument"需求分析 1\o"CurrentDocument"2.1涉及到的知識 1\o"CurrentDocument"2.2軟硬件的需求 1\o"CurrentDocument"2.3功能需求 2\o"CurrentDocument"概要設(shè)計(jì) 2\o"CurrentDocument"詳細(xì)設(shè)計(jì)和實(shí)現(xiàn) 2\o"CurrentDocument"4.1算法描述及詳細(xì)流程圖 2\o"CurrentDocument"4.1.1算法描述 3\o"CurrentDocument"4.1.2算法流程圖 3\o"CurrentDocument"代碼編寫及詳細(xì)注釋 4\o"CurrentDocument"程序調(diào)試 7\o"CurrentDocument"6.1調(diào)試過程、步驟及遇到的問題 7\o"CurrentDocument"運(yùn)行與測試 7\o"CurrentDocument"7.1運(yùn)行演示 7總結(jié) 9致謝 10\o"CurrentDocument"參考文獻(xiàn) 11課題綜述1課題的來源及意義八皇后問題是一個(gè)古老而著名的問題，該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的。在國際象棋中，皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時(shí)，它就能把對方棋子吃掉。所以高斯提出了一個(gè)問題：在8*8的格的國際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。到了現(xiàn)代，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，這一古老而有趣的數(shù)學(xué)游戲問題也自然而然的被搬到了計(jì)算機(jī)上。運(yùn)用所學(xué)計(jì)算機(jī)知識來試著解決這個(gè)問題是個(gè)鍛煉和提高我自己編程能力和獨(dú)立解決問題能力的好機(jī)會(huì)，可以使我增強(qiáng)信心，為我以后的編程開個(gè)好頭，故我選擇了這個(gè)有趣的課題。1.21.2面對的問題i=i1） 解決沖突問題：這個(gè)問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；2） 使用數(shù)據(jù)結(jié)構(gòu)的知識，用遞歸法解決問題。需求分析2.1涉及到的知識本次課程設(shè)計(jì)中，用到的主要知識有：遞歸法的運(yùn)用，for語句的靈活運(yùn)用，數(shù)據(jù)結(jié)構(gòu)中樹知識的靈活運(yùn)用、棧及數(shù)組的掌握。2.2軟硬件的需求1） 系統(tǒng)要求：win98以上操作系統(tǒng)；2） 語言平臺(tái)：tc++或vc++6.0；3功能需求當(dāng)運(yùn)行程序時(shí)，在屏幕上顯示每一種方法八個(gè)皇后的相對位置，要用比較直觀的界面顯示。概要設(shè)計(jì)本課件學(xué)生是用循環(huán)遞歸循環(huán)來實(shí)現(xiàn)的，分別一一測試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個(gè)程序中，我的主要思路以及思想是這樣的：1） 解決沖突問題：這個(gè)問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；行：當(dāng)?shù)贗行被某個(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ù)贗個(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ù)組a[I]：a[I]表示第I個(gè)皇后放置的列；I的范圍：1..8;對角線數(shù)組：b[j]（主對角線）,c[j]（從對角線），根據(jù)程序的運(yùn)行，去決定主從對角線是否放入皇后；詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)4.1算法描述及詳細(xì)流程圖4.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)n<=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無法擺放時(shí)，便要進(jìn)行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷回溯”的尋找解的方法，稱為“回溯法”。C、 使用數(shù)組實(shí)現(xiàn)回溯法的思想。D、 當(dāng)n>8時(shí)，便打印出結(jié)果。E、 輸出函數(shù)我使用printf輸出，運(yùn)行形式為：第m種方法為：********4.1.2算法流程圖

5.代碼編寫及詳細(xì)注釋#include<conio.h>#include<math.h>#include<stdlib.h>#include<stdio.h>#include<iostream.h>#defineQUEENS8intiCount=0;//!記錄解的序號的全局變量。intSite[QUEENS]; //!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個(gè)解。intIsValid(intn);//!判斷第n個(gè)皇后放上去之后，是否有〉沖突。void main()/* Main :主函數(shù)。 */( system("title葉青--遞歸算法八皇后問題");cout<<" "<<"八皇后的解法："<<endl;cout<<" "<<" "<<endl;Queen(0);//!從第0行開始遞歸試探。getch();//!按任意鍵返回。}voidQueen(intn)/* Queen:遞歸放置第n個(gè)皇后，程序的核心! */(inti;if(n==QUEENS)//!參數(shù)n從0開始，等于8時(shí)便試出了一個(gè)解，將它輸出并回溯。( Output(); return;}for(i=1;i<=QUEENS;i++)//!r還沒到8，在第n行的各個(gè)行上依次試探。Site[n]=i;//!在該行的第i行上放置皇后。if(IsValid(n)) //!如果放置沒有沖突，就開始下一行的試探。Queen(n+1); })intIsValid(intn)/* IsValid:判斷第n個(gè)皇后放上去之后，是否合法，即是否無沖突。 */(inti;for(i=0;i<n;i++)〃將第n個(gè)皇后的位置依次于前面n—1個(gè)皇后的位置比較。( if(Site[i]==Site[n])//!兩個(gè)皇后在同一列上，返回0。return0;if(abs(Site[i]-Site[n])==(n-i))//兩個(gè)皇后在同一對角線上，返回0。return0; }return1;//!沒有沖突，返回1。}voidOutput()/* Output:輸出一個(gè)解，即一種沒有沖突的放置方案。 */(inti;printf("No.%-5d",++iCount);//!輸出序號。for(i=0;i<QUEENS;i++)//依次輸出各個(gè)行上的皇后的位置，即所在的列數(shù)。printf("%d",Site[i]);printf(〃\n〃)；}程序調(diào)試6.1調(diào)試過程、步驟及遇到的問題在完整程序調(diào)試時(shí)遇到幾個(gè)小問題，后經(jīng)細(xì)心改正后才把調(diào)試工作做完。例如:當(dāng)用printf輸出時(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)行了.運(yùn)行與測試7.1運(yùn)行演示

g葉青一遞歸算法八皇后問Jg1 八皇后的解法：No.l 15863724No.2 16837425No.3 17468253No.4 17582463No.5 24683175No.6 25713864No.7 25741863No.8 26174835No.9 26831475No.10 27368514No.11 27581463No.12 28613574No.13 31758246No.14 35281746No.15 35286471No.16 35714286No.17 35841726No.18 36258174No.19 36271485No.20 36275184No.21 36418572No.22 36428571No.23 36814752G葉青--遞歸算法八皇后問題No.68 6 3No.68 6 3No.69 6 3No.70 6 3No.71 6 3No.72 6 3No.73 6 3No.74 6 3No.75 6 3No.76 6 4No.77 6 4No.78 6 4No.79 6 4No.80 6 8No.81 7 1No.82 7 2No.83 7 2No.84 7 3No.85 7 3No.86 7 4No.87 7 4No.88 7 5No.89 8 2No.90 8 2No.91 8 3No.92 8 47 5 8 2 48 4 2 7 51 8 5 2 4 75 7 1 4 2 88 1 4 2 77 2 4 8 1 57 2 8 5 1 47 4 1 8 2 55 8 2 7 38 5 7 1 37 1 3 5 2 81 8 2 5 34 1 7 5 38 6 4 2 51 8 5 3 63 1 4 8 56 8 5 2 42 5 1 6 45 8 1 3 68 6 1 3 51 6 8 2 41 7 5 3 63 1 7 4 61 6 2 5 7 41 3 6 2 7 5通過了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)行周期，也可以將軟件的思路從繁化簡，并且都能夠通過數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴(kuò)充，發(fā)展；這也是在這次課程設(shè)計(jì)中我所掌握得到的。但由于我的基本知識還不是那么扎實(shí)，也缺乏對軟件設(shè)計(jì)的經(jīng)驗(yàn)，在這過程中也出現(xiàn)了一些問題，如，八皇后在變成初期由于沒真正體會(huì)到數(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ù)組知識加以運(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ì)上的滿足，更重要的是對自己編程思想的一次更新，以及對算法的一個(gè)全新的認(rèn)識！我覺得還可以考慮開發(fā)N皇后問題,在主界面中添加一個(gè)int型的變量，程序一開始要求輸入一個(gè)數(shù)（確定是幾皇后問題），輸入后按下enter后，輸出各種解.主程序與八皇后的求解大體相同.在這次課程設(shè)計(jì)中，我遇到了不少問題，包括程序上的和課程設(shè)計(jì)的撰寫上的，同學(xué)曾給過我許多幫助，在此我表示對他們的忠心感謝。同時(shí)，指導(dǎo)老師和實(shí)驗(yàn)人員