一、8—皇后問(wèn)題的分析   

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

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

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

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

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

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

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

二、8—皇后問(wèn)題的算法  

[算法]： 可以放置一個(gè)新皇后嗎?   [動(dòng)畫]

    procedure Place(k)

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

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

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

    iß1

    while i<k do

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

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

    then return(false)

    endif

    ißi+1

    repeat

    return(true)

    end Place

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

   [算法]： n—皇后問(wèn)題的所有解   [動(dòng)畫]

    procedure nqueens(n)

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

    的所有可能位置／／

    integer k，n，x(1:n)

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

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

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

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

    x(k)+x(k)+1

    repeat

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

    then if k＝n ／／是一個(gè)完整的解嗎／／

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

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

    endif

    else kßk-1 "回溯"

    endif

    repeat

    end nqueens

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

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

查，即至多只檢查40320個(gè)8—元組。

可以用過(guò)程estimate來(lái)估算nqueens所生成的結(jié)點(diǎn)數(shù)。要指出的是，過(guò)程estimate所需要的假定也適用于nqueens，即，使用固定的限界函數(shù)且在檢索進(jìn)行時(shí)函數(shù)不改變。另外，在狀態(tài)空間樹的同一級(jí)的所有結(jié)點(diǎn)都有相同的度。圖44．8顯示了由過(guò)程estimate求結(jié)點(diǎn)估計(jì)數(shù)所用的五個(gè)8x8棋盤。如同所要求的那樣，棋盤上每一個(gè)皇后的位置是隨機(jī)選取的。對(duì)于每種選擇方案，都記下了可以將一個(gè)皇后合法地放在各行中列的數(shù)目(即狀態(tài)樹的每一級(jí)沒(méi)受限的結(jié)點(diǎn)數(shù))。它們都列在每個(gè)棋盤下方的向量中。向量后面的數(shù)字表示過(guò)程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％。

[動(dòng)畫]