回溯法解決n皇后問題

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

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

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

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

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

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

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

8、或同一對角線則放置失敗，返回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ù)趖個皇后可以放置在t行的某一位置時，繼續(xù)放置下一皇后，直到 所有皇后放置結(jié)束，如果某一皇后不能放置，則移向下一列放置，如果這一列都不能放置或所有皇后放置結(jié)束，返回上一皇后重新放置，最終返回所有可行解個數(shù)。 輸入：第t個皇后。 輸出：可行解個數(shù)。*/int Queen:queen(int t) if(t>n

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