八皇后問題課程設(shè)計報告

v1.0可編寫可改正數(shù)據(jù)構(gòu)造課程設(shè)計報告設(shè)計題目：八皇后問題系（院）:數(shù)學(xué)學(xué)院專業(yè)：信息與計算科學(xué)班級：02班學(xué)生姓名王天宇學(xué)號:指導(dǎo)教師:設(shè)計任務(wù)書課題八皇后1v1.0可編寫可改正名稱用c++語言平臺將一個８＊８的棋盤上放上８個皇后，使得每一個皇后既攻擊不到此外七個皇后，也不被此外七個皇后所攻擊的92種構(gòu)造予以實設(shè)計現(xiàn)．目的經(jīng)過此次課程設(shè)計,提升自己的編程能力,熟習(xí)c++的編程壞境,為此后的程序開發(fā)打下基礎(chǔ).實驗1）語言平臺：tc++或vc++；環(huán)境2）履行文件：八皇后.exe試編寫程序?qū)崿F(xiàn)將八個皇后擱置在國際象棋棋盤的無矛盾的地點(diǎn)上的算法，并任務(wù)給出全部的解。要求2v1.0可編寫可改正課題綜述1課題的根源及意義八皇后問題是一個古老而有名的問題，該問題是十九世紀(jì)有名的數(shù)學(xué)家高斯1850年提出的。在國際象棋中，皇后是最有權(quán)益的一個棋子；只需其他棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時，它就能把對方棋子吃掉。所以高斯提出了一個問題：在8*8的格的國際象棋上擺放八個皇后，使其不可以互相攻擊，即隨意兩個皇后都不可以處于同一列、同一行、或同一條斜線上邊，問共有多少種解法。到了現(xiàn)代，跟著計算機(jī)技術(shù)的飛快發(fā)展，這一古老而風(fēng)趣的數(shù)學(xué)游戲問題也自但是然的被搬到了計算機(jī)上。運(yùn)用所學(xué)計算機(jī)知識來試著解決這個問題是個鍛煉和提升我自己編程能力和獨(dú)立解決問題能力的好時機(jī)，能夠使我加強(qiáng)信心，為我此后的編程開個好頭，故我選擇了這個風(fēng)趣的課題。2面對的問題1）解決矛盾問題：這個問題包含了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的矛盾；行：當(dāng)?shù)贗行被某個皇后占據(jù)后，則同一行上的全部空格都不可以再放皇后，要把以I為下標(biāo)的標(biāo)志置為被占據(jù)狀態(tài)；2）使用數(shù)據(jù)構(gòu)造的知識，用遞歸法解決問題。綱要設(shè)計本課件學(xué)生是用循環(huán)遞歸循環(huán)來實現(xiàn)的，分別一一測試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個程序中，我的主要思路以及思想是這樣的：1）解決矛盾問題：1v1.0可編寫可改正這個問題包含了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的矛盾；行：當(dāng)?shù)贗行被某個皇后占據(jù)后，則同一行上的全部空格都不可以再放皇后，要把以I為下標(biāo)的標(biāo)志置為被占據(jù)狀態(tài)；對角線：對角線有兩個方向。在這我把這兩條對角線稱為：主對角線和從對角線。在同一對角線上的全部點(diǎn)（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。所以，當(dāng)?shù)贗個皇后占據(jù)了第J列后，要同時把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占據(jù)狀態(tài)。2）數(shù)據(jù)構(gòu)造的實現(xiàn)而關(guān)于數(shù)據(jù)構(gòu)造的實現(xiàn)，學(xué)生則是側(cè)重于:數(shù)組a[I]：a[I]表示第I個皇后擱置的列；I的范圍：1..8;對角線數(shù)組：b[j](主對角線),c[j]（從對角線），依據(jù)程序的運(yùn)轉(zhuǎn)，去決定主從對角線能否放入皇后；詳盡設(shè)計和實現(xiàn)算法描繪A、數(shù)據(jù)初始化。B、從n列開始擺放第n個皇后（由于這樣便能夠切合每一豎列一個皇后的要求），先測試目前地點(diǎn)（n，m）能否等于0（未被占據(jù)）。假如是，擺放第n個皇后，并宣告占據(jù)（記得姚橫列豎列斜列一同設(shè)置），接著進(jìn)行遞歸；假如不是，測試下一個地點(diǎn)（n，m+1），可是假如當(dāng)n<=8，m=8時，發(fā)現(xiàn)此時已沒法擺放時，便要進(jìn)行回溯。從問題的某一種可能出發(fā)，搜尋從這類狀況能出發(fā)，持續(xù)搜尋，這類不停“回溯”的找尋解的方法，稱為“回溯法”。C、使用數(shù)組實現(xiàn)回溯法的思想。D、當(dāng)n>8時，便打印出結(jié)果。2v1.0可編寫可改正E、輸出函數(shù)我使用printf輸出，運(yùn)轉(zhuǎn)形式為：第m種方法為：********代碼編寫及詳盡說明#include<iostream>usingnamespacestd;inta[8],b[8],c[30],d[30];inti,k,X=0,Y=0;voidprint( ){intt,n;Y++;cout<<"\tNo."<<Y<<