數(shù)據(jù)結(jié)構(gòu)八皇后問(wèn)題實(shí)習(xí)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告專業(yè)：數(shù)字媒體技術(shù)姓名：李義年級(jí)：2013級(jí)學(xué)號(hào)：201301052015完成日期：2015.12.31題目：八皇后問(wèn)題一、項(xiàng)目簡(jiǎn)介八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8´8格的國(guó)際象棋棋盤(pán)上，安放八個(gè)皇后，要求沒(méi)有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即任意兩個(gè)皇后都不能處于同一行、同一列或同一條對(duì)角線上，求解有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法得出結(jié)論，有92種擺法。二、概要設(shè)計(jì)2.1 主要模塊：這個(gè)程序主要由4個(gè)模

2、塊組成，分別是畫(huà)棋盤(pán)模塊，畫(huà)皇后模塊，輸出皇后擺法模塊，和解決如何擺置皇后模塊。這4個(gè)模塊隸屬于主函數(shù)模塊。既主函數(shù)通過(guò)對(duì)這4個(gè)模塊的合理調(diào)用解決“8皇后問(wèn)題”，同時(shí)這4個(gè)模塊之間也互有調(diào)用。2.2 程序設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)及其關(guān)系：數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：數(shù)組ai：a i表示第i個(gè)皇后放置的列；i的范圍：1-8;對(duì)角線數(shù)組：bj(主對(duì)角線),cj（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；然后進(jìn)行數(shù)據(jù)的初始化。從n列開(kāi)始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測(cè)試當(dāng)前位置(n,m)是否等于（未被占領(lǐng)）:如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(切記要橫列豎列斜列一起來(lái))，接

3、著進(jìn)行遞歸；如果不是，測(cè)試下一個(gè)位置(n,m+1)，但是如果當(dāng)時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無(wú)法擺放時(shí)，便要進(jìn)行回溯。三 、詳細(xì)設(shè)計(jì)3.1 定義相關(guān)的數(shù)據(jù)類型：3.1.1 定義的相關(guān)數(shù)據(jù)類型：int A21,B21,C21,Y8;void *buff1,*buff23.1.2 設(shè)計(jì)思想：本程序通過(guò)對(duì)子函數(shù)void qu(int i)的調(diào)用，將八皇后的問(wèn)題關(guān)鍵通過(guò)數(shù)據(jù)結(jié)構(gòu)的思想予以了實(shí)現(xiàn)。雖然題目以及演算看起來(lái)都比較復(fù)雜，繁瑣，但在實(shí)際中，只要當(dāng)一只皇后放入棋盤(pán)后，在橫與列、斜線上沒(méi)有另外一只皇后與其沖突，再對(duì)皇后的定位進(jìn)行相關(guān)的判斷。即可完成。如果在這個(gè)程序中，我們運(yùn)用的是非遞歸的思想，那么將大量使用if

4、等語(yǔ)句，并通過(guò)不斷的判斷，去推出答案，而且這種非遞歸的思想，大大的增加了程序的時(shí)間復(fù)雜度。如果我們使用了數(shù)據(jù)結(jié)構(gòu)中的算法后，那么程序的時(shí)間復(fù)雜度，以及相關(guān)的代碼簡(jiǎn)化都能取得不錯(cuò)的改進(jìn)。這個(gè)程序，我運(yùn)用到了數(shù)據(jù)結(jié)構(gòu)中的棧、數(shù)組，以及樹(shù)和回溯的方法。特別是在對(duì)于樹(shù)以及二叉樹(shù)的學(xué)習(xí)，更是為八皇后的問(wèn)題提供了科學(xué)的解決方案，通過(guò)對(duì)樹(shù)的分析，把八皇后的問(wèn)題看成了樹(shù)，而在衍生第一個(gè)變化后，上面的第一層八個(gè)變化就變成了八個(gè)結(jié)點(diǎn)，而這八個(gè)結(jié)點(diǎn)再繼續(xù)的衍生，這樣比較形象的將八皇后的問(wèn)題簡(jiǎn)單化了。然后再通過(guò)回溯法進(jìn)行設(shè)計(jì)，回溯法是設(shè)計(jì)遞歸過(guò)程的一個(gè)重要的方法。它的求解過(guò)程實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹(shù)“的過(guò)程。

5、在這個(gè)程序設(shè)計(jì)中，它先進(jìn)行判斷，棋盤(pán)上是否已經(jīng)得到一個(gè)完整的布局（即棋盤(pán)是否已經(jīng)擺上8個(gè)棋子），如果是，則輸出布局；如果不是則依次先根遍歷滿足約束條件的各棵子樹(shù)，流程即是：判斷該子樹(shù)根的布局是否合法：如果合法的話，則先根遍歷該子樹(shù)；如果不合法的話，則剪去該子樹(shù)的分支。3.2 相關(guān)代碼及算法3.2.1 主模塊C碼算法：void main(void)Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:/Win-TC");SetQueen(&Q);setcolor(YELLOW);Qu

