|
一【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇
后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。
下面是算法的实现源码，请大家讨论。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; {放皇后数组}
b:array[2..2*max] of boolean; {/对角线标志数组}
c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
col:array[1..max] of boolean; {列标志数组}
total:integer; {统计总数}
procedure output; {输出}
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do
write(a[i]:3);write(' ');
if (total+1) mod 2 =0
then
writeln; inc(total);
end;
function ok(i,dep:integer):boolean; {判断第dep行第i列可放否}
begin
ok:=false;
if
( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
(col[i]=true)
then ok:=true
end;
procedure try(dep:integer);
var i,j:integer;
begin
for i:=1
to max do {每一行均有max种放法}
if ok(i,dep) then
begin
a[dep]:=i;
b[i+dep]:=false; {/对角线已放标志}
c[dep-i]:=false; {\对角线已放标志}
col[i]:=false; {列已放标志}
if
dep=max then output
else try(dep+1); {递归下一层}
a[dep]:=0; {取走皇后,回溯}
b[i+dep]:=true; {恢复标志数组}
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do
begin
a[i]:=0;col[i]:=true;
end;
for i:=2 to 2*max do
b[i]:=true;
for i:=-(max-1) to max-1 do
c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
|