Question

PASCAL八皇后问题

输出一共有几种方法，我写的程序不知为何不对，请各位赐教：

var
s,i,j,l,n:integer;
a:array[1..8,1..8]of integer;

procedure find(k:integer);
var
p:integer;
begin
if k>8 then s:=s+1 else
begin
for i:=1 to 8 do
begin
p:=0;
a[i,k]:=1;
for j:=1 to k-1 do
if a[i,j]<>0 then p:=1;
if p=0 then
for l:=1 to 8 do
for n:=1 to k do
if (a[l,n]=1) and (abs(l-n)=abs(i-k)) then p:=1;
if p=0 then begin a[i,k]:=1; find(k+1); end
else a[i,k]:=0;
end;
end;
end;

begin
for i:=1 to 8 do
for j:=1 to 8 do
a[i,j]:=0;
find(1);
writeln(s);
end.

Answer 1

var
n,upperlim,sum:longint;
procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin

if row<>upperlim then
begin
pos:=upperlim and not (row or ld or rd);
while pos<>0 do
begin
p:=pos and -pos;
pos:=pos-p;
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
end;
end
else inc(sum);

end;
begin
readln(n);
sum:=0;
upperlim:=(1 shl n)-1;
test(0,0,0);
writeln(sum);
end.
位运算才是王道啊，用这个交usaco秒过

Answer 2

这个正确，是n皇后问题，改改n就可以了
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;

end.

Answer 3

1楼，你似乎是没学过DFS吧！8皇后都不知道，n皇后是8皇后的拓展。

8皇后代码：

var x:array [1..8] of longint;
a,b,c:array [-7..16] of boolean;
i,o,tot:longint;

procedure dfs(i:longint);
var
j:longint;
begin
for j:=1 to 8 do
begin
if a[j] and b[i+j] and c[i-j] then
begin
x[i]:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<8 then dfs(i+1)
else inc(tot);
a[j]:=true;
b[i+j]:=true;
c[i-j]:=true;
end;
end;
end;

begin
fillchar(a,sizeof(a),true);
fillchar(b,sizeof(b),true);
fillchar(c,sizeof(c),true);
dfs(1);
writeln(tot)
end.

Answer 4

你不会？真垃圾！找找2008篇的《pascal语言教程练习》，里面有答案啊^_^不过说实在的，我也不会~_~!

o(∩_∩)o