回溯法解決n皇后問題

1、回溯法解決n皇后問題回溯法解決n皇后問題摘要：回溯法是一種選優(yōu)搜索法，也稱為試探法，按照深度優(yōu)先搜索的策略，從根結點出發(fā)深度探索解空間樹?；厮菟惴ń鉀Q問題的一般步驟。八皇后問題以及8-皇后問題的推廣n-皇后問題，等于要求N個皇后中的任意兩個不能被放在同一行或同一列或同一斜線上。關鍵詞：回溯法、八皇后、顯約束、顯約束、樹結構一回溯法回溯法是一種選優(yōu)搜索法，也稱為試探法，它并不考慮問題規(guī)模的大小，而是從問題的最明顯的最小規(guī)模開始逐步求解出可能的答案，并以此慢慢地擴大問題規(guī)模，迭代地逼近最終問題的解。這種迭代類似于窮舉并且是試探性的，因為當目前的可能答案被測試出不可能可以獲得最終解時，則撤銷當前的這

2、一步求解過程，回溯到上一步尋找其他求解路徑。通過對問題的歸納分析，找出求解問題的一個線索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換其他路線再往前試探。因此，回溯法可以形象地概括為“向前走，碰壁回頭”。有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往使用回溯法。二回溯的一般方法 下面簡要闡述回溯的一般方法。 回溯求解的問題P，通常要能表達為：對于已知的由n元組(x1,x2,xn)組成的一個狀態(tài)空間E=(x1,x2,xn)|xisi,i=1,2,n，給定關于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約

3、束條件的所有n元組。其中si是分量xi的定義域，且|si|有限，i=1,2,n。稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。解問題P的最樸素的方法就是窮舉法，上面已經(jīng)作了介紹，即對E中的所有n元組逐一地檢驗其是否滿足D的全部約束，若滿足，則為問題P的一個解。顯然，其計算量是相當大的。 對于許多問題，所給定的約束集D具有完備性，即i元組(x1,x2,xi)滿足D中僅涉及到x1,x2,xi的所有約束，意味著j(j<i)元組(x1,x2,xj)一定也滿足D中僅涉及到x1,x2,xj的所有約束，i=1,2,n。換句話說，只要存在0jn-1，使得(x1,x2,xj)違反D中僅

4、涉及到x1,x2,xj的約束之一，則以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)也一定違反D中僅涉及到x1,x2,xj的一個約束，nij。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組(x1,x2,xj)違反D中僅涉及x1,x2,xj的一個約束，就可以肯定，以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)都不會是問題P的解，因而就不必去搜索它們，即省略了對部分元素(xj+1,xn)的操作與測試?；厮莘ㄕ轻槍@類問題。三基本思想在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結點出發(fā)深度探索解空間樹。當探索到

5、某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發(fā)繼續(xù)探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。回溯算法解決問題的一般步驟：1、定義一個解空間，它包含問題的解。2、利用適于搜索的方法組織解空間。3、利用深度優(yōu)先法搜索解空間。4、利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。問題的解空間通常是在搜索問題的解的過程中動態(tài)產(chǎn)生的，這是回溯算法的一個重要特性。問題的解向量： 回溯法希望一個問題的解能夠表示成一個n元式(

6、x1,x2,xn)的形式。顯約束： 對分量xi的取值限定。隱約束： 為滿足問題的解而對不同分量之間施加的約束。解空間： 對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結

7、點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止?；厮莘ㄓ小巴ㄓ媒忸}法”之稱，是一種比窮舉“聰明”的搜索技術，在搜索過程中動態(tài)地產(chǎn)生問題的解空間，系統(tǒng)地搜索問題的所有解。當搜索到解空間樹的任一結點時，判斷該結點是否包含問題的解。如果該結點肯定不包含，則“見壁回頭”，跳過以該結點為根的子樹的搜索，逐層向其祖先結點回溯，可大大縮減無效操作，提高搜索效率。因此，結合具體案例的實際設計合適的回溯點是應用回溯法的關鍵所在。 值得注意的是，遞歸具有回溯的功能，很多問題應用遞歸回溯可探索出問題的所有解。例如，在求解橋本分數(shù)式中，既用了回溯法求解，也應用

