皇后問(wèn)題算法設(shè)計(jì)

1、算法設(shè)計(jì)及分析 n皇后問(wèn)題-回溯求解國(guó)際象棋中皇后威力很大，它可以象“車”一樣沿直線上下或左右移動(dòng)；也可以如同“象”那樣沿著斜線移動(dòng)。雙方的皇后是不能在同一行或同一列或同一斜線上對(duì)持的。那么，在一張空白的國(guó)際象棋盤上最多可以放上幾個(gè)皇后并且不讓它們互相攻擊呢？這個(gè)問(wèn)題是偉大數(shù)學(xué)家高斯在十九世紀(jì)中期提出來(lái)的，并作了部分解答。高斯在棋盤上放下了N個(gè)互不攻擊的皇后，他還認(rèn)為可能有N種不同的放法，這就是有名的“N皇后”問(wèn)題。如果你動(dòng)手試試，就一定會(huì)發(fā)現(xiàn)開頭幾顆皇后很容易放置，越到后來(lái)就越困難。由于我們的記憶有限，很可能在某個(gè)位置放過(guò)子后來(lái)證明不行取消了，但是以后又重新放上子去試探，這樣就會(huì)不斷地走彎路

2、，花費(fèi)大量的精力。因此，必須找到一個(gè)簡(jiǎn)易有效、有條不紊的法則才行。回溯法的基本思想：對(duì)于用回溯法求解的問(wèn)題，首先要將問(wèn)題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過(guò)深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出結(jié)果。在深度優(yōu)先搜索的過(guò)程中，不斷的將每個(gè)解（并不一定是完整的，事實(shí)上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進(jìn)行對(duì)照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時(shí)間。不妨以8皇后為例，設(shè)8皇后為xi，她們分別在第i行（i=1,2,3,4,5,6,7,8）,這樣問(wèn)題的解空間就是一個(gè)8個(gè)皇后所在列的序號(hào)，為n元一維向量（x1

3、,x2,x3,x4,x5,x6,x7,x8），搜索空間是1xi8（i=1,2,3,4,5,6,7,8）,共88個(gè)狀態(tài)。約束條件是8個(gè)點(diǎn)（1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一對(duì)角線上。雖然問(wèn)題共有88個(gè)狀態(tài)，但算法不會(huì)真正地搜索這么多的狀態(tài)，因?yàn)榛厮莘ú捎玫氖恰白卟煌ň偷纛^”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的狀態(tài)共有86個(gè)，由于1,2號(hào)皇后在同一列不滿足約束條件，回溯后這些狀態(tài)是不會(huì)搜索的。算法設(shè)計(jì)：我們用三個(gè)數(shù)組c,b,d分別記錄棋盤上的n個(gè)列，2n-1個(gè)住對(duì)角線和2n-1個(gè)副對(duì)

4、角線的占用情況。用i,j分別表示皇后所在的行列，用表達(dá)式i-j+n對(duì)主對(duì)角線編號(hào)，范圍是12n-1，用i+j為負(fù)對(duì)角線編號(hào)，范圍為22n. 程序代碼：#include"stdio.h"int a20,b20,c40,d40,n,i,k;int t=0; /t記錄解的個(gè)數(shù)void output()t=t+1;printf("第%d個(gè)解:",t);for(k=1;k<=n;k+)printf("%d",ak);printf("n");void find(int i)int j;for(j=1;j<=n;j+

5、) /第i個(gè)皇后有n種可能位置if(bj=0&&ci+j=0&&di-j+n=0) /判斷位置是否沖突ai=j; /擺放皇后bj=1; /占領(lǐng)第j列ci+j=1;/占領(lǐng)兩個(gè)對(duì)角線di-j+n=1;if(i<n)find(i+1); /n個(gè)皇后沒(méi)有擺完，遞歸擺放下一皇后elseoutput(); /完成任務(wù)，打印結(jié)果bj=0; /回溯ci+j=0;di-j+n=0;void main()printf("皇后問(wèn)題n=");scanf("%d",&n);for(i=1;i<=n;i+)bi=0;ci=0;di

6、=0;ci+n=0;di+n=0;find(1);n=4時(shí)的運(yùn)行結(jié)果：解的放置方式如圖：n=6時(shí)的運(yùn)行結(jié)果：解的放置方式如圖：算法分析：數(shù)組b,c,d分別用來(lái)標(biāo)記沖突。數(shù)組b代表列沖突，如果某列上已經(jīng)有皇后，則為1，否則為0；數(shù)組c代表主對(duì)角線沖突，如果某條主對(duì)角線上已經(jīng)有皇后，則為1，否則為0；數(shù)組d代表從對(duì)角線沖突，如果某條從對(duì)角線上已經(jīng)有皇后，則為1，否則為0。回溯法是一種滿足某約束條件的窮舉式搜索技術(shù)，適應(yīng)于解決一些組合數(shù)相當(dāng)大的問(wèn)題。其優(yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過(guò)對(duì)問(wèn)題的分析可以大大提高運(yùn)行效率。其程序編寫相對(duì)復(fù)雜，且消耗很多的資源，但其實(shí)際情況較簡(jiǎn)單。遞歸是一種很古老的算法，其應(yīng)用的也十分的廣泛，在很多復(fù)雜的程序中也是經(jīng)常性的使用，遞歸的優(yōu)點(diǎn)是編寫簡(jiǎn)單，缺點(diǎn)是消耗資源大。本程序采用回溯算法和遞歸，把八皇后問(wèn)題的調(diào)用函數(shù)融合