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

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

2、老而著名的問題，該問題是十九世紀(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ī)會，可以使我增強(qiáng)信心，為我以后的編程開個(gè)好頭，故我選擇了這個(gè)有趣的課

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

4、標(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ù)組aI : a I表示第I個(gè)皇后放置的列；I的范圍：1.8;對角線數(shù)組：bj（主對角線）,cj（從對角線），根據(jù)程序的運(yùn)行，去決定主從對角線是否放入皇后;3.詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)4.1.1算法描述數(shù)據(jù)初始化。B、從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后

5、的要求）,先測試當(dāng)前位置（n , m）是否等于0 （未被占領(lǐng)）。如果是，擺放第n個(gè)皇后, 并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測試下一 個(gè)位置（n，m+1 ），但是如果當(dāng)nv=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種方法為：*5.代碼編寫及詳細(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請選擇菜單號(No.0-No.1)M.cin>>choice;switch(choice)case 1:coutvv"nt使用回車查看下一種情況nn"P laceQueen(l);/從第1個(gè)皇后開始放break;case 0:ch=' n'break;default:coutvv"ntt菜單選擇錯(cuò)誤，請重新輸入!n"7.運(yùn)行與測試7.1運(yùn)行演示（以下只是少部分