數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(八皇后問題)

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　課題：八皇后問題</b></p><p>　　學(xué) 院：計(jì)算機(jī)科學(xué)與信息工程學(xué)院 </p><p>　　專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　年 級：2010級計(jì)本二班

2、 </p><p><b>　　八皇后問題</b></p><p><b>　　八皇后問題簡述:</b></p><p>　　八皇后問題，是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于

3、同一行、同一列或同一斜線上，問有多少種擺法。</p><p><b>　　解決思路：</b></p><p>　　先聲明我們根據(jù)條件可以知道皇后肯定是每行都有且只有一個(gè)所以我們創(chuàng)建一個(gè)數(shù)組x[t]讓數(shù)組角標(biāo)表示八皇后的行，用這個(gè)角標(biāo)對應(yīng)的數(shù)組值來確定這個(gè)皇后在這行的那一列。</p><p><b>　　我們用遞歸來做：</b&g

4、t;</p><p>　　這問題要求皇后所在的位置必須和其他皇后的位置不在同一行、列還有 把兩個(gè)皇后看成點(diǎn)其|斜率|=1；所以我們就要寫這個(gè)限定條件用一個(gè)函數(shù)來實(shí)現(xiàn)：函數(shù)內(nèi)對每一個(gè)已經(jīng)放好的皇后的位置進(jìn)行判斷，所以就要有個(gè)循環(huán)。</p><p>　　我們既然是用遞歸來解決問題那就要把這個(gè)問題分成一個(gè)個(gè)相同的小問題來實(shí)現(xiàn)。</p><p>　　不難發(fā)現(xiàn)我們要在8*8的

5、方格里放好8個(gè)皇后那我們就要知道在8（列）*7（行）是怎么放的在有我們事先寫好的判斷函數(shù)放好最后行就搞定了；以此類推我們要知道8*7的怎么方的我們就要知道8*6是怎么樣的就好了，所以我們是以一行怎么放作為一個(gè)單元。</p><p>　　我們就去建一個(gè)可以放好一行的函數(shù)backtrack（int t）里面的t表示是第幾行，在main函數(shù)調(diào)用的時(shí)候第一次傳進(jìn)來的是0也就是從第一行開始判斷。</p>&l

6、t;p>　　我們就開始寫函數(shù)體了：</p><p>　　每一行有8個(gè)位置可以放，每一個(gè)位置我們都要去判斷一下所以我們就用循環(huán)來搞定。</p><p>　　在這個(gè)循環(huán)里面我們讓x[t]=i也就是從這一行的第一個(gè)開始判斷。放好后就要去判斷是否符合條件。如果符合條件我們就在調(diào)用這個(gè)函數(shù)本身backtrack不過傳進(jìn)去的參數(shù)是t+1也就是下一行的意思。</p><p>

7、;　　在進(jìn)行判斷下一行之前我們要判斷一下t是不是等于8也就是已經(jīng)是最后一行了，如果是最后一行了我們就可以將其進(jìn)行輸出。打印8*8的矩陣（提示在寫一個(gè)函數(shù)）皇后的位置用1表示出來沒有的用0表示。</p><p><b>　　三.組員工作分配:</b></p><p>　　尹佐斌: 算法分析，代碼編寫，后期調(diào)試</p><p>　　黃文毅: 資料查

8、找，論文設(shè)計(jì)，代碼編寫 </p><p>　　檀衛(wèi)杰: 算法分析，代碼編寫，后期調(diào)試</p><p>　　馬賑耀: 論文設(shè)計(jì)，代碼編寫，后期調(diào)試 </p><p><b>　　代碼與注解：</b></p><p>　　#include <math.h></p><p>　　#i

9、nclude <stdio.h></p><p>　　#include<string.h></p><p>　　#include<conio.h> //用getch()要調(diào)用的頭文件</p><p>　　#include <stdlib.h> //

10、要用system函數(shù)要調(diào)用的頭文件</p><p>　　int SUM=0; //統(tǒng)計(jì)有多少種可能</p><p>　　int shezhi(){ //設(shè)置為N皇后問題</p><p><b>　　int N;</b></p><

11、p>　　printf("這是一個(gè)N皇后問題...\n請輸入N=");</p><p>　　scanf("%d",&N);</p><p><b>　　return N;</b></p><p><b>　　}</b></p><p>　　void

12、 Print(int N,int x[]) //印出結(jié)果</p><p><b>　　{ </b></p><p>　　int MAX=N;</p><p>　　for(int i=0;i<MAX;i++)</p><p><b>　　{</b></p>

13、<p>　　for(int j=0;j<MAX;j++)</p><p>　　if(j==x[i])</p><p>　　printf("●");</p><p><b>　　else</b></p><p>　　printf("○");</p>

14、<p>　　printf("\n");</p><p><b>　　}</b></p><p>　　SUM++; //打印一種情況統(tǒng)計(jì)一次</p><p>　　printf("\n");</p><p><b>

