01.cpp

用Ａ＊算法来对人工智能中的八数码难题进行实现

#include <iostream.h>

#include <malloc.h>
struct node 
{
	int a[9] ;
	int g ;
	int f ;
    struct node *parent ;
} ;
struct node1
{
	struct node  *t ;
	struct node1 *next ;
} ;
int target[9]={1,2,3,8,0,4,7,6,5} ;
struct node1 *head_open ,*head_close ;

int s_Blank( int p[9])
{
	for(int i=0; i<9 ;i++ )
	if(p[i]==0) break ;
		return i ;
}

int m_Target(int p[9] )
{
	int count=9 ;
	for(int i=0 ;i<9 ;i++)
	{
		
		if(p[i]==target[i]) count-- ;
	}
	return count ;
}
int  pipei_Target(struct node *p)
{
	for(int i=0 ;i<9 ;i++)
	{
		
		if(p->a[i]!=target[i]) break ;
		//cout<<p->a[i]<<"--------"<<target[i]<<endl ;/////////////////////////////////////////////
	}
	//cout<<i<<endl ;
	if(i==9) 
	{
		cout<<"成功！！"<<endl ;
		int i1 ;
		for( i1=0 ;i1<3 ;i1++)
				cout<<target[i1]<<"    "  ;
			cout<<endl ;
			for( i1=3 ;i1<6 ;i1++)
				cout<<target[i1]<<"    " ;
			cout<<endl ;
			for( i1=6;i1<9 ;i1++)
				cout<<target[i1]<<"    "  ;
			cout<<endl ;
			cout<<endl ;
			cout<<endl ;






		while(p->parent!=NULL)
		{
			int i ;
			for( i=0 ;i<3 ;i++)
				cout<<p->parent->a[i]<<"    "  ;
			cout<<endl ;
			for( i=3 ;i<6 ;i++)
				cout<<p->parent->a[i]<<"    " ;
			cout<<endl ;
			for( i=6;i<9 ;i++)
				cout<<p->parent->a[i]<<"    "  ;
			cout<<endl ;
			cout<<endl ;
			cout<<endl ;

			p=p->parent ;
		}

		return 0 ;
	}
	else return 1 ;
}


void add_Headopen(struct node *p)
{
	
	struct node1 *q,*h ;
	q=head_open->next ;
	
	
	while(q->next!=NULL&&q->next->t->f<p->f)
	{ 
	//cout<<endl ;
		   //cout<<p->f<<"子/////上"<<q->next->t->f<<endl;	


		q=q->next ;
		
	}
	


	//int p3 ;
	//1	cin>>p3 ;
	
	h=(struct node1*) malloc(sizeof(struct node1)) ;
	h->t=p;
	h->next=q->next;
	q->next=h;
	
}







