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

什么八数码问题呀？如果是八皇后问题的话，你可以看看这个。

【原创】试探法求解N皇后问题C++编程
2010-06-01 20:39:21 阅读9 评论0 字号：大中小
终于让我给想出来了！哈哈！

#include <iostream>
#include <cmath>
using namespace std;

class Queen
{
public:

 Queen(int n);

 void Print();

 void Move(int m);

 void Fill1(int data);

 void Fill0();
public:

 int ci;

 int num;

 int qipan[20+1][20+1];

 int pt[20+1];
};

Queen::Queen(int n)
{

 ci=0;

 pt[0]=0;

 num=n;

 for(int i=1;i<=num;i++)
  for(int j=1;j<=num;j++)
   qipan[i][j]=0;

 Move(1);
}

void Queen::Fill0()
{

 for(int i=1;i<=num;i++)
  for(int j=1;j<=num;j++)
   if(qipan[i][j]==pt[0])
    qipan[i][j]=0;
}

void Queen::Fill1(int data)
{

 int hang=pt[0];

 int lie=pt[pt[0]];


 int i;

 for(i=1;i<=num;i++)

 {
  if(qipan[hang][i]==0)
   qipan[hang][i]=data;
  if(qipan[i][lie]==0)
   qipan[i][lie]=data;

 }


 if(hang+lie<=num)

 {
  for(i=1;i<=hang+lie-1;i++)
   if(qipan[hang+lie-i][i]==0)
    qipan[hang+lie-i][i]=data;

 }

 else

 {
  for(i=(hang+lie)%num;i<=num;i++)
   if(qipan[hang+lie-i][i]==0)
    qipan[hang+lie-i][i]=data;

 }


 if(hang>lie)

 {
  for(i=1;i<=num-hang+lie;i++)
   if(qipan[hang-lie+i][i]==0)
    qipan[hang-lie+i][i]=data;

 }

 else

 {
  for(i=1+lie-hang;i<=num;i++)
   if(qipan[hang-lie+i][i]==0)
    qipan[hang-lie+i][i]=data;

 }
}

void Queen::Move(int m)
{

 pt[0]++;

 for(int i=1;i<=num;i++)

 {
  if(qipan[m][i]==0)
  {
   pt[pt[0]]=i;
   Fill1(pt[0]);
   Move(m+1);
  }

 }


 Print();


 {
  pt[0]--;
  Fill0();
  m=pt[0];

 }
}

void Queen::Print()
{

 if(pt[0]>num)

 {
  ci++;
  cout<<"第"<<ci<<"种解法:"<<endl;
  for(int i=1;i<=num;i++)
  {
   for(int j=1;j<=num;j++)
   {
    if(j==pt[i])
     cout<<"@ ";
    else
     cout<<"* ";
   }
   cout<<endl;
  }

 }
}

int main()
{

 Queen q(9);


 return 0;
}

你看看是不是你想要的。

例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语言的