一、8—皇后问题的分析
8—皇后问题实际上很容易一般化为n－皇后问题，即要求找出在一个n＊n棋盘上放置n个皇后并使其不能互相攻击的所有方案。令(x1，…，x )表示一个解，其中x 是把第i个皇后放在第i行的列数。由于没有两个皇后可以放入同一列；因此这所有的xi将是截然不同的。那么应如何去测试两个皇后是否在同一条斜角钱上呢?
如果设想：棋盘的方格像二维数组a(1：n，1：n)的下标那样标记，那么可以看到，对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的“行一列”值，同样，在同一条斜角线上的由右上方到左下方的每一个元素则有相同的“行+列”值。假设有两个皇后被放置在(i，j)和(k，1)位置上，那么根据以上所述，仅当
i-j=k-1或i+j=k+1
时，它们才在同一条斜角线上。将这两个等式分别变换成
j-1＝i-k 和 j-1＝k-i
因此，当且仅当|j一1|＝|i—k|时，两个皇后在同一条斜角线上。
过程Place(k)返回一个布尔值，当第k个皇后能放置于x（k）的当前值处时，这个返回值为真。这个过程测试两种情况，即x(k)是否不同于前面x(1)，…，x(k-1)的值以及在同一条斜角线上是否根本就没有别的皇后。该过程的计算时间是 。
二、8—皇后问题的算法
[算法]： 可以放置一个新皇后吗? [动画]
procedure Place(k)
／／如果一个皇后能放在第k行和x(k)列，则返回．true；否则返回false。x是
个全程数组，进入此过程时已置了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 ／／对所有的行执行以下语句／／
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) ／／是，打印这个数组／／
elsek<--k+1；x(k)+0 ／／转向下一行／／
else kßk-1 "回溯"
end nqueens
此时，读者可能对于过程nqueens怎么会优于硬性处理感奇怪。原因是这样的，如果硬
性要求一个8*8的棋盘安排出8块位置，就有 种可能的方式，即要检查将近4．4*10 个8—元组。然而过程nqueens只允许把皇后放置在不同的行和列上，因此至多需要作81次检
查，即至多只检查40320个8—元组。
可以用过程estimate来估算nqueens所生成的结点数。要指出的是，过程estimate所需要的假定也适用于nqueens，即，使用固定的限界函数且在检索进行时函数不改变。另外，在状态空间树的同一级的所有结点都有相同的度。图44．8显示了由过程estimate求结点估计数所用的五个8x8棋盘。如同所要求的那样，棋盘上每一个皇后的位置是随机选取的。对于每种选择方案，都记下了可以将一个皇后合法地放在各行中列的数目(即状态树的每一级没受限的结点数)。它们都列在每个棋盘下方的向量中。向量后面的数字表示过程estimate由这些量值所产生的值。这五次试验的平均值是1625。8—皇后状态空间树的结点总数是
因此不受限结点的估计数大约只是8—皇后状态空间树的结点总数的2．34％。
[动画]