6、eenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,"Eight Queens");setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,"2009.11.8 3:30pm");QueenRe(&Q,0);getch();closegraph();3.2.2 棋盤(pán)模塊C碼算法void Checker(void) /* 畫(huà)棋盤(pán)函數(shù) */int i,k;for(k=0;k<8;k+)

7、for(i=0;i<8;i+)if(k%2=0&&i%2=0|k%2!=0&&i%2!=0)setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);elsesetfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20)

8、;floodfill(i*20+10,20+k*20+10,WHITE);3.2.3 皇后模塊C碼算法：void QueenPic(void) /* 畫(huà)皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ int size,polypoints110=9,1,11,1,20,20,1,20,9,1,polypoints210=29,1,31,1,40,20,21,20,29,1;setfillstyle(SOLID_FILL,LIGHTBLUE); /* 畫(huà)淡藍(lán)色棋格 */setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);set

9、fillstyle(SOLID_FILL,WHITE); /* 畫(huà)白色棋格 */setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */buff1=(

10、void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();3.2.4 八皇后擺放方法模塊C碼:void QueenRe(Queen *Q, int y) 八皇后的遞歸算法int x;if(y>7)return;for(x=0;x<8;x+)if(!Q->Ax+7&&!Q->Bx+y+7&&!Q->Cx-y+7) 下一棵要遍歷的子樹(shù)由狀態(tài)數(shù)確定 Q->Yy=x;

11、放置皇后Q->Ax+7=1;標(biāo)記下次這里不能放置皇后Q->Bx+y+7=1;標(biāo)記下次這里不能放置皇后Q->Cx-y+7=1; 標(biāo)記下次這里不能放置皇后if(y=7)PrintQueen(Q);調(diào)用輸出圖形函數(shù)QueenRe(Q,y+1); 進(jìn)入下一層遞歸Q->Ax+7=0;如果上次擺法導(dǎo)致后面不能繼續(xù)擺放則重置標(biāo)記為0 Q->Bx+y+7=0;Q->Cx-y+7=0;3.2.5 初始化模塊C碼:void SetQueen(Queen *Q) /* 初始化 */ int i;for(i=0;i<21;i+)Q->Ai=0; Q->Bi=0;Q

12、->Ci=0;初始化為0，表示可以放置皇后。 for(i=0; i<8; i+)Q->Yi=-1;3.2.6 圖形輸出：void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */int k;char str20;static total=0;total+;setviewport(240,80,400,260,1); /* 設(shè)置窗口 */sprintf(str,"NO.%d",total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k&l

13、t;8;k+)if(k%2=0&&t->Yk%2=0|k%2!=0&&t->Yk%2!=0)putimage(t->Yk)*20,20+k*20,buff1,COPY_PUT);elseputimage(t->Yk)*20,20+k*20,buff2,COPY_PUT);getch();if(getch()=27) exit(0);clearviewport();void QueenRe(Queen *Q, int y) /* 八皇后的遞歸算法 */ int x;if(y>7)return;for(x=0;x<8;x+)if(

14、!Q->Ax+7&&!Q->Bx+y+7&&!Q->Cx-y+7) /* 下一棵要遍歷的子樹(shù)由狀態(tài)數(shù)確定 */Q->Yy=x;Q->Ax+7=1;Q->Bx+y+7=1;Q->Cx-y+7=1;if(y=7)PrintQueen(Q);QueenRe(Q,y+1); /* 進(jìn)入下一層遞歸 */Q->Ax+7=0;Q->Bx+y+7=0;Q->Cx-y+7=0;3.3函數(shù)調(diào)用圖3.4項(xiàng)目流程圖四、調(diào)試分析通過(guò)編譯連接后，程序基本上把八皇后的92種擺法的都進(jìn)行了演示； 但程序運(yùn)行中也出現(xiàn)了以下缺點(diǎn)：因?yàn)榘嘶?/p>

15、后的表現(xiàn)方法甚多，輸出后雖能全部顯示，但未能使屏幕停留，把一個(gè)一個(gè)的將其顯示出來(lái),但是這樣便使得操作步驟太多,也會(huì)造成不必要的麻煩!所以只畫(huà)出了第一種和最后一種的輸出結(jié)果，演示如圖所示：五、設(shè)計(jì)體會(huì)該程序在調(diào)試的過(guò)程中出現(xiàn)了不少的問(wèn)題！如數(shù)據(jù)溢出等（是自己過(guò)于粗心而造成的）。在調(diào)試的過(guò)程中出現(xiàn)的一個(gè)最大的問(wèn)題就是：在運(yùn)行的時(shí)候出現(xiàn)解的個(gè)數(shù)大于自己所預(yù)計(jì)的。經(jīng)過(guò)不斷的查看內(nèi)存變量，操作次數(shù)但還是沒(méi)有找出問(wèn)題的所在。終于在晚上十二點(diǎn)的時(shí)候，決定睡覺(jué)！但一關(guān)上電腦，躺在床上的時(shí)候，突然想到了一個(gè)問(wèn)題：經(jīng)過(guò)讀了一些資料，知道八皇后問(wèn)題有12組實(shí)質(zhì)解，92組全解這說(shuō)明在這12組實(shí)質(zhì)解中有其中的一組解是比

