move8.c

解决九宫重排问题的原代码,代码非常简洁,演示也很清晰,比如输入初始排局(0表示空位) row0 : 123 row1 : 408 row2 : 675 程序就能很快自动算出到目标排局的演变过程

 #define len sizeof(POINT)
 #define nil 0
 #define MAX 200
 #define STOK 150
 #include <stdio.h>
 #include <stdlib.h>
 typedef struct PT{ char a[3][3];
	    char blkx,blky;
	    char drc;
	    int score;
	    unsigned l;
	    struct PT *pretre;
	    struct PT *next;
	  } POINT;
 typedef struct { int r,c;}STU;
 int directx[4]={1,0,-1,0},
     directy[4]={0,-1,0,1};
 char b[3][3]={{1,2,3},{8,0,4},{7,6,5}};
 char pt[3][3]={{7,6,4},{3,0,2},{5,8,1}};
 STU next[3][3]={ {{0,1},{0,2},{1,2}},
		  {{0,0},{0,0},{2,2}},
		  {{1,0},{2,0},{2,1}} };
 STU num[9]={{0,0},{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}};
 POINT *head,*h,*path[45];
 int consult(POINT *pp);
 char lm;
 int stop;
 char watch;
 void mvtree(POINT *point);
 void move(char (*pt)[3]);
 void print(POINT *pp);
 int (*fun)();
 void blk(POINT *pp)
  { int i,j;
    for(i=0;i<3;i++)
     for(j=0;j<3;j++)
      if(pp->a[i][j]==0){pp->blkx=j;pp->blky=i;break;}
  }
 int order(POINT *pp)
  { int i,j,tmr,tmc;
    int val,count=0;
    for(i=0;i<3;i++)
     for(j=0;j<3;j++)
      { val=pp->a[i][j];
	    if(i==1&&j==1){ if(val!=0)count++;}
	     else if(val!=0)
		        { tmr=next[i][j].r;tmc=next[i][j].c;
		    	  if(pp->a[tmr][tmc]!=val%8+1)count+=2;
		        }
      }
    return(count);
  }
 int distance(POINT *pp)
  { int i,j,val,count=0;
    for(i=0;i<3;i++)
     for(j=0;j<3;j++)
      { val=pp->a[i][j];
	if(val)count+=abs(i-num[val].r)+abs(j-num[val].c);}
    return(count);
  }
 int total(POINT *pp)
  { return(distance(pp)+3*(order(pp)));}
 int consult(POINT *pp)
  {char i,j;int count=0;
   for(i=0;i<3;i++)
    for(j=0;j<3;j++)
     if(pp->a[i][j]!=0&&pp->a[i][j]!=b[i][j])count++;
   return(count);
  }
 void print(point)
  POINT *point;
  {char i,j;
   for(i=0;i<3;i++)
    {for(j=0;j<3;j++)
      {char x=point->a[i][j];
       if(x)printf("%d ",x);
	else printf("  ");}
     printf("\n");
    }
   printf(": %d = %d + %d\n",point->score,fun(point),point->l);
  }
 void waring()
  { printf("\nOut of memory!\n");}
 int comp(POINT *p1,POINT *p2)
  { int i,j;
    for(i=0;i<3;i++)
     for(j=0;j<3;j++)
      if(p1->a[i][j]!=p2->a[i][j])return(1);
    return(0);
  }
 void mvtree(point)
  POINT *point;
  {int bx=point->blkx,by=point->blky,l=point->l;
   char pdrc=point->drc;
   int i,k,j;
   for(i=0;i<4;i++)
    {int tmpx,tmpy;
     POINT *q,*p,*p1;
     if(bx==2&&i==0)continue;
     if(bx==0&&i==2)continue;
     if(by==0&&i==1)continue;
     if(by==2&&i==3)continue;
     if(point->l!=0)
      if((i-pdrc+4)%2==0&&i!=pdrc)continue;
     tmpx=bx+directx[i];tmpy=by+directy[i];
      p1=(POINT *)malloc(sizeof(POINT));
      if(p1==nil){stop=1;waring();return;}
      for(k=0;k<3;k++)
       for(j=0;j<3;j++)
	  p1->a[k][j]=point->a[k][j];
      p1->a[by][bx]=p1->a[tmpy][tmpx];p1->a[tmpy][tmpx]=0;
      p1->l=l+1;p1->score=fun(p1)+p1->l;p1->drc=i;
      p1->blkx=tmpx;p1->blky=tmpy;
      p=head->next;q=head;
      while(p!=h)
       { if(comp(p,p1)==0){free(p1);break;}
	      else q=p;p=p->next;
       }
      if(p!=h)continue;
      q=h;p=h->next;
      while(p!=nil&&p1->score>=p->score&&comp(p,p1))
       {q=p;p=p->next;}
      
      if(p!=nil&&comp(p,p1)==0){ free(p1);continue;}
       else
	   {  q->next=p1;p1->next=p;p1->pretre=point;
	      q=p1;

	      while(p!=nil&&comp(p,p1))
	       {q=p;p=p->next;}
	      if(p!=nil&&comp(p,p1)==0)
	       {q->next=p->next;free(p);}
	   }
    }
  }
 void move(pt)
  char (*pt)[3];
  {POINT *p;char i,j;
   head=(POINT*)malloc(sizeof(POINT));
   h=(POINT*)malloc(sizeof(POINT));
   head->next=h;h->next=nil;
   for(i=0;i<3;i++)
    for(j=0;j<3;j++)
     h->a[i][j]=pt[i][j];
   blk(h);
   h->score=fun(h);h->l=0;
   while(h->score!=h->l)
    {
     if(watch=='y'){ print(h);
		printf("Press y to continue watch and other key to end\n");
		watch=getch();}
     mvtree(h);
     if(stop==1)return;
     h=h->next;
    }
   p=h;lm=p->l;
   for(i=lm;i>=0;i--)
    {path[i]=p;p=p->pretre;}
  }
 void main()
  {char ch;
   int i,j;
   POINT *p,*q;

do{stop=0;
   printf("\n");
   for(i=0;i<3;i++)
     { printf("row %d : ",i);
       scanf("%s",pt+i);
       for(j=0;j<3;j++)
	pt[i][j]-='0';
     }
   printf("What value function(t d p o): ");
   ch=getch();
   switch(ch) { case 'p':fun=consult;break;
		case 'd':fun=distance;break;
		case 'o':fun=order;break;
		default:fun=total;
	      }
   printf("\nWatch search?(y n)\n");
   watch=getch();
   move(pt);
   if(stop==0)
     { printf("\nresult->\n");
       for(i=0;i<=lm;i++)
	{print(path[i]);
	 getch();
	}
     }
   p=head->next;
   while(p!=nil)
    { q=p;p=p->next;free(q);}
   printf("\nYou can select 1(Again)  0(End) ");
   scanf("%d",&i);
  } while(i!=0);

   free(head);
  }