八皇后問題的最佳解決方案

1、2算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析報(bào)告報(bào)告3算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告八皇后問題的最佳解決方案八皇后問題的最佳解決方案回溯法概述回溯法概述1八皇后問題八皇后問題2解決八皇后問題常用算法解決八皇后問題常用算法3算法分析與總結(jié)算法分析與總結(jié)4回溯法概述回溯法概述1一一 回溯法回溯法 回溯法實(shí)際是一個類似枚舉的搜索嘗試方法，它的主題思想是在搜索嘗試中找問題的解，當(dāng)不滿足求解條件就”回溯”(返回)，嘗試別的路徑?；厮菟惴ㄊ菄L試搜索算法中最為基本的一種算法,其采用了一種“走不通就掉頭”的思想，作為其控制結(jié)構(gòu)。本文主要描述遞歸回溯與非遞歸回溯，并用這兩個算法解決經(jīng)典的“八皇后”問題,找出該問

2、題的最佳解決方案。八皇后問題描述八皇后問題描述2二二 八皇后問題描述：八皇后問題描述： 八皇后問題：要在8*8的國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。如圖2-1為一種方案，求所有的解。：圖圖 2-12-1 解決八皇后問題常用算法解決八皇后問題常用算法3三三 解決八皇后問題常用的算法：解決八皇后問題常用的算法： 枚舉法解決八皇后問題枚舉法解決八皇后問題3.1 非遞歸回溯法解決八皇后問題非遞歸回溯法解決八皇后問題3.2 遞歸回溯法解決八皇后問題遞歸回溯法解決八皇后問題3.2 這是一種最簡單的算法，通過八重循環(huán)模擬搜索空間中的8

3、8個狀態(tài)，按深度優(yōu)先思想，把第1個皇后放在第1列，然后開始搜索第2到第8個皇后的合理位置，每個皇后只能在同一行的8個位置存放，每前進(jìn)一步檢查是否滿足約束條件,不滿足時，檢查下一個位置，若滿足約束條件，開始下一個皇后的合理位置檢查，直到找出8個皇后的所有合理位置（即問題的全部解）。 枚舉法解決八皇后問題枚舉法解決八皇后問題3.13.1枚舉算法解決八皇后問題：枚舉算法解決八皇后問題：概述概述：n不在同一列的表達(dá)式為：不在同一列的表達(dá)式為：xixj；n不在同一主對角線上的表達(dá)式為：不在同一主對角線上的表達(dá)式為：xi-ixj-j；n不在同一負(fù)對角線上的表達(dá)式為：不在同一負(fù)對角線上的表達(dá)式為：xi+ix

4、j+j. 枚舉法解決八皇后問題枚舉法解決八皇后問題3.1 約束條件約束條件 算法算法描述描述 枚舉法解決八皇后問題枚舉法解決八皇后問題3.1Mainain1（ ）int a9; / /初始化定義數(shù)組初始化定義數(shù)組 for (x1=1; x1=8; x1+) /從第一列開始搜索從第一列開始搜索 for (x2=1; x2=8; x2+) if （ check(x2,2)=0 ） continue; /如果約束條件滿足，則執(zhí)行下一如果約束條件滿足，則執(zhí)行下一個個for 語句，否則當(dāng)前皇后位置向右移動一位繼續(xù)檢查約束條件語句，否則當(dāng)前皇后位置向右移動一位繼續(xù)檢查約束條件 for (x3=1;x3=8

5、;x3+) if（check(x3,3)=0） continue; /同上同上 for (x4=1;x4=8; x4+) if （check(x4,4)=0） continue; /同上同上 for (x5=1; x5=8; x5+) if （check(x5,5)=0） continue; /同上同上 for (x6=1; x6=8; x6+) if （check(x6,6)=0） continue;/ 同上同上 枚舉法解決八皇后問題枚舉法解決八皇后問題3.1for(x7=1; x7=8; x7+) if （check(x7,7)=0） continue; /同上同上 for(x8=1; x

6、8=8; x8+) /同上同上 if （check(x8,8)=0） continue; /同上同上 else /找到了一組解找到了一組解 for(i=1;i=8;i+) /輸出一組滿足約束的解輸出一組滿足約束的解 print(xi);); check(int xi, int n) /該函數(shù)是用來判斷是否滿足約束該函數(shù)是用來判斷是否滿足約束 int i; for(i=1;i0 ) ak=ak+1; while (ak=n) and (check(k)=0) /搜搜索第索第k個皇后位置個皇后位置 ak=ak+1; if（ ak=n） if(k=n ) output(n); /找到一組解找到一組解

