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

2算法設(shè)計與分析報告3算法設(shè)計與分析試驗報告八皇后問題的最佳解決方案回溯法概述1

內(nèi)容提要八皇后問題2解決八皇后問題常用算法3算法分析與總結(jié)4回溯法概述1一回溯法回溯法實際是一個類似枚舉的搜尋嘗試方法，它的主題思想是在搜尋嘗試中找問題的解，當(dāng)不滿足求解條件就”回溯”(返回)，嘗試別的路徑。回溯算法是嘗試搜尋算法中最為基本的一種算法,其接受了一種“走不通就掉頭”的思想，作為其限制結(jié)構(gòu)。本文主要描述遞歸回溯與非遞歸回溯，并用這兩個算法解決經(jīng)典的“八皇后”問題,找出該問題的最佳解決方案。八皇后問題描述2二八皇后問題描述：八皇后問題：要在8*8的國際象棋棋盤中放八個皇后，使隨意兩個皇后都不能相互吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的隨意棋子。如圖2-1為一種方案，求全部的解。：圖2-1解決八皇后問題常用算法3三

解決八皇后問題常用的算法：

枚舉法解決八皇后問題3.1非遞歸回溯法解決八皇后問題3.2遞歸回溯法解決八皇后問題3.2這是一種最簡潔的算法，通過八重循環(huán)模擬搜尋空間中的88個狀態(tài)，按深度優(yōu)先思想，把第1個皇后放在第1列，然后起先搜尋第2到第8個皇后的合理位置，每個皇后只能在同一行的8個位置存放，每前進一步檢查是否滿足約束條件,不滿足時，檢查下一個位置，若滿足約束條件，起先下一個皇后的合理位置檢查，直到找出8個皇后的全部合理位置（即問題的全部解）。枚舉法解決八皇后問題3.13.1枚舉算法解決八皇后問題：概述：不在同一列的表達式為：xi≠xj；不在同一主對角線上的表達式為：xi-ixj-j；不在同一負(fù)對角線上的表達式為：xi+i≠xj+j.

枚舉法解決八皇后問題3.1②約束條件算法描述

枚舉法解決八皇后問題3.1Main1（）{inta[9];//初始化定義數(shù)組for(x1=1;x1<=8;x1++)//從第一列起先搜尋for(x2=1;x2<=8;x2++){if（check(x2,2)=0）continue;//假如約束條件滿足，則執(zhí)行下一個for語句，否則當(dāng)前皇后位置向右移動一位接著檢查約束條件for(x3=1;x3<=8;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;x8<=8;x8++)//同上{if（check(x8,8)=0）continue;//同上else//找到了一組解for(i=1;i<=8;i++)//輸出一組滿足約束的解print(xi);}}}}}}}}check(intxi,intn)//該函數(shù)是用來推斷是否滿足約束{inti;for(i=1;i<=n-1;i++)//這里只須要推斷前n-1個if(abs(xi-xn)=abs(i-n))or(xi=xn)//推斷是否同一列或者同一對角線return(0);return(1);}非遞歸回溯法解決八皇后問題3.23.2非遞歸回溯解決八皇后問題：算法1的枚舉算法可讀性很好，但它只能解決八皇后問題，而不能解決隨意的n皇后問題。因此不是通用的回溯算法。下面的非遞歸算法可以說是通用的n皇后問題算法模型。概述：②算法描述非遞歸回溯法解決八皇后問題3.2ta[20],n;Main2(){input(n);bckdate（n）;}//初始化，輸入皇后數(shù)目backdate(intn)//該函數(shù)是用來找尋滿足約束的全部解{intk;a[1]=0;k=1;//k用來表示第k個皇后while(k>0){a[k]=a[k]+1;while((a[k]<=n)and(check(k)=0))//搜尋第k個皇后位置a[k]=a[k]+1;if（a[k]<=n）if(k=n)output(n);//找到一組解/else{k=k+1;//接著為第k+1個皇后找到位置/a[k]=0;}//留意下一個皇后確定要從頭起先搜尋/elsek=k-1;//回溯}}非遞歸回溯法解決八皇后問題3.2check(intk)//檢查皇后是否滿足約束{inti;for(i=1;i<=k-1;i++)if(abs(a[i]-a[k])=abs(i-k))or(a[i]=a[k])return(0);return(1);}output()//輸出滿足該約束下的一組皇后位置{inti;for(i=1;i<=n;i++)print(a[i]);}遞歸回溯法解決八皇后問題3.23.3遞歸回溯解決八皇后問題：概述：對于回溯算法，更便利地是用遞歸限制方式實現(xiàn)，這種方式也可以解決隨意的n皇后問題，算法的思想同樣用深度優(yōu)先搜尋，在不滿足約束條件時剛好回溯。與上面兩個算法不同，都是用check（）函數(shù)來檢查當(dāng)前狀態(tài)是否滿足約束條件，由于遞歸調(diào)用、回溯的整個過程是非線性的，用check（）函數(shù)來檢查當(dāng)前狀態(tài)是否滿足約束條件是不充分的，而用check（）函數(shù)（在算法1中說明）來檢查當(dāng)前狀態(tài)是否滿足約束條件又有太多冗余。這里，我們“利用數(shù)組記錄狀態(tài)信息”的技巧，用三個數(shù)組c,b,d分別記錄棋盤上的n個列、2n-1個主對角線和2n-1個負(fù)對角線的占用狀況。②算法描述遞歸回溯法解決八皇后問題3.2inta[20],b[20],c[40],d[40];intn,t,i,j,k;//t記錄解的個數(shù)，i限制行，j限制列main(){inti,input(n);//輸入皇后的個數(shù)for(i=1;i<=n;i++){b[i]=0;//記錄棋盤n個列c[i+1]=0;c[n+i]=0;//記錄棋盤負(fù)對角線d[i]=0;d[n+i-1]=0;//記錄棋盤主對角線}try（1）;}遞歸回溯法解決八皇后問題3.2try(inti){intj;for(j=1;j<=n;j++)//j表示列號，第i個皇后有n種可能位置if(b[j]=0)and(c[i+j]=0)and(d[i-j+n]=0)//推斷位置是否沖突{a[i]=j;//第i行第j列可以擺放編號為i的皇后b[j]=1;//占據(jù)第j列c[i+j]=1;d[i-j+n]=1;//占據(jù)兩個對角線if(i<n)try(i+1);//n個皇后沒有擺完,遞歸擺放下一皇后elseoutput();//完成任務(wù)，打印結(jié)果b[j]=0;c[i+j]=0;d[i-j+n]=0;//回溯，清理現(xiàn)場，從低向上回溯}}output(){t=t+1;//這里的t只是用來統(tǒng)計滿足條件的解的個數(shù)print(t,'');for(k=1;k<=n;k++)print(a[k],'