求PASCAL递归八皇后程序，加解析，要在FREE PASCAL上过了的，事后给分
问题分析：
为了解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j，i与j的值都是从1到n。 当某个皇后占了位置（i，j）时，在这个位置的垂直方向，水平方向和斜线（两条斜线）方向都不能再放其它皇后了。显然n个皇后肯定是对应不同的i值，也即是在i的每一个值上都有一个皇后，现在的关键问题是求出每一个皇后的j坐标。
根据回溯法思想，从一条路往前走，能进则进，不能进则退，换一条路再试，直到所有路径都到试。按照此思想，直到第1个皇后的n-1个位置都试完，就可以得到全部的解，算法框架如下：
1、初始化棋盘为空
2、为皇后1选择合适位置
为第i个皇后选择合适位置的过程算法如下：
for j：=1 to n do
if (i,j)位置为空 then
begin
占用位置（i，j）
if i<n then 为i+1个皇后选择合适的位置 {实际是对此过程的递归调用}
else 输出一个解 {输出数组x}
释放位置（i，j）
end
下面以“四皇后问题”为例给出带“回溯”的一棵四叉树。
上图中只有A结点是合法布局。其余叶结点都不是合法布局。
上述算法中，较困难和关键的一步，是如何检查所选择的皇后位置(i,j)是否安全，即不被前面已放好的皇后攻击。下面我们就来解决这个问题。根据上述规则应检查以下3项要求：
（1）不在同一行；
（2）不在同一列；
（3）不在同一对角线；
第一个要求在用数组x表示状态时已解决；
第二个要求我们用标志数组a，如果第j列已放了皇后，则有：a[j]=TRUE
第三项检查对角线的问题，我们先分析一下同一对角线上的棋子的位置关系。我们发现，对于从右上到左下的对角线，例如：（6，6），（7，5），（8，4）…，类似地可发现有规律：i + j = 常数。此常数最小为1+1=2，最大为n+n=2*n，所以可以用数组b[2..2*n]来表示。对于从左上到右下的对角线，如：（1，3），（2，4），（3，5），（4，6）…，同一对角线的位置坐标i–j = 常数，这个常数，不同的对角线不一样，最小为1-n=-n+1，最大为n-1=n-1，因此我们也可以用一个标志数组c[-n+1..n-1]来表示它。
这样如果我们在第i行第j列上放置了皇后，则只要设置：a[j]=False；c[i-j]=False；b[i+j]=False；就可以解决是否被攻击的问题。为了方便起见我们把数组a、b、c的下标说明为子界类型-n+1..2*n。数组x记录每组解的排列。
非递归
program N_Queens;
const MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1-MaxN..MaxN-1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数 }
procedure Out;{输出方案}
var
I: Integer;
begin
Inc(Total);
Write(Total: 3, ':');
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Main;
var
K: Integer;
begin
X[1] := 0; K := 1;
while K > 0 do begin
if X[K] <> 0 then begin
A[X[K]] := True;
B[X[K] + K] := True;
C[X[K] - K] := True;
end;
Inc(X[K]);
while(X[K]<=N)and not(A[X[K]]and B[X[K]+K]and C[X[K]-K])do
Inc(X[K]); {寻找一个可以放置的位置}
if X[K] <= N then
if K = N then Out
else begin
A[X[K]] := False;
B[X[K] + K] := False;
C[X[K] -K] := False;
Inc(K);
X[K] := 0; {继续放置下一个皇后}
end
else Dec(K); {回溯}
end;
end;
begin
Write('Queens Number = ');
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, Sizeof(c), True);
Main;
Writeln('Total = ', Total);
end.
program N_Queens;
const
MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1-MaxN..MaxN-1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数}
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total); Write(Total: 3, ':');
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
递归：
procedure Try(I: Integer);
{搜索第I个皇后的可行位置}
var
J: Integer;
begin
if I = N + 1 then Out; {N个皇后都放置完毕，则输出解}
for J := 1 to N do
if A[J] and B[J + I] and C[J - I] then begin
X[I] := J;
A[J] := False;
B[J + I] := False;
C[J - I] := False;
Try(I + 1); {搜索下一皇后的位置}
A[J] := True;
B[J + I] := True;
C[J - I] := True;
end;
end;
begin
Write('Queens Numbers = ');
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, Sizeof(C), True);
Try(1);
Writeln('Total = ', Total);
end.
PROGRAM e710;
VAR
x:ARRAY[1..8]OF integer;
a,b,c:ARRAY[-7..16]OF boolean; {-7,16是观察棋盘得出的边界,看完后面就明白了}
i,g:integer;
PROCEDURE print(Var g:integer); {打印棋盘}
VAR k,j,h:integer;
BEGIN
IF g MOD 16=0
THEN readln; {每输出16个棋盘暂停一次,方便检查.}
writeln('means',g); {输出有第g种方法.可有可无.}
FOR j:=8 DOWNTO 1 DO
BEGIN
FOR k:=1 TO 16 DO write('_');
writeln;
FOR k:=1 TO 8 DO
IF x[k]=j
THEN BEGIN
FOR h:=1 TO k-1 DO write(' |');
write('Q|'); {Q代表皇后}
FOR h:=k TO 7 DO write(' |')
END;
writeln
END;
inc(g)
END;
PROCEDURE try(i:integer); {这里是核心了}
VAR j:integer;
BEGIN
FOR j:=1 TO 8 DO {j是棋盘的纵坐标,i是横坐标,画图可以看出只需循环j. }
IF a[j]AND b[i+j]AND c[i-j] {判断该格子是否被占, i+j和i-j都是这一个的斜线方向,自己画图就懂,若被占了直接返回上面的循环..该格子为空则继续下面 }
THEN BEGIN
x[i]:=j; {记录第i个皇后的纵坐标}
a[j]:=false;b[j+i]:=false;c[i-j]:=false; {将该格子占领}
IF i<8 {,i=8时,即排到 第八个皇后的时候,就打印棋盘}
THEN try(i+1) {没到第八个时则继续递归, 求i+1的皇后的位置}
ELSE print(g);
a[j]:=true;b[i+j]:=true;c[i-j]:=true
END;
END;
BEGIN
FOR i:=-7 TO 16 DO
BEGIN
a[i]:=true;b[i]:=true;c[i]:=true
END;
g:=1;
try(1)
END.
说的很详细了. 看不懂就补充提问吧.. 谢谢.. 打字辛苦呀.
