n皇后問(wèn)題實(shí)驗(yàn)報(bào)告

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

2、d for4. flag=false5. k=16. while k=17. while ck=58. ck=ck+19. if c為合法著色 then set flag=ture 且從兩個(gè)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 #include iostream u

3、sing 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個(gè)皇后是否互相攻擊 while(ki&abs(queenk-queeni)&(abs(queenk-queeni)-abs(k-i) k+; if (k=i-1) /與第k個(gè)皇后互相攻擊 queeni+; /第i個(gè)皇后右移一列，重測(cè) continue; i+; /無(wú)沖突，安置下一行皇后 if(iN)

4、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個(gè)皇后右移一列，前8個(gè)不動(dòng) i=N-1; /此處是制造機(jī)會(huì)，如不成功則回溯，關(guān)鍵一步 else /當(dāng)前行皇后無(wú)法安置，回溯 queeni=0; /當(dāng)前行皇后回歸1列 i-; /回溯到前一行皇后 if(i0) /回溯到數(shù)組1行之前，結(jié)束 co

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

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

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

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

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

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

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

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

13、at if X(k)=n /找到一個(gè)位置/ then if k=n /是一個(gè)完整的解嗎？/ then print(X) /是，打印數(shù)組/ else kk+1;X(k)0 /轉(zhuǎn)向下一行/ endif else kk-1 /否則，回溯上一行/ endif repeatend NQUEENSC語(yǔ)言八皇后問(wèn)題的實(shí)現(xiàn)：#include #include #define max 8int queenmax, sum=0; /* max為棋盤(pán)最大坐標(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+) /* 檢查橫排和對(duì)角線上是否可以放置皇后 */ 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