888.cpp

人工智能的8数码问题的求解

# include <iostream.h>
#include <stdio.h>
typedef struct
{ char num;
  int flag;
}SZ;


void  printnum(SZ N[][5])//打印矩阵
{ int a,b;
  cout<<"-------------------------------------------------"<<endl;
	for(a=1; a<4; a++)
		for(b=1;b<4;b++)
		{printf(" %c ",N[a][b].num);
		 if(b==3)printf("\n");
		}
}

int compare(SZ N[][5],SZ M[][5])//求位置不正确的位置个数
{ int i,j,wrong=0;
    for(i=1; i<4; i++)
		for(j=1;j<4;j++)
		 if(N[i][j].num!=M[i][j].num)wrong++;
  return wrong;
}
   

void left(SZ N[][5])//空格左移
{ 
	int i,j,a,b;
    char tmp;
	for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){a=i;b=j;}
		 tmp=N[a][b].num;
	     N[a][b].num=N[a][b-1].num;
         N[a][b-1].num=tmp;
         N[a][b].flag=0;
}

void right(SZ N[][5])//空格右移
{ 
	int i,j,a,b;
    char tmp;
	for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){a=i;b=j;}
		 tmp=N[a][b].num;
	     N[a][b].num=N[a][b+1].num;
         N[a][b+1].num=tmp;
		N[a][b].flag=0;
}

void up(SZ N[][5])//空格上移
{ 
	int i,j,a,b;
    char tmp;
	for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){a=i;b=j;}
			tmp=N[a][b].num;
	     N[a][b].num=N[a-1][b].num;
         N[a-1][b].num=tmp;
        N[a][b].flag=0;
}

void down(SZ N[][5])//空格下移
{ 
	int i,j,a,b;
    char tmp;
	for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){a=i;b=j;}
			tmp=N[a][b].num;
	     N[a][b].num=N[a+1][b].num;
         N[a+1][b].num=tmp;
         N[a][b].flag=0;
}


int choose(SZ N1[][5],SZ N2[][5],SZ M[][5])//两矩阵不正确数字相同且为最小时，通过可能的下一步来决定
{SZ temp1[5][5],temp2[5][5],temp3[5][5],temp4[5][5];
   int tmp1,tmp2,tmp3,tmp4;
   int i,j,a,b,min1,min2;
    tmp1=tmp2=tmp3=tmp4=100;
  for(i=0;i<5;i++)
	  for(j=0;j<5;j++)
	  {temp1[i][j]=N1[i][j];
	      temp2[i][j]=N1[i][j];
		  temp3[i][j]=N1[i][j];
		  temp4[i][j]=N1[i][j];}
      for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N1[i][j].num=='E'){a=i;b=j;}

	  if(temp1[a][b-1].flag){ left(temp1);  tmp1=compare(temp1,M);}
      if(temp2[a][b+1].flag){ right(temp2); tmp2=compare(temp2,M);}
	  if(temp3[a-1][b].flag){ up(temp3);    tmp3=compare(temp3,M);}
      if(temp4[a+1][b].flag){ down(temp4);  tmp4=compare(temp4,M);}

     if(tmp1<=tmp2&&tmp1<=tmp3&&tmp1<=tmp4) min1=tmp1; 
     if(tmp2<=tmp1&&tmp2<=tmp3&&tmp2<=tmp4) min1=tmp2;
     if(tmp3<=tmp1&&tmp3<=tmp2&&tmp3<=tmp4) min1=tmp3;
     if(tmp4<=tmp1&&tmp4<=tmp3&&tmp4<=tmp2) min1=tmp4;
	 /////////////////////////////////////////////////// 
     tmp1=tmp2=tmp3=tmp4=100;
  for(i=0;i<5;i++)
	  for(j=0;j<5;j++)
	  {temp1[i][j]=N2[i][j];
	      temp2[i][j]=N2[i][j];
		  temp3[i][j]=N2[i][j];
		  temp4[i][j]=N2[i][j];}

      for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N1[i][j].num=='E'){a=i;b=j;}
	   if(temp1[a][b-1].flag){ left(temp1); tmp1=compare(temp1,M);}
       if(temp2[a][b+1].flag){ right(temp2); tmp2=compare(temp2,M);}
	  if(temp3[a-1][b].flag){ up(temp3); tmp3=compare(temp3,M);}
      if(temp4[a+1][b].flag){ down(temp4); tmp4=compare(temp4,M);}

     if(tmp1<=tmp2&&tmp1<=tmp3&&tmp1<=tmp4)min2=tmp1; 
     if(tmp2<=tmp1&&tmp2<=tmp3&&tmp2<=tmp4) min2=tmp2;
     if(tmp3<=tmp1&&tmp3<=tmp2&&tmp3<=tmp4) min2=tmp3;
     if(tmp4<=tmp1&&tmp4<=tmp3&&tmp4<=tmp2) min2=tmp4;
   if(min1<=min2)return 1;
   else return  2;

}
 
 
int decide(SZ N[][5],SZ M[][5],int *L,int *R,int *U, int *D)//决定空格的移动方向
{ SZ temp1[5][5],temp2[5][5],temp3[5][5],temp4[5][5];
   int tmp1,tmp2,tmp3,tmp4;
int i,j,a,b;
 *L=*R=*U=*D=0;
 tmp1=tmp2=tmp3=tmp4=100;
  for(i=0;i<5;i++)
	  for(j=0;j<5;j++)
	  {temp1[i][j]=N[i][j];
	      temp2[i][j]=N[i][j];
		  temp3[i][j]=N[i][j];
		  temp4[i][j]=N[i][j];}
      for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){a=i;b=j;}
	   if(temp1[a][b-1].flag){ left(temp1); tmp1=compare(temp1,M);}
       if(temp2[a][b+1].flag){ right(temp2); tmp2=compare(temp2,M);}
	  if(temp3[a-1][b].flag){ up(temp3); tmp3=compare(temp3,M);}
      if(temp4[a+1][b].flag){ down(temp4); tmp4=compare(temp4,M);}
	  if(temp1[a][b-1].flag==0&& temp2[a][b+1].flag==0&&temp3[a-1][b].flag==0&&temp4[a+1][b].flag==0)
	  {cout<<"不能移动"<<endl; return 1;}

	  if(temp1[a][b-1].flag&&(tmp1<=tmp2)&&(tmp1<=tmp3)&&(tmp1<=tmp4))*L=1; 
     if(temp1[a][b+1].flag&&tmp2<=tmp1&&tmp2<=tmp3&&tmp2<=tmp4) *R=1;
     if(temp1[a-1][b].flag&&tmp3<=tmp1&&tmp3<=tmp2&&tmp3<=tmp4) *U=1;
     if(temp1[a+1][b].flag&&tmp4<=tmp1&&tmp4<=tmp3&&tmp4<=tmp2)  *D=1;
     
	 if(*L==1)
	 { if(*R==1){ if(choose(temp1,temp2,M)==1)*R=0;
	              else *L=0;}
	   if(*U==1){ if(choose(temp1,temp3,M)==1)*U=0;
	              else *L=0;}
       if(*D==1){ if(choose(temp1,temp4,M)==1)*D=0;
	              else *L=0;}
	 }
     if(*R==1)
	 { if(*U==1){ if(choose(temp2,temp3,M)==1)*U=0;
	              else *R=0;}
	   if(*D==1){ if(choose(temp2,temp4,M)==1)*D=0;
	              else *R=0;}
	 }
	 if(*U==1)
	 {if(*D==1){ if(choose(temp3,temp4,M)==1)*D=0;
	              else *U=0;}
	 }
      if(*L==1) return tmp1;
      if(*R==1) return tmp2;
      if(*U==1) return  tmp3;
      else   return tmp4;

}

