Question

八皇后算法 free pascal

Answer 1

〖问题描述〗
在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。
〖问题分析〗(聿怀中学吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8
（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；
如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
3、当n>;8时，便一一打印出结果。
〖优点〗逐一测试标准答案，不会有漏网之鱼。
〖参考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procedureprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceduretry(i:integer);
varj:integer;
begin
forj:=1to8do
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then
begin
a:=j;
b[j]:=1;
c[i+j]:=1;
d[i-j]:=1;
ifi<8thentry(i+1)
elseprint;
b[j]:=0;
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);
end.
==========================================
这是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
(col[i]=true)
then
ok:=true
end;
procedure
try(dep:integer);
var
i,j:integer;
begin
for
i:=1
to
max
do
//每一行均有max种放法，对吧？xixi~~~~
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.