八皇后問題_實(shí)驗(yàn)報(bào)告_源程序.doc

《八皇后問題_實(shí)驗(yàn)報(bào)告_源程序.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、八皇后問題實(shí)驗(yàn)報(bào)告需求分析八皇后問題是一個(gè)古老而著名的問題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的。八皇后問題要求在一個(gè)８＊８的棋盤上放上８?jìng)€(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊．按照國(guó)際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子，問有多少種不同的擺法？并找出所有的擺法。因此，八皇后問題等于要求八個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上。而本課程設(shè)計(jì)本人的目的也是通過C語言平臺(tái)將一個(gè)８＊８的棋盤上放上８?jìng)€(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后

2、所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．最終將其問題變得一目了然，更加易懂。概要分析本課件學(xué)生是用遞歸來實(shí)現(xiàn)的，分別一一測(cè)試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個(gè)程序中，學(xué)生的主要思路以及思想是這樣的：1.解決沖突問題：這個(gè)問題包括了行，列，兩條對(duì)角線；列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；行：當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；對(duì)角線：對(duì)角線有兩個(gè)方向。在這學(xué)生把這兩條對(duì)角線稱為：主對(duì)角線和從對(duì)角線。在同一對(duì)角線上的所有點(diǎn)（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)

3、是常數(shù)。因此，當(dāng)?shù)趇個(gè)皇后占領(lǐng)了第j列后，要同時(shí)把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。(1)滿足上述條件的八個(gè)皇后，必然是每行一個(gè)，每列一個(gè)。(2)棋盤上任意一行、任意一列、任意一條斜線上都不能有兩個(gè)皇后。如果我們把8×8的棋盤看成是一個(gè)平面直角坐標(biāo)系，則八皇后問題就可以用數(shù)學(xué)語言來描述了，任意兩個(gè)皇后在平面上的坐標(biāo)應(yīng)該同時(shí)滿足以下三個(gè)條件：①兩個(gè)皇后不在同一行：兩個(gè)皇后的橫坐標(biāo)不相等；②兩個(gè)皇后不在同一列：兩個(gè)皇后的縱坐標(biāo)不相等；③兩個(gè)皇后不在同一條斜線上：兩個(gè)皇后的橫坐標(biāo)之差的絕對(duì)值不等于兩個(gè)皇后的縱坐標(biāo)之差的絕對(duì)值。2.數(shù)據(jù)結(jié)構(gòu)的實(shí)

4、現(xiàn)對(duì)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，則是著重于:（1）數(shù)組chess[i]：chess[i]表示第i個(gè)皇后放置的列；i的范圍：1-8;3對(duì)角線數(shù)組：b[j](主對(duì)角線),c[j]（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；（2）數(shù)據(jù)初始化。（3）從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先用check函數(shù)測(cè)試當(dāng)前位置是否未被占領(lǐng):如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(切記要橫列豎列斜列一起來)，接著進(jìn)行遞歸；如果不是，測(cè)試下一個(gè)位置(n,m+1)，但是如果當(dāng)n<=8,m=8時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無法擺放時(shí)，便要進(jìn)行回溯。（4）當(dāng)n

5、>8時(shí)，便一一打印出結(jié)果。詳細(xì)設(shè)計(jì)3.設(shè)計(jì)思想：本程序通過對(duì)關(guān)鍵函數(shù)putchess的調(diào)用，將八皇后的問題關(guān)鍵通過數(shù)據(jù)結(jié)構(gòu)的思想予以了實(shí)現(xiàn)。雖然題目以及演算看起來都比較復(fù)雜，繁瑣，但在實(shí)際中，只要當(dāng)一只皇后放入棋盤后，在橫與列、斜線上沒有另外一只皇后與其沖突，再對(duì)皇后的定位進(jìn)行相關(guān)的判斷。即可完成。如果在這個(gè)程序中，我們運(yùn)用的是非遞歸的思想，那么將大量使用if等語句，并通過不斷的判斷，去推出答案，而且這種非遞歸的思想，大大的增加了程序的時(shí)間復(fù)雜度。如果我們使用了數(shù)據(jù)結(jié)構(gòu)中的算法后，那么程序的時(shí)間復(fù)雜度，以及相關(guān)的代碼簡(jiǎn)化都能取得不錯(cuò)的改進(jìn)。這個(gè)程序，我運(yùn)

6、用到了數(shù)據(jù)結(jié)構(gòu)中的數(shù)組和回溯的方法。通過回溯法進(jìn)行設(shè)計(jì)，回溯法是設(shè)計(jì)遞歸過程的一個(gè)重要的方法。它的求解過程實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹“的過程。在這個(gè)程序設(shè)計(jì)中，它先進(jìn)行判斷，棋盤上是否已經(jīng)得到一個(gè)完整的布局（即棋盤是否已經(jīng)擺上8個(gè)棋子），如果是，則輸出布局；如果不是，則繼續(xù)放置下一個(gè)皇后。4.源代碼分析：數(shù)組chess[8]記錄了每個(gè)可行結(jié)果中，每行皇后的位置，以數(shù)字1-8表示。子函數(shù)check檢查對(duì)于每個(gè)i,新的皇后是否與第i行沖突。子函數(shù)showchess將每個(gè)符合要求的chess[8]輸出到文件8QANS.txt。子函數(shù)putchess用遞歸

7、放置每行的皇后，并調(diào)用函數(shù)check檢查可行性。如果此棋盤已排滿，則調(diào)用showchess函數(shù)輸出布局。主函數(shù)中調(diào)用putchess函數(shù)做主要工作。5.可改進(jìn)處：輸出到文件的形式可以優(yōu)化為棋盤模式，甚至優(yōu)化過的圖形模式。代碼展示//八皇后問題，結(jié)果輸出到同目錄下的8Qans.txt。#includeintresult=1;intchess[8];intcheck(intn){//依次檢查新的皇后是否與第i行沖突3inti;for(i=1;i<=n-1;i++){if(chess[n]==chess[i]+(n-i)

8、

9、chess[n]=

10、=chess[i]-(n-i)

11、

12、chess[n]==chess[i])retu