//////////////////////////////////////////////////////////////////////
int count=-2;
int  research(SZ N[][5], SZ M[][5],int c, int d,int e,int f,int g,int h,int wrong)
{ int i,j,L,R,U,D;
   SZ temp1[5][5],temp2[5][5],temp3[5][5],temp4[5][5];
   int vaule,move;
    count++;
    if(count)N[c][d].flag=1;
	c=e;d=f;
	e=g;f=h;
    for(i=1; i<4; i++)
		for(j=1;j<4;j++)
			if(N[i][j].num=='E'){g=i;h=j;}

   vaule=compare(N,M);
   if(vaule==0) return 0;
   move=decide(N,M,&L,&R,&U,&D);
   if(vaule > move)wrong=move;
   if((vaule-wrong)>2) return 1; //情况恶化时返回 
	if(vaule)
	{ for(i=0;i<5;i++)
	  for(j=0;j<5;j++)
	  {temp1[i][j]=N[i][j];
	      temp2[i][j]=N[i][j];
		  temp3[i][j]=N[i][j];
		  temp4[i][j]=N[i][j];}	
	printnum(N);
 //////////////////////////////////      
		if(L==1)
		{left(temp1);
		 if(research(temp1,M,c,d,e,f,g,h,wrong)==0){cout<<"◆↑向左走一步"<<endl;return 0;}
		 else return 1;
		 
        }
///////////////////////////////
        if(R==1)
		{right(temp1);
		 if(research(temp1,M,c,d,e,f,g,h,wrong)==0){cout<<"◆↑向右走一步"<<endl;return 0;}
		 else return 1;
		}
		//////////////////////////////////
        if(U==1)
		{up(temp1);
		if(research(temp1,M,c,d,e,f,g,h,wrong)==0)
		{cout<<"◆↑向上走一步"<<endl;return 0;}
         else return 1;
		}
		////////////////////////////////
		if(D==1){down(temp4);
		       if(research(temp4,M,c,d,e,f,g,h,wrong)==0)
			   {cout<<"◆↑向下走一步"<<endl;return 0;}
		else return 1;}
      }
	return 1;
}

    

void main()
{ SZ N[5][5], M[5][5];
	int i,j,ture=1;
  for(i=0;i<5;i++)
	  for(j=0;j<5;j++)
		  N[i][j].flag=0,M[i][j].flag=0;
	  cout<<"------------------八数码问题的搜索-----------------\n";
	  cout<<"请输入初始数字，空格用大写字母'E'表示:"<<endl;
   for(i=1;i<4;i++)
	   for(j=1;j<4;j++)
	   {printf("N[%d][%d]:",i,j);
		   cin>>N[i][j].num; N[i][j].flag=1;	   
	   }
	  
  cout<<"请输入目的数字，空格用用大写字母'E'表示:"<<endl;
   for(i=1;i<4;i++)
	   for(j=1;j<4;j++)
	   {printf("M[%d][%d]:",i,j);
	   cin>>M[i][j].num;N[i][j].flag=1;}
      
	   ture=research(N,M,0,0,0,0,0,0,9);
        
	   if(ture==0){cout<<"(注：空格移动的步骤为由下到上)"<< "     成功了，可以找到！  "<<endl;
	               printnum(M);
				   }
	  if(ture==1) cout<<" 不好意思，好像不行。换一组数试试。"<<endl;
	   
    
}