八皇后问题求解方法分类

八皇后问题

{
“八皇后”问题递归法求解 (Pascal语言)

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。现代教学中，把八皇后问题当成一个经典递归算法例题。

算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；
数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；
数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；
另优化：第一个皇后在1~4格，最后*2，即为总解数

}
program queens;
var a:array [1..8] of integer;
b,c,d:array [-7..16] of integer;
t,i,j,k:integer;
procedure print;
begin
t:=t+1;
write(t,': ');
for k:=1 to 8 do write(a[k],' ');
writeln;
end;

procedure try(i:integer);
var j:integer;
begin
for j:=1 to 8 do {每个皇后都有8种可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突}
begin
a:=j; {摆放皇后}
b[j]:=1; {宣布占