n皇后問題實(shí)驗(yàn)報告材料

1、精選優(yōu)質(zhì)文檔-傾情為你奉上N后問題算法一、實(shí)驗(yàn)?zāi)康募耙笏婕盎蛘莆盏闹R：1. 了解皇后相互攻擊的條件：如果任意兩個皇后在同一行，同一列或同一對角線，則她們相互攻擊。2. 運(yùn)用迭代的方法實(shí)現(xiàn)6皇后問題，求解得到皇后不相互攻擊的一個解3. 在運(yùn)用迭代的方法實(shí)現(xiàn)編程時，要注意回溯點(diǎn)二、問題描述及實(shí)驗(yàn)內(nèi)容對6皇后問題求解，用數(shù)組c16來存皇后的位置。ci=j表示第i個皇后放在第j列。最后程序運(yùn)行的結(jié)果是c16=1,5,8,6,3,7 三、問題分析和算法描述6-QUEENS的算法表示：輸入：空。輸出：對應(yīng)于6皇后問題的解的向量c16=1,5,8,6,3,71. for k=1 to 62. ck=

2、0 /沒有放皇后3. end for4. flag=false5. k=16. while k=17. while ck=58. ck=ck+19. if c為合法著色 then set flag=ture 且從兩個while循環(huán)退出10. else if c是部分解 then k=k+111. end while12. ck=0 /回溯并ck=013. k=k-114. end while15. if flag then output c16. else output “no solution”四、具體實(shí)現(xiàn)# include #include #include #include #inclu

3、de iostream using namespace std;int total = 0; /方案計(jì)數(shù) void backtrace(int queen,int N) int i, j, k; cout為皇后放置位置n;for (i=1;) /首先安放第1行 if(queeniN) /皇后還可調(diào)整 k=0; /檢查與第k個皇后是否互相攻擊 while(ki&abs(queenk-queeni)&(abs(queenk-queeni)-abs(k-i) k+; if (k=i-1) /與第k個皇后互相攻擊 queeni+; /第i個皇后右移一列，重測 continue; i+; /無沖突，安置

4、下一行皇后 if(iN) continue; cout第total+1種為：n; for(int i=0;iN;i+) for(int j=0;jqueeni;j+) cout; cout; for(int k=queeni+1;kN;k+) cout; coutendl; total+; /方案數(shù)加1 if(total%5=0) coutendl; queenN-1+; / 將第8個皇后右移一列，前8個不動 i=N-1; /此處是制造機(jī)會，如不成功則回溯，關(guān)鍵一步 else /當(dāng)前行皇后無法安置，回溯 queeni=0; /當(dāng)前行皇后回歸1列 i-; /回溯到前一行皇后 if(i0) /回溯

5、到數(shù)組1行之前，結(jié)束 coutn針對 N 皇后問題，一共找到 total 種放置方法。 endl; coutendl; return; else queeni+; /前一行皇后右移一列 void main() while(1) clock_t start, finish; double duration; int N; cout請輸入皇后個數(shù)：N; int* queen=new intN; for (int i=0;iN;i+) queeni = 0; /八皇后全放在第0列 int n=N; /* 定義數(shù)組pN用來存放結(jié)果序列，n為行號 */ start=clock(); total=0; b

6、acktrace(queen,N); finish=clock(); duration=(double)(finish-start); cout為找出放置方法系統(tǒng)共耗時 duration/1000 秒！nendl; delete queen; 運(yùn)行結(jié)果：回溯法求解八皇后問題2010-10-29 18:28:56|分類：|標(biāo)簽：|舉報|字號訂閱問題描述：八皇后問題是一個以國際象棋為背景的問題：如何能夠在 88 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。問題歷史：八皇后問題最早是由國際象棋棋手馬克斯貝瑟爾于

7、1848年提出。之后陸續(xù)有數(shù)學(xué)家對其進(jìn)行研究，其中包括高斯和康托，并且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年，S.岡德爾提出了一個通過行列式來求解的方法，這個方法后來又被J.W.L.格萊舍加以改進(jìn)。轉(zhuǎn)化規(guī)則：其實(shí)八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)閚n，而皇后個數(shù)也變成n。當(dāng)且僅當(dāng) n = 1 或 n 4 時問題有解。令一個一位數(shù)組an保存所得解，其中ai 表示把第i個皇后放在第i行的列數(shù)（注意i的值都是從0開始計(jì)算的），下面就八皇后問題做一個簡單的從規(guī)

8、則到問題提取過程。（1）因?yàn)樗械幕屎蠖疾荒芊旁谕涣?，因此?shù)組的不能存在相同的兩個值。（2）所有的皇后都不能在對角線上，那么該如何檢測兩個皇后是否在同一個對角線上？我們將棋盤的方格成一個二維數(shù)組，如下：假設(shè)有兩個皇后被放置在（i，j）和（k，l）的位置上，明顯，當(dāng)且僅當(dāng)|i-k|=|j-l|時，兩個皇后才在同一條對角線上。算法原型：上面我們搞清楚了在解決八皇后問題之前需要處理的兩個規(guī)則，并將規(guī)則轉(zhuǎn)化到了我們數(shù)學(xué)模型上的問題，那么這段我們開始著手討論如何設(shè)計(jì)八皇后的解決算法問題，最常用的就是回溯法，什么是回溯法？回溯法（英語：backtracking）是窮盡搜索算法（英語：Brute-forc

