拼图游戏的算法

相信大家都玩过”滑块拼图”游戏!
 大概说一下 :假如一副图是由几个部分拼凑成的,现在要你把这些散块拼凑成一副完整的图片
       也可以是几个数字来拼凑
 比如 3*3的格子
    1 2 3
    4 5 6
    7 8   (相当于原始矩阵)
有一个格子是空的现在要你组合成
   1 2 7
   3 6 4
   5 8     (目标矩阵)
问题是编写一种算法 能根据输入的原始图形(矩阵)拼凑成目标图形(目标矩阵) 要求是步数最少(耗时间最少)
 #include”iostream.h”
struct node{
int nodesun[4][4];

int x,y;
}path[1000];
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
int top;
int desti[4][4];//目标状态
int detect(struct node *p)
{int i,j;
 for(i=1;i<4;i++)
   for(j=1;j<4;j++)
  if(p->nodesun[j]!=desti[j])
  return 0;
 return 1;
}

void printlj()
{int tempt;
int i,j;
tempt=1;
while(tempt<=top)
{  for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<path[tempt].nodesun[j];
  if(j==3)
  cout<<” “<<endl;
 }
 tempt++;
}
}

 
 

void main()
{ //初始化
 int i,j,m,n,f;
 int temp,find=0;
 top=1;
for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<”请输入第”<<i<<”行”<<”第”<<j<<”列的值”<<endl;
  cin>>temp;
  path[1].nodesun[j]=temp;
 }
 cout<<”请输入初始状态的空格的位置(行)”<<endl;
 cin>>temp;
 path[1].x=temp;
cout<<”请输入初始状态的空格的位置(列)”<<endl;
 cin>>temp;
 path[1].y=temp;
//目标状态
for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<”请输入目标状态第”<<i<<”行”<<”第”<<j<<”列的值”<<endl;
  cin>>temp;
  desti[j]=temp;
 }
 //深度优先搜索
while(!find)
{ m=path[top].x;
 n=path[top].y ;
 for(f=0;f<4;f++)
 {i=m+zx[f];
  j=n+zy[f];
  if(i>=1&&i<=3&&j>=1&&j<= 3)
  {top++;
  path[top]=path[top-1];
path[top].nodesun[m][n]=path[top-1].nodesun[j];
path[top].nodesun[j]=0;

path[top].x=i;
path[top].y=j;

  if(detect(&path[top]))
  {printlj();
  find=1;
  break;
  }

  break;
  }//if
 
 }//for
 
  }//while
}



#include”iostream.h”
struct node{
int nodesun[4][4];
int pre;
int x,y;
}path[400];
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
int front,rear;
int desti[4][4];//目标状态
int detect(struct node *p)
{int i,j;
 for(i=1;i<4;i++)
   for(j=1;j<4;j++)
  if(p->nodesun[j]!=desti[j])
  return 0;
 return 1;
}

void printlj()
{int tempt;
int i,j;
tempt=rear;
while(tempt!=0)
{  for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<path[tempt].nodesun[j];
  if(j==3)
  cout<<” “<<endl;
 }
 tempt=path[tempt].pre;
}
}

 
 

void main()
{ //初始化
 int i,j,m,n,f;
 int temp,find=0;
 front=rear=1;
 path[1].pre=0;
for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<”请输入第”<<i<<”行”<<”第”<<j<<”列的值”<<endl;
  cin>>temp;
  path[1].nodesun[j]=temp;
 }
 cout<<”请输入初始状态的空格的位置(行)”<<endl;
 cin>>temp;
 path[1].x=temp;
cout<<”请输入初始状态的空格的位置(列)”<<endl;
 cin>>temp;
 path[1].y=temp;
//目标状态
for(i=1;i<4;i++)
   for(j=1;j<4;j++)
 {cout<<”请输入目标状态第”<<i<<”行”<<”第”<<j<<”列的值”<<endl;
  cin>>temp;
  desti[j]=temp;
 }
 //广度优先搜索
while(front<=rear&&!find)
{ m=path[front].x;
 n=path[front].y ;
 for(f=0;f<4;f++)
 {i=m+zx[f];
  j=n+zy[f];
  if(i>=1&&i<=3&&j>=1&&j<= 3)
  {rear++;
  path[rear]=path[front];
path[rear].nodesun[m][n]=path[front].nodesun[j];
path[rear].nodesun[j]=0;
path[rear].pre=front;
path[rear].x=i;
path[rear].y=j;
  if(detect(&path[rear]))
  {printlj();
  find=1;
  break;
  }
  }
 }
  front++;
  }
}

上面是用最简单的深度优先，广度优先直接搜索得来得，毫无AI可言，这并不说明我不能写出其更好得算法，这里最简单得的估价函数f(x)=g(x)+h(x)
g(x)用初始化的节点到当前的节点的路径长度来表示h(x)启发函数用当前状态和目标状态的位置不同的个数来表