人工知能:(C言語)状態空間法を用いて八デジタル問題を解く

実験要求:八数コードの難題は九宮問題とも呼ばれ、それは3×3の四角い碁盤には、表1、2、3、4、5、6、7、8の8枚の札がそれぞれ置かれています.初期状態S 0、目標状態Sgは、プログラムが任意の初期状態と目標状態を入力できるように要求され、8枚の札をスペースで移動して碁盤が初期状態から目標状態に達するように要求されています.**移動ルール:**は、スペース(上下左右)に隣接する1つの数字のみをスペースに平行移動できます.実験では、広さ優先検索ポリシーを適用して、初期状態からターゲット状態への解のパスを探すことが求められ、プログラミング言語はCシリーズ言語です.
完全なコードは次のとおりです.

#include
struct node
{
     
 int a[3][3];
 int u;
 int d;
 int l;
 int r;
 int p;
};
int judge();
void search();
void up();
void down();
void left();
void right();
void output();
//typedef 
node np[400000];
int target[3][3];
int f,r,zero_i,zero_j;
int x[100],y[100]; 
int main()
{
     
 f=0;
 r=0;
 int i,j,n;
 printf("       ：
");
 n=0;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   scanf("%d",&np[0].a[i][j]);
   if(np[0].a[i][j]!=0) x[n++]=np[0].a[i][j];
  }
 }
 np[0].p=-1;
 printf("       ：
");
 n=0;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   scanf("%d",&target[i][j]);
   if(target[i][j]!=0) y[n++]=target[i][j];
  }
 }
 
 if(judge()==1)
 {
     
  search();
 }
 else printf("               
");
 return 0;
}
int judge()
{
     
 int sum1=0,sum2=0,i,j;
 for(i=1;i<8;i++)
 {
     
  for(j=0;j<i;j++)
  {
     
   if(x[i]>x[j]) sum1++;
   if(y[i]>y[j]) sum2++;
  }
 }
 if((sum1%2)==(sum2%2)) return 1;
 else return 0;
}
void search()
{
     
 int i,j,temp;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   if(np[f].a[i][j]!=target[i][j]) break;
  }
  if(j<3) break;
 }
 if(i>=3&&j>=3) output(); 
 else
 {
     
 // printf("111
");
  for(zero_i=0;zero_i<3;zero_i++)
  {
     
   for(zero_j=0;zero_j<3;zero_j++)
   {
     
    if(np[f].a[zero_i][zero_j]==0)  break;
   }
   if(zero_j<3) break;
  }
  
  if(zero_i!=0) up();
  if(zero_i!=2) down();
  if(zero_j!=0) left();
  if(zero_j!=2) right();
  
  f++;
  search();
 }
}
void up()
{
     
 int i,j; 
 r++;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   if((i==zero_i&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i-1][j];
   else if((i==zero_i-1&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i][j];
   else np[r].a[i][j]=np[f].a[i][j];
  }
 }
 np[r].p=f;
 np[f].u=r;
}
void down()
{
     
 int i,j; 
 r++;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   if((i==zero_i&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i+1][j];
   else if((i==zero_i+1&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i][j];
   else np[r].a[i][j]=np[f].a[i][j];
  }
 }
 np[r].p=f;
 np[f].d=r;
}
void left()
{
     
 int i,j; 
 r++;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   if((i==zero_i&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i][zero_j-1];
   else if((i==zero_i&&j==zero_j-1)) np[r].a[i][j]=np[f].a[zero_i][zero_j];
   else np[r].a[i][j]=np[f].a[i][j];
  }
 }
 np[r].p=f;
 np[f].l=r;
}
void right()
{
     
 int i,j; 
 r++;
 for(i=0;i<3;i++)
 {
     
  for(j=0;j<3;j++)
  {
     
   if((i==zero_i&&j==zero_j)) np[r].a[i][j]=np[f].a[zero_i][zero_j+1];
   else if((i==zero_i&&j==zero_j+1)) np[r].a[i][j]=np[f].a[zero_i][zero_j];
   else np[r].a[i][j]=np[f].a[i][j];
  }
 }
 np[r].p=f;
 np[f].r=r;
}
void output()
{
     
 int i,j,n,m,temp,b[1000];
 char ch[1000];
 n=f;
 m=0;
 b[m]=f;
 while(np[n].p!=-1)
 {
     
  //b[m+1]=np[n].p;
  temp=n;
  n=np[n].p;
  if(np[n].u==temp) ch[m]='U';
  if(np[n].d==temp) ch[m]='D';
  if(np[n].l==temp) ch[m]='L';
  if(np[n].r==temp) ch[m]='R';
  m++;
  b[m]=np[temp].p;
 }
 m--;
 for(i=0;i<3;i++)
 {
     
  printf("      ");
  for(j=0;j<3;j++) printf("%d ",np[0].a[i][j]);
  printf("
");
 }
 printf("
");
 while(m>=0)
 {
     
  printf("%c     ",ch[m]);
  for(i=0;i<3;i++)
  {
     
   
   for(j=0;j<3;j++) printf("%d ",np[b[m]].a[i][j]);
   printf("
");
   printf("      ");
  }
  printf("
");
  m--;
 }
}