算法實驗 遞歸回溯解八皇后問題

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

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

3、n if k=n /是一個完整的解嗎t(yī)hen print(x) /是，打印數(shù)組else kk+1;x(k)0 /轉向下一行endifelse kk-1 /否則，回溯上一行endifrepeatend btrack_queen實驗結果：(圖1 回溯法解八皇后問題)(圖2 回溯法解八皇后問題)(圖3 測試數(shù)據(jù)結果)注：根據(jù)實驗數(shù)組中保存的列坐標，對應行坐標順序輸入即可。實驗中多加入了一組不滿足八皇后問題的解。mfc可視化下八皇后的實現(xiàn)與結果：代碼3：/判斷是否符合八皇后問題的解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; 實驗結果：（圖4 八皇后的第1種解）(圖5 八皇后的第92種解)注：由于時間有限，這個月考試較多，程序還要很多地方需要完善。三實驗分析與結論根據(jù)八皇后問題的規(guī)則皇后不能放置在同行、同列及同一對角線上，進而將問題轉化為將第i個皇后放在第i行第xi列上(1i,xin)，皇后間彼此不能同列及不同對角線表示為xi != xj，|ixi| != |jxj|。八皇后問題的解法主要有枚舉法、非遞歸回溯法、遞歸回溯法這三種，枚舉法是將所以的可能組合都進行判斷，時間復雜度為o(nn),適用于個數(shù)

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

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

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