void main()
{
	struct node *p1 ;
    struct node1 *h1 ;

	int i=0,d ;
	struct node *q ;
	struct node1 *h ;
	head_open=(struct node1*) malloc(sizeof(struct node1)) ;
head_close=(struct node1*) malloc(sizeof(struct node1)) ;

	q= (struct node *) malloc(sizeof(struct node)) ;
for(i=0 ; i<9;i++ )
	{
		cin>>d ;
		q->a[i]=d  ;
 }
q->f=0;
q->g=0;
q->parent=NULL ;
   h=(struct node1*) malloc(sizeof(struct node1)) ;
   h->t=q ;
   h->next=NULL ;
   head_open->next=h ;
   head_close->next=h;
   h->next=NULL ;
   int t1=1 ;
   //////////////处理
   while(t1) 
   {
	   
	   int t,i,j,p ;
	   
	   t=s_Blank(head_open->next->t->a ) ;
	   i=t/3 ;
	   j=t%3 ;
	   /////////////////////////////////////////cout<<i<<j<<endl ;
	   /////////////////////////向左走
	   if(j-1>=0) 
	   {
		   q= (struct node *) malloc(sizeof(struct node)) ;
		   //struct node *p1 ;
	       //struct node1 *h1 ;
		   int c[9];
		   for(int i1=0 ;i1<9 ;i1++)
		   {
			   c[i1]=head_open->next->t->a[i1] ;
		   }
		   p=3*i+j-1 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		  c[t]=c[p] ;
		  c[p]=0 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		   for(int i2=0 ; i2<9;i2++ )
		   {
			   
		      q->a[i2]= c[i2] ;
			  ///////////////////////////
		   }
		   if(head_open->next->t->parent==NULL)
			   q->g=1;
		   else
		   q->g=head_open->next->t->parent->g+1 ;
		   q->f=q->g+m_Target(q->a) ;
		   
	
		   q->parent=head_open->next->t ;
		   add_Headopen(q) ;
	/////////////////////////////////////////////////////
		   /*h1=(struct node1*) malloc(sizeof(struct node1)) ;
	   p1= (struct node *) malloc(sizeof(struct node)) ;
	   h1=head_open->next->next ;
	   p1=h1->t;
	   t1=pipei_Target(p1) ;*/
	   //head_open=head_open->next ;
	   //free(h1) ;
	   //free(p1)  ;
	 

			


		   
		 
	 

	   }
	   /////////// 向上走
	   t=s_Blank(head_open->next->t->a ) ;
	   i=t/3 ;
	   j=t%3 ;
	  if(i-1>=0)
		   {
		  q= (struct node *) malloc(sizeof(struct node)) ;
	//	 struct node *p1 ;
	 //  struct node1 *h1 ;
		  int c[9];
		  for(int i1=0 ;i1<9 ;i1++)
		   {
			   c[i1]=head_open->next->t->a[i1] ;
				   //cout<<c[i1]<<"**";
		   }
		   p=3*(i-1)+j;
		   //cout<<p<<endl ;
//cout<<c[t]<<"--------"<<c[p]<<endl ;
		  c[t]=c[p] ;
		  c[p]=0 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		   for(i=0 ; i<9;i++ )
		   {
		      q->a[i]= c[i] ;
		   }
		   if(head_open->next->t->parent==NULL)
			   q->g=1;
		   else
		   q->g=head_open->next->t->parent->g+1 ;
		   q->f=q->g+m_Target(q->a) ;
		   q->parent=head_open->next->t ;
		   add_Headopen(q) ;
		   	  /* h1=(struct node1*) malloc(sizeof(struct node1)) ;
	   p1= (struct node *) malloc(sizeof(struct node)) ;
	   h1=head_open->next->next ;
	   p1=h1->t;
	   t1=pipei_Target(p1) ;
	   head_open=head_open->next ;*/


	   }
	   //////////////////向右走
        t=s_Blank(head_open->next->t->a ) ;
	   i=t/3 ;
	   j=t%3 ;

	   if(j+1<=2)
		   {
		   q= (struct node *) malloc(sizeof(struct node)) ;
		   //struct node *p1 ;
	       //struct node1 *h1 ;
		   int c[9];
		   for(int i1=0 ;i1<9 ;i1++)
		   {
			   c[i1]=head_open->next->t->a[i1] ;
		   }
		   p=3*i+j+1 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		  c[t]=c[p] ;
		  c[p]=0 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		   for(int i2=0 ; i2<9;i2++ )
		   {
			   
		      q->a[i2]= c[i2] ;
			  ///////////////////////////
		   }
		   if(head_open->next->t->parent==NULL)
			   q->g=1;
		   else
		   q->g=head_open->next->t->parent->g+1 ;
		   q->f=q->g+m_Target(q->a) ;
		   
	
		   q->parent=head_open->next->t ;
		   add_Headopen(q) ;

	   }
	   ////////////////向下走
       t=s_Blank(head_open->next->t->a ) ;
	   i=t/3 ;
	   j=t%3 ;
	   

	   if(i+1<=2)
		   {
		   q= (struct node *) malloc(sizeof(struct node)) ;
		   //struct node *p1 ;
	       //struct node1 *h1 ;
		   int c[9];
		   for(int i1=0 ;i1<9 ;i1++)
		   {
			   c[i1]=head_open->next->t->a[i1] ;
			   //cout<<head_open->next->t->a[i1]<<"_______________________"<<endl ;
		   }
		   p=3*(i+1)+j ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		  c[t]=c[p] ;
		  c[p]=0 ;
		   //cout<<c[t]<<"--------"<<c[p]<<endl ;
		   for(int i2=0 ; i2<9;i2++ )
		   {
			   
		      q->a[i2]= c[i2] ;
			  ///////////////////////////
		   }
		   if(head_open->next->t->parent==NULL)
			   q->g=1;
		   else
		   q->g=head_open->next->t->parent->g+1 ;
		   q->f=q->g+m_Target(q->a) ;
		   
	
		   q->parent=head_open->next->t ;
		   add_Headopen(q) ;

	   }
	   /*h1=(struct node1*) malloc(sizeof(struct node1)) ;
	   p1= (struct node *) malloc(sizeof(struct node)) ;
	   h1=head_open->next ;
	   p1=h1->t;
	   t1=pipei_Target(p1) ;
	   head_open=head_open->next ;*/
	   h1=(struct node1*) malloc(sizeof(struct node1)) ;
	   p1= (struct node *) malloc(sizeof(struct node)) ;
	   h1=head_open->next->next ;
	   p1=h1->t;
	   t1=pipei_Target(p1) ;
	   
	   head_open=head_open->next ;
	   
	   
	 

	   





	   
   }


 /*p=(struct node *) malloc(sizeof(struct node)) ;
 for(i=0 ; i<9;i++ )
	{
		p->a[i]=q->a[i] ;
 }
 p->parent=q ;*/

 


}