主题:[讨论]孔明棋走法的搜索
孔明棋的走法包含在程序中,大家看一下,我不认为我用错了方法,到底是哪里错了呢?program kongm(input,output,f);
type tt=record
l,h:integer;
f:integer;
end;
type ss=record
sh:array[1..32]of tt;
max,st:integer;
end;
var f:text;
lh:array[0..7,0..7]of 0..1;i,j,st:integer;
rec:array[1..32]of ss;c:array[1..32]of tt;
m,n:integer;
procedure find;
var i,j:integer;
begin
for i:=3 to 5 do
for j:=2 to 6 do
if (lh[i,j-1]=1)and(lh[i,j]=1)and(lh[i,j+1]=0)
then begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=1;
end
else if (lh[i,j+1]=1)and(lh[i,j]=1)and(lh[i,j-1]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=2;
end;
for j:=3 to 5 do
for i:=2 to 6 do
if (lh[i-1,j]=1)and(lh[i,j]=1)and(lh[i+1,j]=0) then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end else
if (lh[i-1,j]=0)and(lh[i,j]=1)and(lh[i+1,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
for i:=1to 2 do
if (lh[i,3]=1)and(lh[i,4]=1)and(lh[i,5]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=1;
end
else if(lh[i,3]=0)and(lh[i,4]=1)and(lh[i,5]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=2;
end;
for i:=6 to 7 do
if (lh[i,3]=1)and(lh[i,4]=1)and(lh[i,5]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=1;
end
else if(lh[i,3]=0)and(lh[i,4]=1)and(lh[i,5]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=2;
end;
for j:=1 to 2 do
if (lh[3,j]=1)and(lh[4,j]=1)and(lh[5,j]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end
else if(lh[3,j]=0)and(lh[4,j]=1)and(lh[5,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
for j:=6 to 7 do
if (lh[3,j]=1)and(lh[4,j]=1)and(lh[5,j]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end
else if(lh[3,j]=0)and(lh[4,j]=1)and(lh[5,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
rec[st].max:=rec[st].st;rec[st].st:=1;
end;
begin
assign(f,'d:\huang\answer.txt');
rewrite(f);
for i:=3 to 5 do
for j:=1 to 7 do
lh[i,j]:=1;
for j:=3 to 5 do
for i:=1 to 7 do
lh[i,j]:=1;
lh[4,4]:=0;
for i:=1 to 7 do
begin
for j:=1 to 7 do
write(lh[j,i]);
writeln;
end;
st:=1;find;
repeat
if (rec[st].st<=rec[st].max)then
begin
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h]:=0;
case rec[st].sh[rec[st].st].f of
1:begin lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h-1]:=0;
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h+1]:=1;
end;
2:begin lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h+1]:=0;
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h-1]:=1;
end;
3:begin lh[rec[st].sh[rec[st].st].l+1,rec[st].sh[rec[st].st].h]:=1;
lh[rec[st].sh[rec[st].st].l-1,rec[st].sh[rec[st].st].h]:=0;
end;
4:begin lh[rec[st].sh[rec[st].st].l+1,rec[st].sh[rec[st].st].h]:=0;
lh[rec[st].sh[rec[st].st].l-1,rec[st].sh[rec[st].st].h]:=1;
end;
end;
c[st].l:=rec[st].sh[rec[st].st].l;
c[st].h:=rec[st].sh[rec[st].st].h;
c[st].f:=rec[st].sh[rec[st].st].f;
writeln('step',st);
st:=st+1;rec[st].st:=0;find;
end
else begin
st:=st-1;
lh[c[st].l,c[st].h]:=1;
case c[st].f of
1:begin lh[c[st].l,c[st].h-1]:=1;
lh[c[st].l,c[st].h+1]:=0;
end;
2:begin lh[c[st].l,c[st].h-1]:=0;
lh[c[st].l,c[st].h+1]:=1;
end;
3:begin lh[c[st].l-1,c[st].h]:=1;
lh[c[st].l+1,c[st].h]:=0;
end;
4:begin lh[c[st].l-1,c[st].h]:=0;
lh[c[st].l+1,c[st].h]:=1;
end;
end;{case}
writeln('huifu-->');
inc(rec[st].st);
end;
if (st=32)and(lh[4,4]=1)then begin
for m:=1 to 31 do
begin
writeln;writeln(f);
write('(',c[m].l,' ',c[m].h,')[',c[m].f,']');
write(f,'(',c[m].l+(c[m].h-1)*7,')[',c[m].f,']');
end;readln;
end;
until rec[1].st>rec[1].max;
end.用回溯做的[size=3][/size][size=6][/size][color=0000FF][/color]
type tt=record
l,h:integer;
f:integer;
end;
type ss=record
sh:array[1..32]of tt;
max,st:integer;
end;
var f:text;
lh:array[0..7,0..7]of 0..1;i,j,st:integer;
rec:array[1..32]of ss;c:array[1..32]of tt;
m,n:integer;
procedure find;
var i,j:integer;
begin
for i:=3 to 5 do
for j:=2 to 6 do
if (lh[i,j-1]=1)and(lh[i,j]=1)and(lh[i,j+1]=0)
then begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=1;
end
else if (lh[i,j+1]=1)and(lh[i,j]=1)and(lh[i,j-1]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=2;
end;
for j:=3 to 5 do
for i:=2 to 6 do
if (lh[i-1,j]=1)and(lh[i,j]=1)and(lh[i+1,j]=0) then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end else
if (lh[i-1,j]=0)and(lh[i,j]=1)and(lh[i+1,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
for i:=1to 2 do
if (lh[i,3]=1)and(lh[i,4]=1)and(lh[i,5]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=1;
end
else if(lh[i,3]=0)and(lh[i,4]=1)and(lh[i,5]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=2;
end;
for i:=6 to 7 do
if (lh[i,3]=1)and(lh[i,4]=1)and(lh[i,5]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=1;
end
else if(lh[i,3]=0)and(lh[i,4]=1)and(lh[i,5]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=i;
rec[st].sh[rec[st].st].h:=4;
rec[st].sh[rec[st].st].f:=2;
end;
for j:=1 to 2 do
if (lh[3,j]=1)and(lh[4,j]=1)and(lh[5,j]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end
else if(lh[3,j]=0)and(lh[4,j]=1)and(lh[5,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
for j:=6 to 7 do
if (lh[3,j]=1)and(lh[4,j]=1)and(lh[5,j]=0)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=3;
end
else if(lh[3,j]=0)and(lh[4,j]=1)and(lh[5,j]=1)then
begin
inc(rec[st].st);
rec[st].sh[rec[st].st].l:=4;
rec[st].sh[rec[st].st].h:=j;
rec[st].sh[rec[st].st].f:=4;
end;
rec[st].max:=rec[st].st;rec[st].st:=1;
end;
begin
assign(f,'d:\huang\answer.txt');
rewrite(f);
for i:=3 to 5 do
for j:=1 to 7 do
lh[i,j]:=1;
for j:=3 to 5 do
for i:=1 to 7 do
lh[i,j]:=1;
lh[4,4]:=0;
for i:=1 to 7 do
begin
for j:=1 to 7 do
write(lh[j,i]);
writeln;
end;
st:=1;find;
repeat
if (rec[st].st<=rec[st].max)then
begin
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h]:=0;
case rec[st].sh[rec[st].st].f of
1:begin lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h-1]:=0;
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h+1]:=1;
end;
2:begin lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h+1]:=0;
lh[rec[st].sh[rec[st].st].l,rec[st].sh[rec[st].st].h-1]:=1;
end;
3:begin lh[rec[st].sh[rec[st].st].l+1,rec[st].sh[rec[st].st].h]:=1;
lh[rec[st].sh[rec[st].st].l-1,rec[st].sh[rec[st].st].h]:=0;
end;
4:begin lh[rec[st].sh[rec[st].st].l+1,rec[st].sh[rec[st].st].h]:=0;
lh[rec[st].sh[rec[st].st].l-1,rec[st].sh[rec[st].st].h]:=1;
end;
end;
c[st].l:=rec[st].sh[rec[st].st].l;
c[st].h:=rec[st].sh[rec[st].st].h;
c[st].f:=rec[st].sh[rec[st].st].f;
writeln('step',st);
st:=st+1;rec[st].st:=0;find;
end
else begin
st:=st-1;
lh[c[st].l,c[st].h]:=1;
case c[st].f of
1:begin lh[c[st].l,c[st].h-1]:=1;
lh[c[st].l,c[st].h+1]:=0;
end;
2:begin lh[c[st].l,c[st].h-1]:=0;
lh[c[st].l,c[st].h+1]:=1;
end;
3:begin lh[c[st].l-1,c[st].h]:=1;
lh[c[st].l+1,c[st].h]:=0;
end;
4:begin lh[c[st].l-1,c[st].h]:=0;
lh[c[st].l+1,c[st].h]:=1;
end;
end;{case}
writeln('huifu-->');
inc(rec[st].st);
end;
if (st=32)and(lh[4,4]=1)then begin
for m:=1 to 31 do
begin
writeln;writeln(f);
write('(',c[m].l,' ',c[m].h,')[',c[m].f,']');
write(f,'(',c[m].l+(c[m].h-1)*7,')[',c[m].f,']');
end;readln;
end;
until rec[1].st>rec[1].max;
end.用回溯做的[size=3][/size][size=6][/size][color=0000FF][/color]