8、了遞歸求解，請認真比較這二者之間的關聯(lián)。盡管遞歸的效率不高，但遞歸設計的簡明是一般回溯設計所不及的。 回溯法的時間復雜度因案例的具體實際而異。一般來說，其搜索效率要高于窮舉。四八皇后問題八皇后問題是一個古老而著名的問題。該問題是十九世紀著名的數(shù)學家高斯1850提出；在8×8格的國際象棋上擺放八皇后，使得每一個皇后既攻擊不到另外七個皇后，也不被另外七個皇后所攻擊按照國際象棋的規(guī)則，一個皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子因此，八皇后問題等于要求八個皇后中的任意兩個不能被放在同一行或同一列或同一斜線上。可以從矩陣的特點上找到規(guī)律，如果在同一行，則行號相同

9、；如果在同一列上，則列號相同；如果同在“/”斜線上的行列值之和相同；如果在對角線上，則行列號之和或之差相等，逐個紀錄符合題意的情況,最終得出解。分析：由于8*8的棋盤太大，所以用4*4來演示，右圖是一組解坐標表示：（1，3）（2，1）（3，4）（4，2）當n=4時的一種可能的樹結構。像這樣的一棵樹稱之為排列樹。樹的邊由xi的可能值所標記。由1級到2級結點的邊給出x1的值。因此，最左子樹包含著x1=1的所有解，而該子樹的最左子樹又包含著x1=1且x2=2的所有解，等等。由i級到i1級的邊用xi的值標記。解空間則是由從根結點到葉結點的所有路徑所定義的。在下圖的這棵樹中，有4!=24個葉結點。圖2

10、4-皇后問題解空間的樹結構，結點按深度優(yōu)先檢索編號考慮用回溯法來處理n-皇后問題?？捎靡恍╋@而易見的標準來作為限界函數(shù)，即如果(x1,x2,xi)是到當前E-結點的路徑，那么具有父-子標記xi+1的所有孩子結點是一些這樣的結點，它們使得(x1,x2,xi+1)表示沒有兩個皇后正在互相攻擊的一種棋盤格局。開始時，把根結點作為唯一的活結點，該根結點就成為E-結點且路徑為()。接著生成一個孩子結點，如果假定按自然數(shù)遞增的次序來生成孩子結點，那么，如圖所示的結點2被生成，其路徑為(1)。這相當于把皇后1放在第1列上。結點2變成E-結點，生成結點3，但立即被殺死。下一個生成的結點是8且路徑變成(l,3)

11、。結點 8成為 E-結點，由于它的所有孩子表示的是一些不可能導致答案結點的棋盤格局，因此結點8也被殺死。于是回溯到結點2并生成它的另一個孩子結點13?，F(xiàn)在的路徑是(l,4)。思路： 有序地從第 1 行的第 1 列開始，嘗試放上一個皇后，然后再嘗試第 2 行的第幾列能夠放上一個皇后，如果第 2 行也放置成功，那么就繼續(xù)放置第 3 行，如果此時第 3 行沒有一行可以放置一個皇后，說明目前為止的嘗試是無效的（即不可能得到最終解），那么此時就應該回溯到上一步（即第 2 步），將上一步（第 2 步）所放置的皇后的位置再重新取走放在另一個符合要求的地方如此嘗試性地遍歷加上回溯，就可以慢慢地逼近最

