bsm.c

用C语言编写的八数码问题算法

#include"iostream.h" 

struct node{ 
int nodesun[4][4]; 
int pre; 
int flag; 
int value; 
int x,y; 
}queue[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=top; 
while(tempt!=0) 
{    for(i=1;i<4;i++) 
    for(j=1;j<4;j++) 
 {cout<<queue[tempt].nodesun[j]; 
  if(j==3) 
   cout<<" "<<endl; 
 } 
 tempt=queue[tempt].pre; 
} 
} 

   
   


  int VALUE(struct node *p) 
{int count=0; 
   
  int i,j; 
for(i=1;i<4;i++) 
    for(j=1;j<4;j++) 
if(p->nodesun[j]!=desti[j]) 
count++; 
return count; 
} 


   

void main() 
{ //初始化 
 int i,j,m,n,f; 
 int min=10; 
 int temp,find=0,minnumber; 
 top=1; 
for(i=1;i<4;i++) 
    for(j=1;j<4;j++) 
 {cout<<"请输入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl; 
  cin>>temp; 
  queue[1].nodesun[j]=temp; 
 } 
 cout<<"请输入初始状态的空格的位置(行)"<<endl; 
 cin>>temp; 
queue[1].x=temp; 
cout<<"请输入初始状态的空格的位置(列)"<<endl; 
 cin>>temp; 
 queue[1].y=temp; 
queue[1].value=VALUE(&queue[1]); 
queue[1].pre=0; 
queue[1].flag=0; 

//目标状态 
for(i=1;i<4;i++) 
    for(j=1;j<4;j++) 
 {cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl; 
  cin>>temp; 
  desti[j]=temp; 
 } 
 //根据估价函数 
while(!find&&top>0) 
{ for(i=1;i<=top;i++) 
 {if(queue.value<min&&queue.flag==0) 
 {minnumber=i; 
  min=queue.value; 
   } 
} 
queue[minnumber].flag=1; 
min=10; 

 for(f=0;f<4;f++) 
 {m=queue[minnumber].x; 
 n=queue[minnumber].y; 
i=m+zx[f]; 
  j=n+zy[f]; 
  if(i>=1&&i<=3&&j>=1&&j<=3) 
  {top++; 
   queue[top]=queue[minnumber]; 
queue[top].nodesun[m][n]=queue[minnumber].nodesun[j]; 
queue[top].nodesun[j]=0; 

queue[top].x=i; 
queue[top].y=j; 
queue[top].pre=minnumber; 
queue[top].value=VALUE(&queue[top]); 
queue[top].flag=0; 

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


  }//if 
  
 }//for 
   
  }//while 
}