一、8—皇后問題的分析   

8—皇后問題實(shí)際上很容易一般化為n－皇后問題，即要求找出在一個n＊n棋盤上放置n個皇后并使其不能互相攻擊的所有方案。令(x1，…，x )表示一個解，其中x 是把第i個皇后放在第i行的列數(shù)。由于沒有兩個皇后可以放入同一列；因此這所有的xi將是截然不同的。那么應(yīng)如何去測試兩個皇后是否在同一條斜角錢上呢? 

    如果設(shè)想：棋盤的方格像二維數(shù)組a(1：n，1：n)的下標(biāo)那樣標(biāo)記，那么可以看到，對于在同一條斜角線上的由左上方到右下方的每一個元素有相同的“行一列”值，同樣，在同一條斜角線上的由右上方到左下方的每一個元素則有相同的“行+列”值。假設(shè)有兩個皇后被放置在(i，j)和(k，1)位置上，那么根據(jù)以上所述，僅當(dāng)

        i-j=k-1或i+j=k+1

時，它們才在同一條斜角線上。將這兩個等式分別變換成

       j-1＝i-k 和 j-1＝k-i

因此，當(dāng)且僅當(dāng)|j一1|＝|i—k|時，兩個皇后在同一條斜角線上。

    過程Place(k)返回一個布爾值，當(dāng)?shù)趉個皇后能放置于x（k）的當(dāng)前值處時，這個返回值為真。這個過程測試兩種情況，即x(k)是否不同于前面x(1)，…，x(k-1)的值以及在同一條斜角線上是否根本就沒有別的皇后。該過程的計(jì)算時間是 。

二、8—皇后問題的算法  

[算法]： 可以放置一個新皇后嗎?   [動畫]

    procedure Place(k)

    ／／如果一個皇后能放在第k行和x(k)列，則返回．true；否則返回false。x是

    個全程數(shù)組，進(jìn)入此過程時已置了k個值。abs(r)過程返回r的絕對值／／

    global x(1：k)；integer i；k

    iß1

    while i<k do

    if x(i)＝x(k) ／／在同一列有兩個皇后／／

    or abs(x(i)-x(k))＝abs(i-k) ／／在同一條斜角線上／／

    then return(false)

    endif

    ißi+1

    repeat

    return(true)

    end Place

使用過程Place來改進(jìn)以上算法給出的一般回溯方法，可得出下面求n—皇后問題正確解的算法。

   [算法]： n—皇后問題的所有解   [動畫]

    procedure nqueens(n)

    ／／此過程使用回溯法求出在一個n*n棋盤上放置n個皇后，使其不能互相攻擊

    的所有可能位置／／

    integer k，n，x(1:n)

    x(1)ß0；kß1 ／／k是當(dāng)前行；x(k)是當(dāng)前列／／

    whilek>0 do ／／對所有的行執(zhí)行以下語句／／

    x(k)ßx(k)+1 ／／移到下一列／／

    while x(k)≤n and not Place(k) do ／／此處能放這個皇后嗎／

    x(k)+x(k)+1

    repeat

    ifx(k)≤n ／／找到一個位置／／

    then if k＝n ／／是一個完整的解嗎／／

    thenprint(x) ／／是，打印這個數(shù)組／／

                  elsek<--k+1；x(k)+0 ／／轉(zhuǎn)向下一行／／

    endif

    else kßk-1 "回溯"

    endif

    repeat

    end nqueens

    此時，讀者可能對于過程nqueens怎么會優(yōu)于硬性處理感奇怪。原因是這樣的，如果硬

性要求一個8*8的棋盤安排出8塊位置，就有 種可能的方式，即要檢查將近4．4*10 個8—元組。然而過程nqueens只允許把皇后放置在不同的行和列上，因此至多需要作81次檢

查，即至多只檢查40320個8—元組。

可以用過程estimate來估算nqueens所生成的結(jié)點(diǎn)數(shù)。要指出的是，過程estimate所需要的假定也適用于nqueens，即，使用固定的限界函數(shù)且在檢索進(jìn)行時函數(shù)不改變。另外，在狀態(tài)空間樹的同一級的所有結(jié)點(diǎn)都有相同的度。圖44．8顯示了由過程estimate求結(jié)點(diǎn)估計(jì)數(shù)所用的五個8x8棋盤。如同所要求的那樣，棋盤上每一個皇后的位置是隨機(jī)選取的。對于每種選擇方案，都記下了可以將一個皇后合法地放在各行中列的數(shù)目(即狀態(tài)樹的每一級沒受限的結(jié)點(diǎn)數(shù))。它們都列在每個棋盤下方的向量中。向量后面的數(shù)字表示過程estimate由這些量值所產(chǎn)生的值。這五次試驗(yàn)的平均值是1625。8—皇后狀態(tài)空間樹的結(jié)點(diǎn)總數(shù)是

 因此不受限結(jié)點(diǎn)的估計(jì)數(shù)大約只是8—皇后狀態(tài)空間樹的結(jié)點(diǎn)總數(shù)的2．34％。

[動畫]