【題1】n皇后問題

《【題1】n皇后問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、【題1】n皇后問題一個(gè)ｎ×ｎ（1≤n≤100）的國際象棋棋盤上放置ｎ個(gè)皇后，使其不能相互攻擊，即任何兩個(gè)皇后都不能處在棋盤的同一行、同一列、同一條斜線上，試問共有多少種擺法？輸入：n輸出：所有分案。每個(gè)分案為n+1行，格式：方案序號以下n行。其中第i行（1≤i≤n）行為棋盤i行中皇后的列位置。在分析算法思路之前，先讓我們介紹幾個(gè)常用的概念：1、狀態(tài)（state）狀態(tài)是指問題求解過程中每一步的狀況。在ｎ皇后問題中，皇后所在的行位置i(1≤i≤n)即為其時(shí)皇后問題的狀態(tài)。顯然，對問題狀態(tài)的描述，應(yīng)與待解決問題的自然特性相似，而且應(yīng)盡量做到占用空間少，又易于用算符對狀態(tài)進(jìn)

2、行運(yùn)算。2、算符（operater）算符是把問題從一種狀態(tài)變換到另一種狀態(tài)的方法代號。算符通常采用合適的數(shù)據(jù)來表示，設(shè)為局部變量。n皇后的一種擺法對應(yīng)1．．ｎ排列方案（a1，…，an）。排列中的每個(gè)元素ai對應(yīng)ｉ行上皇后的列位置（1≤i≤n）。由此想到，在ｎ皇后問題中，采用當(dāng)前行的列位置i(1≤i≤n)作為算符是再合適不過了。由于每行僅放一個(gè)皇后，因此行攻擊的問題自然不存在了，但在試放當(dāng)前行的一個(gè)皇后時(shí)，不是所有列位置都適用。例如(l，ｉ)位置放一個(gè)皇后，若與前1．．l-1行中的j行皇后產(chǎn)生對角線攻擊(｜ｊ－l｜=｜aj－i｜)或者列攻擊(ｉ≠aj)，那么算符ｉ顯然

3、是不適用的，應(yīng)當(dāng)舍去。因此，不產(chǎn)生對角線攻擊和列攻擊是ｎ皇后問題的約束條件，即排列（排列a1，…，ai，…，aj，…，an）必須滿足條件(｜ｊ－ｉ｜≠｜aj－ai｜)and(ai≠aj)(1≤i，j≤n)。3、解答樹（analytictree）現(xiàn)在讓我們先來觀察一個(gè)簡單的ｎ皇后問題。設(shè)ｎ＝4，初始狀態(tài)顯然是一個(gè)空棋盤。此時(shí)第一個(gè)皇后開始從第一行第一列位置試放，試放的順序是從左至右、自上而下。每個(gè)棋盤由４個(gè)數(shù)據(jù)表征相應(yīng)的狀態(tài)信息（見下圖）：（××××）其中第i（1≤i≤4）個(gè)數(shù)據(jù)指明當(dāng)前方案中第i個(gè)皇后置放在第i行的列位置。若該數(shù)據(jù)為０，表明所在行尚未放置皇后。棋盤狀

4、態(tài)的定義如下varstack：array[1‥4]ofinteger；{stack[i]為i行皇后的列位置}從初始的空棋盤出發(fā)，第１個(gè)皇后可以分別試放第１行的４個(gè)列位置，擴(kuò)展出４個(gè)子結(jié)點(diǎn)。在上圖中，結(jié)點(diǎn)右上方給出按回溯法擴(kuò)展順序定義的結(jié)點(diǎn)序號。現(xiàn)在我們也可以用相同方法找出這些結(jié)點(diǎn)的第二行的可能列位置，如此反復(fù)進(jìn)行，一旦出現(xiàn)新結(jié)點(diǎn)的四個(gè)數(shù)據(jù)全非空，那就尋到了一種滿足題意要求的擺法。當(dāng)嘗試了所有可能方案，即獲得了問題的解答，于是得到了下列圖形。該圖形象一棵倒懸的樹。其初始結(jié)點(diǎn)v1叫根結(jié)點(diǎn)，而最下端的結(jié)點(diǎn)v3、v5、v9、v13、v16、v17稱為葉結(jié)點(diǎn)，其中2個(gè)數(shù)據(jù)全非