12、終解了。下圖所示為應用回溯的實施過程，其中方格中的*表示試圖在該方格放置一個皇后,但由于受前面已放置的皇后的攻擊而放棄的位置。圖 3 四皇后問題的一個回溯解的例子1(a)1(b)*21(c)2*1(d)2*31(e)23*1(f)1(g)*21(h)23*4圖3生動地顯示了應用回溯算法求一個解所經(jīng)過的步驟。圖中的點表示曾試圖放置一個皇后但由于受到另-皇后的攻擊而放棄了的位置。在(a)中，第一個皇后被放在第1列上。在(b)中，第二個皇后被放在第1，第2列而最后放置在第3列上。在(c)中，算法把四列都試驗了，但沒法將下一個皇后放在一個方格中，此時就進行回溯。在(d)中，第二個皇后被移到下一個可能的

13、列，即第4列，然后將第三個皇后放在第2列上。(e)、(f)、(g)和(h)則顯示了用這個算法一直找到一個解為止所進行的其余步驟。用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；顯然，每一行可以而且必須放一個皇后，所以n皇后問題的解可以用一個n元向量X=（x1,x2,.xn）表示，其中，1 i n且1 xi n，即第n個皇后放在第i行第xi列上。由于兩個皇后不能放在同一列上，所以，解向量X必須滿足的約束條件為:xi xj;若兩個皇后的擺放位置分別是（i,xi）和（j,xj），在棋盤上斜率為-1的斜線上，滿足條件：i-j=xi-xj;在棋盤上斜率為1的斜線上，滿足條件：i+j=xi+xj;綜合兩種情況

14、，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足的約束條件為:|i-xi| |j-xj|用限界函數(shù)剪去得不到最優(yōu)解的子樹。i < n + 1j < n + 1五數(shù)據(jù)結構Int column col = row 表示第 col 列的第 row 行放置一個皇后；Boolean rowExistsi = true 表示第 i 行有皇后；Boolean ai = true 表示右高左低的第 i 條斜線有皇后（按   順序從1 2*N -1 依次編號）；Boolean bi = true

15、0;表示左高右低的第 i 條斜線有皇后（按   順序從1 2*N -1 依次編號）。六程序調(diào)試當n=4時：當n=6時：七總結從八皇后問題設計以及分析中，本人從中理解到了數(shù)據(jù)結構對于計算機軟件設計的重要性，它的使用，可以改變一個軟件的運行周期，也可以將軟件的思路從繁化簡，并且都能夠通過數(shù)據(jù)結構的相關引導，將本身以前編程思想進行擴充，發(fā)展；這也是在這次課程設計中我所掌握得到的。 參考文獻 1  蘇仕華,數(shù)據(jù)結構課程設計.-北京:機械工業(yè)出版社,2005.5 2  于永彥,趙建洋.課程設計指導書.淮安

16、：江蘇淮陰工學院 計算機工程系,2006 3 王峰.Java多媒體程序設計.清華大學出版社.19994 耿祥義.Java課程設計.清華大學出版社.2003代碼：public class nhuanghou private int queensNum=4 ; / queensNum代表皇后個數(shù)private int number = 1; / rowExistsi = true 表示第 i 行有皇后 private boolean rowExists = new booleanqueensNum + 1; / columni = j 表示第 i 列的第 j 行放置一個皇后 p

17、rivate int queens = new intqueensNum + 1; / ai = true 表示右高左低的第 i 條斜線有皇后 private boolean a = new booleanqueensNum * 2; / bi = true 表示左高右低的第 i 條斜線有皇后 private boolean b = new booleanqueensNum * 2; / 初始化變量 private void init() for (int i = 0; i < queensNum + 1; i+) rowExistsi = false; for(int i = 0; i

18、 < queensNum * 2; i+) ai = bi = false; / 判斷該位置是否已經(jīng)存在一個皇后,存在則返回 true private boolean isExists(int row, int col) return (rowExistsrow | arow + col - 1 | bqueensNum + col - row); / 主方法：測試放置皇后 public void testing(int column) / 遍歷每一行 for (int row = 1; row < queensNum + 1; row+) / 如果第 row 行第 column 列可以放置皇后 if (!isExists(row, column) / 設置第 row 行第 column 列有皇后 queenscolumn = row; /