算法實(shí)驗(yàn) 遞歸回溯解八皇后問(wèn)題

1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 算法分析與復(fù)雜性理論 實(shí)驗(yàn)項(xiàng)目名稱： 八皇后問(wèn)題 學(xué)院： 計(jì)算機(jī)與軟件學(xué)院 專業(yè)： 軟件工程 指導(dǎo)教師： 楊烜 報(bào)告人： 學(xué)號(hào)： 班級(jí)： 15級(jí)軟工學(xué)術(shù)型 實(shí)驗(yàn)時(shí)間： 2015-12-08 實(shí)驗(yàn)報(bào)告提交時(shí)間： 2015-12-09 教務(wù)部制一實(shí)驗(yàn)?zāi)康?. 掌握選回溯法設(shè)計(jì)思想。2. 掌握八皇后問(wèn)題的回溯法解法。二實(shí)驗(yàn)步驟與結(jié)果實(shí)驗(yàn)總體思路：根據(jù)實(shí)驗(yàn)要求，通過(guò)switch選擇八皇后求解模塊以及測(cè)試數(shù)據(jù)模塊操作，其中八皇后模塊調(diào)用擺放皇后函數(shù)模塊，擺放皇后模塊中調(diào)用判斷模塊。測(cè)試數(shù)據(jù)模塊主要調(diào)用判斷模塊進(jìn)行判斷，完成測(cè)試。用一維數(shù)組保存每行擺放皇后的位置

2、，根據(jù)回溯法的思想遞歸討論該行的列位置上能否放置皇后，由判斷函數(shù)judge()判斷，若不能放置則檢查該行下一個(gè)位置。相應(yīng)結(jié)果和過(guò)程如下所示（代碼和結(jié)果如下圖所示）。回溯法的實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果：1、 判斷函數(shù)代碼1：procedure btrack_queen(n)/如果一個(gè)皇后能放在第k行和x(k)列，則返回true，否則返回false。globalx(1:k);integeri,ki1whilei0 dox(k)x(k)+1 /移到下一個(gè)位置while x(k)=n and not judge(k) do /判斷能否放置皇后x(k)x(k)+1repeatif x(k)=n /找到一個(gè)位置the

3、n if k=n /是一個(gè)完整的解嗎t(yī)hen print(x) /是，打印數(shù)組else kk+1;x(k)0 /轉(zhuǎn)向下一行endifelse kk-1 /否則，回溯上一行endifrepeatend btrack_queen實(shí)驗(yàn)結(jié)果：(圖1 回溯法解八皇后問(wèn)題)(圖2 回溯法解八皇后問(wèn)題)(圖3 測(cè)試數(shù)據(jù)結(jié)果)注：根據(jù)實(shí)驗(yàn)數(shù)組中保存的列坐標(biāo)，對(duì)應(yīng)行坐標(biāo)順序輸入即可。實(shí)驗(yàn)中多加入了一組不滿足八皇后問(wèn)題的解。mfc可視化下八皇后的實(shí)現(xiàn)與結(jié)果：代碼3：/判斷是否符合八皇后問(wèn)題的解int cbfhoudlg:check(int row, int col) /看同行是否合法; for(int i=0;i

4、=col-1;i+) if(arowi=1)return 0; for(i=col+1;i8;i+) if(arowi=1)return 0; /看同列是否合法; for(i=0;i=row-1;i+) if(aicol=1)return 0; for(i=row+1;i=0&j= n-1) if(aij=1)return 0; -i;+j; i=row+1; j=col-1; while(i=0) if(aij=1)return 0; +i;-j; i=row-1;j=col-1; while(i=0&j=0) if(aij=1)return 0; -i;-j; i=row+1;j=col+