7、/ else k=k+1; /繼續(xù)為第繼續(xù)為第k+1個皇后找到位置個皇后找到位置/ ak=0; /注意下一個皇后一定要從頭開始搜索注意下一個皇后一定要從頭開始搜索/ else k=k-1; /回溯回溯 非遞歸回溯法解決八皇后問題非遞歸回溯法解決八皇后問題3.2check(int k)/檢查皇后是否滿足約束檢查皇后是否滿足約束 int i; for(i=1;i=k-1;i+)if (abs(ai-ak)=abs(i-k) or (ai=ak) return(0); return(1);output( ) /輸出滿足該約束下的一組皇后位置輸出滿足該約束下的一組皇后位置 int i; for(i=1

8、;i=n;i+) print(ai); 遞歸回溯法解決八皇后問題遞歸回溯法解決八皇后問題3.23.3遞歸回溯解決八皇后問題：遞歸回溯解決八皇后問題：概述概述：n對于回溯算法，更方便地是用遞歸控制方式實(shí)現(xiàn)，這種方式也可對于回溯算法，更方便地是用遞歸控制方式實(shí)現(xiàn)，這種方式也可以解決任意的以解決任意的n皇后問題，算法的思想同樣用深度優(yōu)先搜索，在不滿皇后問題，算法的思想同樣用深度優(yōu)先搜索，在不滿足約束條件時及時回溯。足約束條件時及時回溯。n與上面兩個算法不同，都是用與上面兩個算法不同，都是用check（）函數(shù)來檢查當(dāng)前狀態(tài)是否（）函數(shù)來檢查當(dāng)前狀態(tài)是否滿足約束條件，由于遞歸調(diào)用、回溯的整個過程是非線性

9、的，用滿足約束條件，由于遞歸調(diào)用、回溯的整個過程是非線性的，用check（）函數(shù)來檢查當(dāng)前狀態(tài)是否滿足約束條件是不充分的，而（）函數(shù)來檢查當(dāng)前狀態(tài)是否滿足約束條件是不充分的，而用用check（）函數(shù)（在算法（）函數(shù)（在算法1中說明）來檢查當(dāng)前狀態(tài)是否滿足約束中說明）來檢查當(dāng)前狀態(tài)是否滿足約束條件又有太多冗余。條件又有太多冗余。n這里，我們這里，我們 “利用數(shù)組記錄狀態(tài)信息利用數(shù)組記錄狀態(tài)信息”的技巧，用三個數(shù)組的技巧，用三個數(shù)組c,b,d分別記錄棋盤上的分別記錄棋盤上的n個列、個列、2n-1個主對角線和個主對角線和2n-1個負(fù)對角線的占用個負(fù)對角線的占用情況。情況。 算法描述算法描述 遞歸回溯

10、法解決八皇后問題遞歸回溯法解決八皇后問題3.2int a20,b20,c40,d40; int n,t,i,j,k; /t/t記錄解的個數(shù)，記錄解的個數(shù)，i控制行，控制行，j控制列控制列 main( ) int i, input(n); /輸入皇后的個數(shù)輸入皇后的個數(shù) for(i=1;i=n;i+) bi=0;/記錄棋盤記錄棋盤n個列個列 ci+1=0; cn+i=0;/記錄棋盤負(fù)對角線記錄棋盤負(fù)對角線 di=0; dn+i-1=0;/記錄棋盤主對角線記錄棋盤主對角線 try（1）; 遞歸回溯法解決八皇后問題遞歸回溯法解決八皇后問題3.2try(int i) int j; for(j=1;j=

11、n;j+) /j表示列號，第表示列號，第i個皇后有個皇后有n種可能位置種可能位置 if (bj=0) and (ci+j=0) and (di-j+n=0)/判斷位置是否沖突判斷位置是否沖突 ai=j; /第第i行第行第j列可以擺放編號為列可以擺放編號為i的皇后的皇后 bj=1; /占領(lǐng)第占領(lǐng)第j列列 ci+j=1; di-j+n=1; /占領(lǐng)兩個對角線占領(lǐng)兩個對角線 if (in) try(i+1); /n個皇后沒有擺完個皇后沒有擺完, ,遞歸擺放下一皇后遞歸擺放下一皇后 else output( ); /完成任務(wù)，打印結(jié)果完成任務(wù)，打印結(jié)果 bj=0; ci+j=0; di-j+n=0;

12、/回溯，清理現(xiàn)場，從低向上回溯回溯，清理現(xiàn)場，從低向上回溯 output( ) t=t+1;/;/這里的這里的t只是用來統(tǒng)計(jì)滿足條件的解的個數(shù)只是用來統(tǒng)計(jì)滿足條件的解的個數(shù) print(t, ); for( k=1;k=n;k+) print(ak, ); print(“ “ 換行符換行符”); 算法分析與總結(jié)算法分析與總結(jié)4 四四 算法分析與總結(jié)：算法分析與總結(jié)：三種算法比較分析三種算法比較分析：算法名字時間復(fù)雜度空間復(fù)雜度優(yōu)缺點(diǎn)枚舉法8864優(yōu)點(diǎn)：簡單，易實(shí)現(xiàn)。缺點(diǎn)：局限于皇后個數(shù)較少的情況非遞歸回溯法S(n2)O(nn)遞歸回溯法算法分析與總結(jié)算法分析與總結(jié)4 本文給出了求解八皇后的三種算法：枚舉算本文給出了求解八皇后的三種算法：枚舉算法、遞歸回溯算法和非遞歸回溯