一、8—皇后問題的分析
8—皇后問題實際上很容易一般化為n－皇后問題，即要求找出在一個n＊n棋盤上放置n個皇后并使其不能互相攻擊的所有方案。令(x1，…，x )表示一個解，其中x 是把第i個皇后放在第i行的列數(shù)。由于沒有兩個皇后可以放入同一列；因此這所有的xi將是截然不同的。那么應(yīng)如何去測試兩個皇后是否在同一條斜角錢上呢?
如果設(shè)想：棋盤的方格像二維數(shù)組a(1：n，1：n)的下標那樣標記，那么可以看到，對于在同一條斜角線上的由左上方到右下方的每一個元素有相同的“行一列”值，同樣，在同一條斜角線上的由右上方到左下方的每一個元素則有相同的“行+列”值。假設(shè)有兩個皇后被放置在(i，j)和(k，1)位置上，那么根據(jù)以上所述，僅當
i-j=k-1或i+j=k+1
時，它們才在同一條斜角線上。將這兩個等式分別變換成
j-1＝i-k 和 j-1＝k-i
因此，當且僅當|j一1|＝|i—k|時，兩個皇后在同一條斜角線上。
過程Place(k)返回一個布爾值，當?shù)趉個皇后能放置于x（k）的當前值處時，這個返回值為真。這個過程測試兩種情況，即x(k)是否不同于前面x(1)，…，x(k-1)的值以及在同一條斜角線上是否根本就沒有別的皇后。該過程的計算時間是 。
二、8—皇后問題的算法
[算法]： 可以放置一個新皇后嗎? [動畫]
procedure Place(k)
／／如果一個皇后能放在第k行和x(k)列，則返回．true；否則返回false。x是
個全程數(shù)組，進入此過程時已置了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來改進以上算法給出的一般回溯方法，可得出下面求n—皇后問題正確解的算法。
[算法]： n—皇后問題的所有解 [動畫]
procedure nqueens(n)
／／此過程使用回溯法求出在一個n*n棋盤上放置n個皇后，使其不能互相攻擊
的所有可能位置／／
integer k，n，x(1:n)
x(1)ß0；kß1 ／／k是當前行；x(k)是當前列／／
whilek>0 do ／／對所有的行執(zhí)行以下語句／／
x(k)ßx(k)+1 ／／移到下一列／／
while x(k)≤n and not Place(k) do ／／此處能放這個皇后嗎／
x(k)+x(k)+1
ifx(k)≤n ／／找到一個位置／／
then if k＝n ／／是一個完整的解嗎／／
thenprint(x) ／／是，打印這個數(shù)組／／
elsek<--k+1；x(k)+0 ／／轉(zhuǎn)向下一行／／
else kßk-1 "回溯"
end nqueens
此時，讀者可能對于過程nqueens怎么會優(yōu)于硬性處理感奇怪。原因是這樣的，如果硬
性要求一個8*8的棋盤安排出8塊位置，就有 種可能的方式，即要檢查將近4．4*10 個8—元組。然而過程nqueens只允許把皇后放置在不同的行和列上，因此至多需要作81次檢
查，即至多只檢查40320個8—元組。
可以用過程estimate來估算nqueens所生成的結(jié)點數(shù)。要指出的是，過程estimate所需要的假定也適用于nqueens，即，使用固定的限界函數(shù)且在檢索進行時函數(shù)不改變。另外，在狀態(tài)空間樹的同一級的所有結(jié)點都有相同的度。圖44．8顯示了由過程estimate求結(jié)點估計數(shù)所用的五個8x8棋盤。如同所要求的那樣，棋盤上每一個皇后的位置是隨機選取的。對于每種選擇方案，都記下了可以將一個皇后合法地放在各行中列的數(shù)目(即狀態(tài)樹的每一級沒受限的結(jié)點數(shù))。它們都列在每個棋盤下方的向量中。向量后面的數(shù)字表示過程estimate由這些量值所產(chǎn)生的值。這五次試驗的平均值是1625。8—皇后狀態(tài)空間樹的結(jié)點總數(shù)是
因此不受限結(jié)點的估計數(shù)大約只是8—皇后狀態(tài)空間樹的結(jié)點總數(shù)的2．34％。
[動畫]