5、1; while(i=n-1)&j=n-1) if(aij=1)return 0; +i;+j; return 1; 實(shí)驗(yàn)結(jié)果：（圖4 八皇后的第1種解）(圖5 八皇后的第92種解)注：由于時(shí)間有限，這個(gè)月考試較多，程序還要很多地方需要完善。三實(shí)驗(yàn)分析與結(jié)論根據(jù)八皇后問(wèn)題的規(guī)則皇后不能放置在同行、同列及同一對(duì)角線上，進(jìn)而將問(wèn)題轉(zhuǎn)化為將第i個(gè)皇后放在第i行第xi列上(1i,xin)，皇后間彼此不能同列及不同對(duì)角線表示為xi != xj，|ixi| != |jxj|。八皇后問(wèn)題的解法主要有枚舉法、非遞歸回溯法、遞歸回溯法這三種，枚舉法是將所以的可能組合都進(jìn)行判斷，時(shí)間復(fù)雜度為o(nn),適用于個(gè)數(shù)

6、n比較少的情況。而非遞歸回溯法采用深度優(yōu)先搜索策略判斷當(dāng)前位置是否符合該問(wèn)題的解，時(shí)間復(fù)雜度為o(n2)，在實(shí)現(xiàn)大規(guī)模的n皇后問(wèn)題上性能更好。遞歸回溯法同樣采用深度優(yōu)先搜索策略，但在搜索到不滿足約束條件時(shí)能及時(shí)回溯，整體上提高了解題的效率。時(shí)間復(fù)雜度較非回溯法更低。四實(shí)驗(yàn)心得八皇后問(wèn)題以前也看過(guò)，只是以前沒(méi)有將測(cè)試數(shù)據(jù)模塊和解八皇后問(wèn)題模塊整合到主函數(shù)中，后面也想到用mfc實(shí)現(xiàn)可視化求解，但是之前都沒(méi)學(xué)過(guò)mfc編程，根據(jù)網(wǎng)上的資料還是完成了較為基本的程序。這次實(shí)驗(yàn)確實(shí)學(xué)到很多東西，不光是提高了編程能力、代碼閱讀能力，更掌握了回溯法的遞歸求解思路。 附錄：代碼#include#include#i

7、nclude#define max 8using namespace std; int queenmax, sum=0; / max為棋盤(pán)最大坐標(biāo) /*輸出所有皇后的坐標(biāo) */void show_queen() cout( ; for(int i = 0; i max; i+) coutqueeni+1 ; cout)endl; sum+; /*判斷是否滿足八皇后問(wèn)題函數(shù)*/int judge(int n) for(int i = 0; i n; i+) / 檢查橫排和對(duì)角線上是否可以放置皇后 if(queeni = queenn | abs(queeni - queenn) = (n - i

8、) return 1; return 0;/*回溯嘗試皇后位置,n為橫坐標(biāo)*/void backtrack_queen(int n) for(int i = 0; i max; i+) queenn = i; /* 將皇后擺到當(dāng)前循環(huán)到的位置 */ if(!judge(n) if(n = max-1 ) show_queen(); /* 如果全部擺好，則輸出所有皇后的坐標(biāo) */ else backtrack_queen(n + 1); /* 否則繼續(xù)擺放下一個(gè)皇后 */ int main()while(1) int n;cout*endl;cout* 選擇相應(yīng)序號(hào)進(jìn)行操作： *endl;cout* 1.八皇后問(wèn)題 2.測(cè)試數(shù)據(jù) 0.退出 *endl;cout*n;switch(n)case 0: cout退出程序成功.endl;return 0; /一個(gè)程序兩個(gè)出口 case 1: cout八皇后問(wèn)題的解為：endl;backtrack_queen(0);cout共有sum個(gè)解endl;break;case 2: cout運(yùn)行測(cè)試數(shù)據(jù)：endl;while(1) cout請(qǐng)輸入要測(cè)試的數(shù)據(jù)：endl;for(int j=0;jqueenj; if(judge(max)=1) cout該數(shù)據(jù)是八皇后問(wèn)題的解en