N皇后問題.txt

1、8皇后問題和N皇后問題今天來學(xué)習(xí)一個非常著名的算法題：8皇后問題和由他推廣得到的N皇后問題。題目來源于國際象棋的玩法，因為皇后所在的位置可以縱向、橫向、兩個斜向四個方向的“捕捉”，所以8皇后問題就是要求如何布置8個皇后在88的棋盤上而使他們互相無法“捕捉”。也就是說不存在兩個皇后同行或同列，或在同一斜線上。而N皇后問題就是如何布置N個皇后在NN棋盤里使不存在兩個皇后在同行同列和同一斜線上。因為8皇后問題可以歸為N皇后問題，所以下面按照N

2、皇后問題來進(jìn)行討論。解決N皇后問題的最好最著名的算法就是回溯法。在算法設(shè)計的基本方法中，回溯法是最一般的方法之一。在那些涉及到尋找一組解的問題或者求滿足某些約束條件的最優(yōu)解的問題中，有許多可以用回溯法來求解?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)

3、點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題?；厮莘ǖ幕舅枷耄捍_定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這

4、個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。運用

5、回溯法解題通常包含以下三個步驟：（1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；一般回溯法可用遞歸來實現(xiàn)，下面是從網(wǎng)上找來的一個非常典型的遞歸程序結(jié)構(gòu)。proceduretry(i:integer)varbeginifinthen輸出結(jié)果elsefj:=下界to上界dobeginx[i]:=h[j]if可行滿足限界函數(shù)和約束條件thenbeg

6、in置值；try(i1)endendend說明：i是遞歸深度；n是深度控制，即解空間樹的的高度；可行性判斷有兩方面的內(nèi)容：不滿約束條件則剪去相應(yīng)子樹；若限界函數(shù)越界，也剪去相應(yīng)子樹；兩者均滿足則進(jìn)入下一層，直到最后的葉子輸出結(jié)果?；氐絅皇后問題的解決來，看看如何用回溯法解。首先找出解空間：給棋盤的行和列都編上1到N的號碼，皇后也給編上1到N的號碼。由于一個皇后應(yīng)在不同的行上，為不失一般性，可以假定第i個皇后將放在第i行上的某列。因此N皇

7、后問題的解空間可以用一個N元組（X1，X2，.....Xn）來表示，其中Xi是放置皇后i所在的列號。這意味著所有的解都是N元組（1，2，3，.......，N）的置換。解空間大小為N！。其次我們看約束條件：因為解空間已經(jīng)給我們排除了不在同一行（因為每個皇后分別已經(jīng)對應(yīng)不同的行號）的約束條件。我們要判斷的是不在同一列和不在同一斜線的約束。因為Xi表示皇后所在的列號，所以如果存在X（k）=X（i）那么肯定存在第k個皇后和第i個皇后同列。所以