15、;　　}</b></p><p>　　int Judge(int k,int x[]) //判斷是否在同一直、橫、斜線上有其它棋子</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<

16、;k;i++)</p><p>　　if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函數(shù)名: abs; 功能: 求整數(shù)的絕對值 ;</p><p><b>　　return 0;</b></p><p><b>　　return 1;</b></p><

17、p><b>　　}</b></p><p>　　void backtrack(int t,int N,int x[]) // 把棋子放到棋盤上</p><p>　　{ int MAX=N;</p><p><b>　　int i;</b></p><p>　　for(

18、i=0;i<MAX;i++){</p><p><b>　　x[t]=i;</b></p><p>　　if(Judge(t,x))</p><p><b>　　{</b></p><p>　　if(t==MAX-1){</p><p>　　Print(MAX,x);

19、 // 找到其中一種放法，印出結(jié)果</p><p>　　} </p><p>　　else backtrack(t+1,N,x);</p><p><b>　　}</b></p><p><b>　　}</b></p&

20、gt;<p><b>　　}</b></p><p>　　void Introduce(){</p><p>　　printf("* * * * * * * * * * * * * * * * * *\n");</p><p>　　printf("* 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) *

21、\n");</p><p>　　printf("* *\n");</p><p>　　printf("* 組員：尹佐斌 黃文毅 *\n");</p><p>　　printf("* 檀衛(wèi)杰 馬賑耀

22、 *\n");</p><p>　　printf("* *\n");</p><p>　　printf("* * * * * * * * * * * * * * * * * *\n");</p><p>　　printf("\n\n

23、");</p><p>　　printf("1.設(shè)置為N皇后問題。\n");</p><p>　　printf("2.輸出棋局排布結(jié)果。\n");</p><p>　　printf("3.統(tǒng)計(jì)棋局排布總數(shù)。\n");</p><p>　　printf("4.清屏

24、。\n");</p><p>　　printf("\n\n");</p><p><b>　　} </b></p><p>　　void main()</p><p>　　{ int N;</p><p>　　int x[10]; </p><

25、;p>　　printf("\n\n\n");</p><p>　　char flag=1;</p><p>　　while(flag){</p><p><b>　　int n;</b></p><p>　　Introduce(); </p><p><b>　

26、　char a;</b></p><p>　　printf("您確定要進(jìn)行上述操作嗎?(Y/N):");</p><p>　　a=getchar();</p><p>　　while(a=='Y'||a=='y'){</p><p>　　printf("請選擇：&quo

27、t;);</p><p>　　scanf("%d",&n);</p><p>　　switch(n){</p><p><b>　　case 1:</b></p><p>　　N=shezhi();</p><p><b>　　break;</b>

28、</p><p><b>　　case 2:</b></p><p>　　backtrack(0,N,x);</p><p>　　printf("按任意鍵返回...");</p><p><b>　　getch();</b></p><p>　　syste

29、m("cls");</p><p>　　Introduce();</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　printf("統(tǒng)計(jì)結(jié)果:%d\n",SUM);</p>

30、<p>　　printf("按任意鍵返回...");</p><p><b>　　getch();</b></p><p>　　system("cls");</p><p>　　Introduce();</p><p><b>　　break;</b>

31、;</p><p><b>　　case 4:</b></p><p>　　printf("按任意鍵返回...");</p><p><b>　　getch();</b></p><p>　　system("cls");</p><p>

32、;　　Introduce();</p><p><b>　　break;</b></p><p><b>　　default:</b></p><p>　　printf("輸入錯(cuò)誤...\n");</p><p>　　printf("按任意鍵返回...");&

33、lt;/p><p><b>　　getch();</b></p><p>　　system("cls");</p><p>　　Introduce();</p><p><b>　　break;</b></p><p><b>　　}</b&g

34、t;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　五.運(yùn)行效果（截圖）:</p><p><b>　?。?lt;/b></p>

35、<p><b>　　功能簡述：</b></p><p>　　解決八皇后問題根本（遞歸法）</p><p>　　可上升為解決“N皇后問題”</p><p>　　以直觀形式輸出棋局排布</p><p>　　統(tǒng)計(jì)棋子排布方法總數(shù)</p><p><b>　　清屏函數(shù)的調(diào)用</b

36、></p><p><b>　　心得體會</b></p><p>　　本次我們組做的是“八皇后問題”，這是一個(gè)歷史經(jīng)典問題，經(jīng)過資料查找，我們發(fā)現(xiàn)關(guān)于八皇后問題的算法甚多，比如：回溯法，迭代法，遞歸法，殘卷法等。經(jīng)組員討論，最后我們決定使用遞歸的方法解決該問題，分工合作。雖然我們遇到了很多問題，但是經(jīng)過資料查找，和網(wǎng)上提問，我們最終解決了問題。</p>