9、e search）中的一種?；厮莘ú捎迷囧e的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當(dāng)它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計(jì)算，再通過其它的可能的分步解答再次嘗試尋找問題的答案?；厮莘ㄍǔＳ米詈唵蔚倪f歸方法來實(shí)現(xiàn)，在反復(fù)重復(fù)上述的步驟后可能出現(xiàn)兩種情況： * 找到一個可能存在的正確的答案 * 在嘗試了所有可能的分步方法后宣告該問題沒有答案在最壞的情況下，回溯法會導(dǎo)致一次復(fù)雜度為指數(shù)時間的計(jì)算。明顯，回溯的思想是：假設(shè)某一行為當(dāng)前狀態(tài)，不斷檢查該行所有的位置是否能放一個皇后，檢索的狀態(tài)有兩種：（1）先從首位開始檢查，如果不能放

10、置，接著檢查該行第二個位置，依次檢查下去，直到在該行找到一個可以放置一個皇后的地方，然后保存當(dāng)前狀態(tài)，轉(zhuǎn)到下一行重復(fù)上述方法的檢索。（2）如果檢查了該行所有的位置均不能放置一個皇后，說明上一行皇后放置的位置無法讓所有的皇后找到自己合適的位置，因此就要回溯到上一行，重新檢查該皇后位置后面的位置。是否注意到？如果我們用一個數(shù)組來保存當(dāng)前的狀態(tài)，上面的檢索過程是否有點(diǎn)像堆棧的操作？如果找到可行位置，壓棧，如果當(dāng)前行所有位置不行，將出棧。好了，問題模型逐漸清晰開來了，我們可以定義一個過程，這個過程負(fù)責(zé)檢索的過程，如果檢索到當(dāng)前行某個位置可行，壓棧，如果當(dāng)前行所有位置不行，將執(zhí)行出棧操作。8皇后問題，我

11、們假定棧的大小為8，如果棧滿了，表示找到了可行方法，將執(zhí)行所有出棧操作。也許有同學(xué)會問：如果我找到了一個方法，在進(jìn)入找下一個可行方法時，該如何做到找出的方法不重復(fù)？我們是否需要為每行設(shè)定一個狀態(tài)變量？ 其實(shí)這個問題的處理方法很簡單：其實(shí)我們在回溯的時候，每個皇后所在位置就是該行的狀態(tài)變量，回溯轉(zhuǎn)到下一個位置的時候，只需后移1位即可，也就是i+。OK，其實(shí)我們可以使用一個數(shù)組來模擬棧的結(jié)構(gòu)就可以了，上面解說的時候不用數(shù)組而使用棧是因?yàn)闂５慕Y(jié)構(gòu)比數(shù)組更形象而已。根據(jù)上述想法，我們必須定義一個過程，這個過程用來檢查當(dāng)前行的某個位置是否可行，為了方便大家閱讀，我采用了常用的算法描述語言 SPARKS

12、。SPARKS 有個最大的特點(diǎn)就是非常注重算法的思想而不是代碼，這樣可以更加清晰明了地幫助讀者了解作者的算法思想。（1）過程PLACE，檢索當(dāng)前行是否可以放置一個皇后。procedurePLACE(k) /如果一個皇后能放在第K行和X(k)列，則返回true，否則返回false。X是一個全程數(shù)組，進(jìn)入此過程時已設(shè)置了k個值。ABS(r)過程返回r的絕對值/globalX(1:k);integeri,k i1whilei0 do X(k)X(k)+1 /移到下一個位置 while X(k)=n and not PLACE(k) do /此處能放這個皇后嗎？ X(k)X(k)+1 repeat i

13、f X(k)=n /找到一個位置/ then if k=n /是一個完整的解嗎？/ then print(X) /是，打印數(shù)組/ else kk+1;X(k)0 /轉(zhuǎn)向下一行/ endif else kk-1 /否則，回溯上一行/ endif repeatend NQUEENSC語言八皇后問題的實(shí)現(xiàn)：#include #include #define max 8int queenmax, sum=0; /* max為棋盤最大坐標(biāo) */void show() /* 輸出所有皇后的坐標(biāo) */ int i; printf(); for(i = 0; i max; i+) printf( %d, queeni); printf()n); sum+;int PLACE(int n) /* 檢查當(dāng)前列能否放置皇后 */ int i; for(i = 0; i n; i+) /* 檢查橫排和對角線上是否可以放置皇后 */ if(queeni = queenn | abs(queeni - queenn) = (n - i) return 1; return 0;void NQUEENS(int n) /* 回溯嘗試皇后位置,n為橫坐標(biāo) */ int i; for(i = 0; i max; i+) queen