16、其它的解要特殊一點(diǎn)的：其它的解經(jīng)過(guò)等價(jià)的變換之后都會(huì)產(chǎn)生8組等價(jià)的解，只有這個(gè)特殊的解只有4組等價(jià)的解。說(shuō)不定我的問(wèn)題就出在這里！我之前也寫(xiě)了一些有關(guān)的代碼處理這個(gè)問(wèn)題，但我之前以為這個(gè)特殊的解是一個(gè)完全中心對(duì)稱的圖形（每轉(zhuǎn)90度得到的圖形就是它自己本身），所以我的在這里的判斷就出現(xiàn)錯(cuò)誤了！后來(lái)經(jīng)過(guò)相關(guān)代碼的修改，問(wèn)題終于解決了，程序正確運(yùn)行。本課程設(shè)計(jì)本人的目的也是通過(guò)用WIN-TC程序設(shè)計(jì)平臺(tái)將一個(gè)的棋盤(pán)上放上個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)最終將其問(wèn)題變得一目了然，更加易懂。六、用戶使用說(shuō)明6.1 程序的使用平臺(tái)：系統(tǒng)要求：win

17、dows2000以上操作系統(tǒng)；語(yǔ)言開(kāi)發(fā)平臺(tái)：WIN-TC；6.2 源代碼分析：首先對(duì)程序中的函數(shù)頭文件進(jìn)行引入，定位；在這個(gè)程序中，與其他C+的程序一樣，都是引入：#include<iostream.h>；然后開(kāi)始定義里面的函數(shù)所需要的數(shù)組，其中，setviewport(240,80,400,260,1);是對(duì)總的棋盤(pán)狀態(tài)數(shù)進(jìn)行定位，記錄。接著，進(jìn)入了主函數(shù)，在主函數(shù)中，先對(duì)棋盤(pán)進(jìn)行初始化，并規(guī)定了在程序輸出時(shí)的情況；然后，對(duì)行列，對(duì)角線也進(jìn)行了初始化；并在對(duì)這些元素初始后，對(duì)子函數(shù)進(jìn)行調(diào)用； 進(jìn)入子函數(shù)后，便馬上對(duì)皇后放入的位置進(jìn)行判斷，通過(guò)語(yǔ)句的判斷，如果沒(méi)有沖突的話，則放下皇

18、后，并標(biāo)記，在下一次的時(shí)候，不再放入皇后；并在主從對(duì)角線進(jìn)行判斷，標(biāo)記；然后再通過(guò)if語(yǔ)句判斷，如果行還沒(méi)有遍歷完，進(jìn)入下一行；接著通過(guò)放入一個(gè)for語(yǔ)句進(jìn)行分析，如果前次的皇后放置導(dǎo)致后面的放置無(wú)論如何都不能滿足要求，則回溯，重置；當(dāng)所有工作完成后，無(wú)沖突后，就返回主函數(shù)，并通過(guò)編譯后對(duì)結(jié)果進(jìn)行展示。七、附錄#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <dos.h>#include <graphics.h>void *buff1,*buff2;typ

19、edef structint A21,B21,C21,Y8;Queen;void SetQueen(Queen *Q) /* 初始化 */ int i;for(i=0;i<21;i+)Q->Ai=0;Q->Bi=0;Q->Ci=0;for(i=0; i<8; i+)Q->Yi=-1;void QueenPic(void) /* 畫(huà)皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ int size,polypoints110=9,1,11,1,20,20,1,20,9,1,polypoints210=29,1,31,1,40,20,21,20,29,1;setfillstyl

20、e(SOLID_FILL,LIGHTBLUE); /* 畫(huà)淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 畫(huà)白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,pol

21、ypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();void Checker(void) /* 畫(huà)棋盤(pán)函數(shù) */int i,k;for(k=0;k<8;k+)for(i=0;i<8;i+)i

22、f(k%2=0&&i%2=0|k%2!=0&&i%2!=0)setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);elsesetfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */int k;char str20;static total=0;total+;setviewport(240,80,400,260,1); /* 設(shè)置窗口 */sprintf(str,"NO.%d",total);setcolor(GREEN);settextstyle(0,0,1)