八皇后問(wèn)答教學(xué)規(guī)劃報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告八皇后問(wèn)題（院）: 數(shù)學(xué)學(xué)院業(yè)：信息與計(jì)算科學(xué)級(jí):02班學(xué)生姓名 王天宇 學(xué)號(hào):20096390 指導(dǎo)教師：設(shè)計(jì)任務(wù)書(shū)課題名稱1.用C+語(yǔ)言平臺(tái)將一個(gè)8*8的棋盤(pán)上放上8個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)設(shè)計(jì)現(xiàn).目的2.通過(guò)這次課程設(shè)計(jì)，提高自己的編程能力，熟悉C+的編程壞境，為以后的程序開(kāi)發(fā)打下基礎(chǔ).實(shí)驗(yàn)1)語(yǔ)言平臺(tái)：tc+ 或VC+6.0 ；環(huán)境2) 執(zhí)行文件：八皇后.exe試編寫(xiě)程序?qū)崿F(xiàn)將八個(gè)皇后放置在國(guó)際象棋棋盤(pán)的無(wú)沖突的位置上的算法，并任務(wù)給出所有的解。要求1.課題綜述1. 1課題的來(lái)源及意義八皇后問(wèn)題是一個(gè)古

2、老而著名的問(wèn)題，該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的。在國(guó)際象棋中，皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時(shí)，它就能把對(duì)方棋子吃掉。所以高斯提出了一個(gè)問(wèn)題：在8*8的格的國(guó)際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面，問(wèn)共有多少種解法。到了現(xiàn)代，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，這一古老而有趣的數(shù)學(xué)游戲問(wèn)題也自然而然的被搬到了計(jì)算機(jī)上。運(yùn)用所學(xué)計(jì)算機(jī)知識(shí)來(lái)試著解決這個(gè)問(wèn)題是個(gè)鍛煉和提高我自己編程能力和獨(dú)立解決問(wèn)題能力的好機(jī)會(huì)，可以使我增強(qiáng)信心，為我以后的編程開(kāi)個(gè)好頭，故我選擇了這個(gè)有趣的課

3、題。1. 2面對(duì)的問(wèn)題1） 解決沖突問(wèn)題: 這個(gè)問(wèn)題包括了行，列，兩條對(duì)角線;列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突;行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài);2）使用數(shù)據(jù)結(jié)構(gòu)的知識(shí)，用遞歸法解決問(wèn)題。2概要設(shè)計(jì)本課件學(xué)生是用循環(huán)遞歸循環(huán)來(lái)實(shí)現(xiàn)的，分別一一測(cè)試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來(lái)。在這個(gè)程序中，我的主要思路以及思想是這樣的:1 ）解決沖突問(wèn)題: 這個(gè)問(wèn)題包括了行，列，兩條對(duì)角線;列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突;行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的

4、標(biāo)記置為被占領(lǐng)狀態(tài);對(duì)角線：對(duì)角線有兩個(gè)方向。在這我把這兩條對(duì)角線稱為：主對(duì)角線和從對(duì)角線。在同一對(duì)角線上的所有點(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) 而對(duì)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，學(xué)生則是著重于 數(shù)組aI : a I表示第I個(gè)皇后放置的列；I的范圍：1.8;對(duì)角線數(shù)組：bj（主對(duì)角線）,cj（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后;3.詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)4.1.1算法描述數(shù)據(jù)初始化。B、從n列開(kāi)始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后

5、的要求）,先測(cè)試當(dāng)前位置（n , m）是否等于0 （未被占領(lǐng)）。如果是，擺放第n個(gè)皇后, 并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測(cè)試下一 個(gè)位置（n，m+1 ），但是如果當(dāng)nv=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無(wú)法擺放時(shí)，便要 進(jìn)行回溯。從問(wèn)題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不 斷“回溯”的尋找解的方法，稱為“回溯法”C、使用數(shù)組實(shí)現(xiàn)回溯法的思想。D、當(dāng)n>8時(shí)，便打印出結(jié)果。E、輸出函數(shù)我使用printf輸出，運(yùn)行形式為：第 m種方法為：*5.代碼編寫(xiě)及詳細(xì)注釋 #includeviostream> using names pace st

6、d;int a8,b8,c30,d30;int i, k,X=0,Y=0;void p rintOint t,n;Y+;coutvv"tNo."vvYvv": nt"/矩陣形式的第丫種情況for (k=1;kv9;k+)n=ak;for(t=1;tvn;t+)coutvv"x "coutvv"Q "t+;for(t;tv9;t+)coutvv"x "coutvv"nt"coutvv"n"void PI aceQueen(int i)int j ,e=1;f

7、or (j=1;jv9;j+)if (bj=0) &&( ci+j=0)&& (di-j=O)ai=j;bj=1;ci+j=1;di-j=1;if (i<8)PlaceQueen(i+1);elseprintO;II打印結(jié)果bj=0；/回溯ci+j=0;di-j=0;e+;int main()int choice,e=1;char ch;coutvv"nnt*Welcometo EightQueeninquiries software p roblems *nn"for( k=0;kv24;k+)/數(shù)據(jù)初始化bk=0;ck=0;dk=0

8、;ch='y'while(ch='y'|ch='Y')coutvv"ntcoutvv"nt* coutvv"nt*No.1視圖矩陣形式顯示皇后的位置*MNo.0coutvv"nt*coutvv"nt* coutvv"nt請(qǐng)選擇菜單號(hào)(No.0-No.1)M.cin>>choice;switch(choice)case 1:coutvv"nt使用回車(chē)查看下一種情況nn"P laceQueen(l);/從第1個(gè)皇后開(kāi)始放break;case 0:ch=' n'break;default:coutvv"ntt菜單選擇錯(cuò)誤，請(qǐng)重新輸入!n"7.運(yùn)行與測(cè)試7.1運(yùn)行演示（以下只是少部分