5、零的葉結(jié)點(diǎn)，亦即本題的目標(biāo)結(jié)點(diǎn)。由根結(jié)點(diǎn)到每一個(gè)目標(biāo)結(jié)點(diǎn)之間，揭示了一種成功擺法的形成過程。顯然，４皇后問題存在由v9、v13表示的二種方案。上圖被稱作解答樹。樹中的每一結(jié)點(diǎn)都是當(dāng)前方案中滿足約束條件的元素狀態(tài)。除了根結(jié)點(diǎn)、葉結(jié)點(diǎn)以外的結(jié)點(diǎn)都稱作分枝結(jié)點(diǎn)。分枝結(jié)點(diǎn)愈接近根結(jié)點(diǎn)者，輩分愈高；反之，愈遠(yuǎn)離根結(jié)點(diǎn)者，輩分愈低。上圖中結(jié)點(diǎn)v7是結(jié)點(diǎn)v8的父結(jié)點(diǎn)（又稱前件），結(jié)點(diǎn)v13是結(jié)點(diǎn)v12的子結(jié)點(diǎn)（又稱后件）。某結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個(gè)數(shù)稱作該結(jié)點(diǎn)的次數(shù)。顯而易見，所有葉結(jié)點(diǎn)的次數(shù)為０。樹中各結(jié)點(diǎn)次數(shù)最大值，被稱作為該樹的次數(shù)。算符的個(gè)數(shù)即為結(jié)解答樹的次數(shù)。由上圖可見，

6、４皇后的解答樹是４次樹。一棵樹中的某個(gè)分枝結(jié)點(diǎn)也可視作為“子根”，以該結(jié)點(diǎn)為根的樹則稱作“子樹”。由以上討論可以看出解答樹的結(jié)構(gòu)：1、初始狀態(tài)構(gòu)成（主）樹的根結(jié)點(diǎn)。對應(yīng)于ｎ皇后來說，初始時(shí)的空棋盤即為根結(jié)點(diǎn)；2、除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)都具有一個(gè)、且只有一個(gè)父結(jié)點(diǎn)。對應(yīng)于ｎ皇后問題來說，置放i行皇后的子結(jié)點(diǎn)，只有在置放了前i-1行皇后的一個(gè)父結(jié)點(diǎn)基礎(chǔ)上產(chǎn)生；3、每個(gè)非根結(jié)點(diǎn)都有一條路徑通往根結(jié)點(diǎn)，其路徑長度（代價(jià)）定義為這條路徑的邊數(shù)。對應(yīng)于ｎ皇后來說，當(dāng)前行序號即為路徑代價(jià)。當(dāng)路徑代價(jià)為n＋１時(shí)，說明n個(gè)皇后已置放完畢，一種成功的擺法產(chǎn)生。有了以上的基礎(chǔ)知識和對ｎ皇

7、后問題的初步分析，我們已經(jīng)清楚地看到，求解ｎ皇后問題，無非就是做兩件事：1、從左至右逐條樹枝地構(gòu)造和檢查解答樹t；2、檢查t的結(jié)點(diǎn)是否對應(yīng)問題的目標(biāo)狀態(tài)；上述兩件事同時(shí)進(jìn)行。為了加快檢查速度，一般規(guī)定：1、再擴(kuò)展一個(gè)分枝結(jié)點(diǎn)前進(jìn)行檢查，只要它不滿足約束條件，則不再構(gòu)造以它為根的子樹；2、已處理過的結(jié)點(diǎn)若以后不會再用，則不必保留。即回溯過程中經(jīng)過的結(jié)點(diǎn)不再保留。例如在上圖中，當(dāng)我們求出第一種擺法v1－v2－v3后，由于皇后置放第三行任何列位置都會產(chǎn)生攻擊，因此舍棄該擺法，開始尋求第二種擺法。從上圖可看出，第二條路徑為v1－v2－v4－v5，v3在第二種擺法中不再用