Question

pascal 编程题 n皇后问题

在N*N的棋盘上放置N个皇后而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放置2个皇后),编程求解所有不同的摆放方法数目。
输入：
4
输出
2 4 1 3
2 1 4 2

Answer 1

program tt;
var a:array [1..100] of integer;
b,c,d:array [-100..200] of integer;
t,i,j,k:integer;
procedure print;
begin
t:=t+1;
write(t,' ');
for k:=1 to n do write(a[k],' ');
writeln;
end;

procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do {每个皇后都有n种可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突}
begin
a[i]:=j; {摆放皇后}
b[j]:=1; {宣布占领第J行}
c[i+j]:=1; {占领两个对角线}
d[i-j]:=1;
if i<n then try(i+1) {n个皇后没有摆完，递归摆放下一皇后}
else print; {完成任务，打印结果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
readln(n);
try(1);{从第1个皇后开始放置}
end.
另附八皇后：
program tt;
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[i]:=j; {摆放皇后}
b[j]:=1; {宣布占领第J行}
c[i+j]:=1; {占领两个对角线}
d[i-j]:=1;
if i<8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后}
else print; {完成任务，打印结果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
for k:=-7 to 16 do {数据初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{从第1个皇后开始放置}
end.

Answer 2

program bahuanghou;
var a:array[1..20] of integer;{a数组为行}
b:array[1..20] of boolean;{b数组为列}
c:array[-19..19] of boolean;{cd分别为两对角线}
m:array[2..40] of boolean;
x,y,n,k:integer;
procedure print;{若出现符合条件的一组，便输出}
var t,p:integer;
begin
t:=t+1;
write(t,' ');
for p:=1 to k do write(a[p],' ');
writeln;
end;

procedure try(x:integer);{核心：寻找皇后的位置}
var y:integer;
begin
for y:=1 to k do
begin
if (b[y]=true) and (c[x-y]=true) and (m[x+y]=true) then
begin
a[x]:=y;{令皇后在x行的y列}
b[y]:=false;{占领该列，该对角线}
c[x-y]:=false;
m[x+y]:=false;
if x<8 then try(x+1)
else print;
b[y]:=true;{回溯，取消标记}
c[x-y]:=true;
m[x+y]:=true;
end;
end;
end;

begin
readln(k);
for n:=1 to k do b[n]:=true;
for n:=-k+1 to k-1 do c[n]:=true;
for n:=2 to 2*k do m[n]:=true;

try(1);
readln;
end.

应该就是这样的了，还可以再优化一下的，自己想吧