用回溯法解决八数码问题(不要递归的)

例1：8数码难题 ：

                2 8 3    1 2 3

                1 6 4 -> 8   4（用最少的步数）

                7   5    7 6 5

程序如下：

program num8;
const maxn=4000;
type jid=record
     str:string[9];
     f:0..maxn;
     dep:byte;
     end;
    bin=0..1;
var c:array[0..1,1..maxn] of ^jid;
    head,tail:array[0..1] of integer;
    start,goal:string[9];
procedure init;
var i,j:integer;
begin
 start:='283164705';
 goal:='123804765';
 for i:=0 to 1 do
  for j:=1 to maxn do
    new(c[i,j]);
 c[0,1]^.str:=start; c[0,1]^.f:=0; c[0,1]^.dep:=0;
 c[1,1]^.str:=goal;  c[1,1]^.f:=0; c[1,1]^.dep:=0;
 for i:=0 to 1 do
  begin head[i]:=0;tail[i]:=1;end;
end;
procedure print(st:bin;tail,k:integer);
procedure print0(m:integer);
begin
if m<>0 then
 begin print0(c[0,m]^.f);writeln(c[0,m]^.str) end;
end;
procedure print1(m:integer);
var n:integer;
begin
 n:=c[1,m]^.f;
 while n<>0 do
  begin writeln(c[1,n]^.str); n:=c[1,n]^.f end;
end;
begin
 if st=0 then
    begin writeln('step=',c[0,tail]^.dep+c[1,k]^.dep);
         print0(tail); print1(k);end
        else begin writeln('step=',c[0,k]^.dep+c[1,tail]^.dep);
        print0(k); print1(tail); end ;
halt;
end;
procedure check(st:bin);
procedure bool(st:bin);
var i:integer;
begin
 for i:=1 to tail[1-st] do
  if c[st,tail[st]]^.str=c[1-st,i]^.str then  print(st,tail[st],i);
end;
var i:integer;
begin
  for i:=1 to tail[st]-1 do
   if c[st,tail[st]]^.str=c[st,i]^.str then
    begin dec(tail[st]);exit end;
  bool(st);
end;
procedure expand(st:bin);
var i,p0,p1,d:integer;
str0,str1:string[9];
begin
 inc(head[st]);
 str0:=c[st,head[st]]^.str;
 d:=c[st,head[st]]^.dep;
 p0:=pos('0',str0);
 for i:=1 to 4 do
   begin
    if tail[st]>=maxn then exit;
    p1:=p0+2*i-5;
    if (p1 in [1..9]) and not ((p0=3) and (p1=4))and not((p0=4)and (p1=3))
       and not((p0=6)and(p1=7))and not((p0=7)and(p1=6))
      then
       begin
        inc(tail[st]);
        str1:=str0;
        str1[p0]:=str1[p1];
        str1[p1]:='0';
        c[st,tail[st]]^.str:=str1;
        c[st,tail[st]]^.f:=head[st];
        c[st,tail[st]]^.dep:=d+1;
        check(st);
       end;
   end;
 end;
begin
 init;
 check(0);
 repeat
   if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn))
    then expand(0);
   if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn))
    then expand(1);
   if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0);
   if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1);
Until((head[0]>=tail[0])or(tail[0]>=maxn))And((head[1]>=tail[1])or(tail[1]>=maxn));
writeln('No answer');
end.
好不容易找到了 但是不是C语言的