回溯法解決n皇后問(wèn)題

1、n 皇 后 問(wèn) 題N皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題：在N*N格的格子上擺放N個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法？1、定義問(wèn)題的解空間首先以八皇后為例，可以用一棵樹(shù)表示8皇后問(wèn)題的解空間。 由于8皇后問(wèn)題的解空間為8!種排列，因此我們將要構(gòu)造的這棵樹(shù)實(shí)際上是一棵排列樹(shù)。2、確定解空間樹(shù)的結(jié)構(gòu)給棋盤(pán)上的行和列從1到8編號(hào)，同時(shí)也給皇后從1到8編號(hào)。由于每一個(gè)皇后應(yīng)放在不同的行上，不失一般性，假設(shè)皇后i放在第i行上，因此8皇后問(wèn)題可以表示成8元組(x1， x2， ， x8)， 其中xi(i=1， 2， ， 8)表示皇后

2、i所放置的列號(hào)。這種表示法的顯式約束條件是Si=1， 2， 3， 4， 5， 6， 7， 8，i=1， 2， ， 8。在這種情況下， 解空間為88個(gè)8元組組成，而隱式約束條件是沒(méi)有兩個(gè)xi相同(即所有皇后必須在不同列上)，且滿足不存在兩個(gè)皇后在同一條對(duì)角線上。加上隱式約束條件，問(wèn)題的解空間可進(jìn)一步減小。此時(shí)，解空間大小為8!，因?yàn)樗薪舛际?元組的一個(gè)置換。圖5-7表示了8皇后問(wèn)題的一個(gè)解。 圖5-7 8皇后問(wèn)題的一個(gè)解為了簡(jiǎn)單起見(jiàn)，圖5-8只給出了n=4時(shí)問(wèn)題的一種可能樹(shù)結(jié)構(gòu)。圖 5-8 4皇后問(wèn)題解空間的樹(shù)結(jié)構(gòu)在實(shí)際中，并不需要生成問(wèn)題的整個(gè)狀態(tài)空間。通過(guò)使用限界函數(shù)來(lái)刪除那些還沒(méi)有生成其

3、所有子結(jié)點(diǎn)的活結(jié)點(diǎn)。 如果用(x1， x2， ， xi)表示到當(dāng)前E結(jié)點(diǎn)的路徑，那么xi+1就是這樣的一些結(jié)點(diǎn)，它使得(x1， x2， ， xi， xi+1)沒(méi)有兩個(gè)皇后處于相互攻擊的棋盤(pán)格局。 在4皇后問(wèn)題中，惟一開(kāi)始結(jié)點(diǎn)為根結(jié)點(diǎn)1，路徑為( )。開(kāi)始結(jié)點(diǎn)既是一個(gè)活結(jié)點(diǎn)，又是一個(gè)E結(jié)點(diǎn)， 它按照深度優(yōu)先的方式生成一個(gè)新結(jié)點(diǎn)2，此時(shí)路徑為(1)，這個(gè)新結(jié)點(diǎn)2變成一個(gè)活結(jié)點(diǎn)和新的E結(jié)點(diǎn)， 原來(lái)的E結(jié)點(diǎn)1仍然是一個(gè)活結(jié)點(diǎn)。結(jié)點(diǎn)2生成結(jié)點(diǎn)3，但立即被殺死。于是，回溯到結(jié)點(diǎn)2，生成它的下一個(gè)結(jié)點(diǎn)8，且路徑變?yōu)?1， 3)。 結(jié)點(diǎn)8成為E結(jié)點(diǎn)，由于它的所有子結(jié)點(diǎn)不可能導(dǎo)致答案結(jié)點(diǎn)， 因此結(jié)點(diǎn)8也被殺死。

4、回溯到結(jié)點(diǎn)2，生成它的下一個(gè)結(jié)點(diǎn)13， 且路徑變?yōu)?1， 4)。圖5-8表示4皇后問(wèn)題回溯時(shí)的狀態(tài)空間樹(shù)。圖中一個(gè)結(jié)點(diǎn)一旦被限界函數(shù)殺死，則用B做上記號(hào)，如圖5-9所示。4皇后問(wèn)題的解結(jié)果如5-10所示. B B圖 5-9 具有限界函數(shù)的4皇后問(wèn)題的狀態(tài)空間樹(shù)24133142 圖5-10 4皇后問(wèn)題的解圖示 很容易就可將8皇后問(wèn)題推廣到n皇后問(wèn)題(n-queen problem)，即找出n×n的棋盤(pán)上放置n個(gè)皇后并使其不能互相攻擊的所有解。設(shè)X =(x1， x2， ， xn)表示問(wèn)題的解，其中xi表示第i個(gè)皇后放在第i行所在的列數(shù)。由于不存在兩個(gè)皇后位于同一列上， 因此xi互不相同。

