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

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

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

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

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

5、在這個程序設(shè)計中，它先進行判斷，棋盤上是否已經(jīng)得到一個完整的布局（即棋盤是否已經(jīng)擺上8個棋子），如果是，則輸出布局；如果不是則依次先根遍歷滿足約束條件的各棵子樹，流程即是：判斷該子樹根的布局是否合法：如果合法的話，則先根遍歷該子樹；如果不合法的話，則剪去該子樹的分支。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 棋盤模塊C碼算法void Checker(void) /* 畫棋盤函數(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) /* 畫皇后圖象，然后存儲到緩沖區(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); /* 畫淡藍(lán)色棋格 */setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);set

9、fillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */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); /* 計算緩沖區(qū)大小，然后存儲 */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) 下一棵要遍歷的子樹由狀態(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); 進入下一層遞歸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) /* 下一棵要遍歷的子樹由狀態(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); /* 進入下一層遞歸 */Q->Ax+7=0;Q->Bx+y+7=0;Q->Cx-y+7=0;3.3函數(shù)調(diào)用圖3.4項目流程圖四、調(diào)試分析通過編譯連接后，程序基本上把八皇后的92種擺法的都進行了演示； 但程序運行中也出現(xiàn)了以下缺點：因為八皇

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

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

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

18、后，并標(biāo)記，在下一次的時候，不再放入皇后；并在主從對角線進行判斷，標(biāo)記；然后再通過if語句判斷，如果行還沒有遍歷完，進入下一行；接著通過放入一個for語句進行分析，如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重置；當(dāng)所有工作完成后，無沖突后，就返回主函數(shù)，并通過編譯后對結(jié)果進行展示。七、附錄#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) /* 畫皇后圖象，然后存儲到緩沖區(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); /* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */ 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); /* 計算緩沖區(qū)大小，然后存儲 */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();void Checker(void) /* 畫棋盤函數(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)