數(shù)據(jù)結構課程設計(八皇后問題)

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

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

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

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

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

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

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

8、找，論文設計，代碼編寫 </p><p>　　檀衛(wèi)杰: 算法分析，代碼編寫，后期調試</p><p>　　馬賑耀: 論文設計，代碼編寫，后期調試 </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()要調用的頭文件</p><p>　　#include <stdlib.h> //

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

11、p>　　printf("這是一個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[]) //印出結果</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)計一次</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、 // 找到其中一種放法，印出結果</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ù)結構課程設計 *

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.設置為N皇后問題。\n");</p><p>　　printf("2.輸出棋局排布結果。\n");</p><p>　　printf("3.統(tǒng)計棋局排布總數(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("您確定要進行上述操作嗎?(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)計結果:%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("輸入錯誤...\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>　　五.運行效果（截圖）:</p><p><b>　?。?lt;/b></p>

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

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