5、設(shè)有兩個(gè)皇后分別位于棋盤(pán)(i， j)和(k， l)處， 如果兩個(gè)皇后位于同一對(duì)角線上，這表明它們所在的位置應(yīng)該滿足： i-j=k-l或i+j=k+l。這兩個(gè)等式表明，這兩個(gè)皇后位于主對(duì)角線上或次對(duì)角線上。綜合這兩個(gè)等式可得，如果兩個(gè)皇后位于同一對(duì)角線上，那么它們的位置關(guān)系一定滿足|j-l|=| i-k|。 3、搜索解空間樹(shù)解n后問(wèn)題的回溯算法可描述如下：求解過(guò)程從空配置開(kāi)始。在第1列的m列為合理配置的基礎(chǔ)上，再配置第m+1列，直至第n列也是合理時(shí)，就找到了一個(gè)解。在每列上，順次從第一行到第n行配置，當(dāng)?shù)趎行也找不到一個(gè)合理的配置時(shí)，就要回溯，去改變前一列的配置。用元組x1:n表示皇后問(wèn)題的解，

6、xi表示皇后i放在第i 行的第xi列上，用完全叉樹(shù)表示解空間。剪枝函數(shù)設(shè)計(jì)：對(duì)于兩個(gè)皇后A(i，j)、B(k，l)兩個(gè)皇后不同行：i不等于k;兩個(gè)皇后不同列：j不等于l;兩個(gè)皇后不同一條斜線|i-k|j-l|，即兩個(gè)皇后不處于同一條y=x+a或y=-x+a的直線上（1）、遞歸回溯下面的解n后問(wèn)題的回溯法中，遞歸方法queen（1）實(shí)現(xiàn)對(duì)整個(gè)解空間的回溯搜索。queen（i）搜索解空間中第i層子樹(shù)。類Queen的數(shù)據(jù)成員記錄解空間中結(jié)點(diǎn)信息，以減少傳給queen的參數(shù)。sum記錄當(dāng)前已找到的可行方案數(shù)。在算法queen中，當(dāng)i>n時(shí)，算法搜索到葉子結(jié)點(diǎn)，得到一個(gè)新的n皇后互不攻擊放置方案，

7、當(dāng)前已找到的可行方案數(shù)sum加1.當(dāng)in時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有xi=1.2，n，共n個(gè)兒子結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn)，由place檢查其可行性，并以深度優(yōu)先的方式遞歸地對(duì)可行子樹(shù)搜索，或剪去不可行子樹(shù)。算法 5.7 解N后問(wèn)題的遞歸回溯算法class Queenprivate:int n; /皇后個(gè)數(shù) int sum = 0; /可行解個(gè)數(shù) int xN; /皇后放置的列數(shù) int place(int k); int queen(int t);/*功能：判斷函數(shù)，判斷第k個(gè)皇后是否可以放在某一個(gè)位置。 輸入：第k個(gè)皇后。 輸出：如果與之前的皇后出現(xiàn)在同一列

8、或同一對(duì)角線則放置失敗，返回0，否則返1。*/int Queen :place(int k) int i; for(i=1;i<k;i+) if(abs(k-i)=abs(xk-xi) | xk = xi) return 0; return 1; /* 功能：求解可行解函數(shù)。當(dāng)?shù)趖個(gè)皇后可以放置在t行的某一位置時(shí)，繼續(xù)放置下一皇后，直到 所有皇后放置結(jié)束，如果某一皇后不能放置，則移向下一列放置，如果這一列都不能放置或所有皇后放置結(jié)束，返回上一皇后重新放置，最終返回所有可行解個(gè)數(shù)。 輸入：第t個(gè)皇后。 輸出：可行解個(gè)數(shù)。*/int Queen:queen(int t) if(t>n

9、&& n>0) /當(dāng)放置的皇后超過(guò)n時(shí)，可行解個(gè)數(shù)加1，此時(shí)n必須大于0 sum+; else for(int i=1;i<=n;i+) xt = i; /標(biāo)明第t個(gè)皇后放在第i列 if(place(t) /如果可以放在某一位置，則繼續(xù)放下一皇后 queen(t+1); return sum; （2）、迭代回溯數(shù)組x記錄了解空間樹(shù)中從根到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑，這些信息已包含了回溯法在回溯時(shí)所需要的信息。利用數(shù)組x所含信息，可將上述回溯法表示成非遞歸形式，進(jìn)一步省去O（n）遞歸?？臻g。算法 5.8 解N后問(wèn)題的非遞歸迭代回溯算法/* 功能：求解可行解函數(shù)。 輸入：無(wú)輸出：可行解個(gè)數(shù)。*/int Queen:queen() x1 = 0; int