text.c

八数码!很不错的!请你解压后使用! 如果不行的话,请重新传下载!

/*用广度优先搜索*/
#include<stdio.h>
#include<conio.h>
#include<windows.h>

int n,m=0;
int success=0;
typedef struct Node
{
int matrix[9];/*存储矩阵*/
char operate;/*存储不可以进行的操作，N代表没有不可以进行的操作，L代表不能左移,R代表不能右移,U代表不能上移,D代表不能下移*/
char extend;/*是否可以扩展，Y代表可以，N代表不可以*/
int father;/*指向产生自身的父结点*/
}Node;
Node base[4000];

int start[10];
int end[10];    /*最终目标*/
int result[100];/*存放结果的base数组下标号，逆序存放*/

int match()/*判断是否为目标*/
{
   int i;
   for(i=0;i<9;i++)
   {
    if(base[n-1].matrix[i]!=end[i])
	{
       return 0;
	}
   }
   return 1;
}

void show()/*显示矩阵的内容*/
{
   int i=1;
	int mm=0;
   while(m>=0)
   {
      mm=result[m];
 
      printf("\n\n\n\n\n\t\t\t%d\t%d\t%d\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);
      printf("\n\n\t\t\t%d\t%d\t%d\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);
      printf("\n\n\t\t\t%d\t%d\t%d\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);

      m--;
      i++;
   }
}

void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/
{
   n--;
  while(base[n].father!=-1)
  {
    result[m]=n;
    m++;
    n=base[n].father;
  }
   result[m]=0;
   //result[m+1]='\0';
  show();

  printf("\n\n\n\n\n\n\n\n\n\t\t\t\tThe End\n\n\n\n\n\n\n\n\n\n");
  success=1;
  //getch();
  exit(0);
}

int left(int x)/*把下标为X的数组中的矩阵的空格左移*/
{
    int i,j;
    int ch;
    for(i=0;i<9;i++)
	{
       if(base[x].matrix[i]==0)
       break;
	}
    if(i==0||i==3||i==6||i==9)
	{
       return 0;
	}
	for(j=0;i<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}

   ch=base[n].matrix[i-1];
   base[n].matrix[i-1]=base[n].matrix[i];
   base[n].matrix[i]=ch;
   base[n].operate='R';
   base[n].extend='Y';
   base[n].father=x;

   base[x].extend='N';
 
   if(match()==1)
	   leave();
	   
   return 1;
}


int right(int x)/*把下标为X的数组中的矩阵的空格右移*/
{
   int i,j;
   int ch;
   for(i=0;i<9;i++)
   {
      if(base[x].matrix[i]==0)
      break;
   }
   if(i==2||i==5||i==8||i==9)
   {
      return 0;
   }
   for(j=0;i<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}

   ch=base[n].matrix[i+1];
   base[n].matrix[i+1]=base[n].matrix[i];
   base[n].matrix[i]=ch;
   base[n].operate='L';
   base[n].extend='Y';
   base[n].father=x;

   base[x].extend='N';

   if(match()==1)
          leave();
   return 1;
}

int up(int x)/*把下标为X的数组中的矩阵的空格上移*/
{
   int i,j;
   int ch;
   for(i=0;i<9;i++)
   {
     if(base[x].matrix[i]==0)
           break;
   }
   if(i==0||i==1||i==2||i==9)
   {
      return 0;
   }
   for(j=0;i<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}

   ch=base[n].matrix[i-3];
   base[n].matrix[i-3]=base[n].matrix[i];
   base[n].matrix[i]=ch;
   base[n].operate='D';
   base[n].extend='Y';
   base[n].father=x;

   base[x].extend='N';

   if(match()==1)
         leave();
   return 1;
}

int down(int x)/*把下标为X的数组中的矩阵的空格下移*/
{
   int i,j;
   int  ch;
   for(i=0;i<9;i++)
   {
       if(base[x].matrix==0)
          break;
   }
   if(i==6||i==7||i==8||i==9)
   {
      return 0;
   }

    for(j=0;i<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}

    ch=base[n].matrix[i+3];
    base[n].matrix[i+3]=base[n].matrix[i];
    base[n].matrix[i]=ch;
    base[n].operate='U';
    base[n].extend='Y';
    base[n].father=x;

    base[x].extend='N';
  
    if(match()==1)
        leave();
    return 1;
}

void search(int k)
{
    if(base[k].extend=='Y')
	{
		if(base[k].operate=='L')
		{
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(right(k)==1)
				  search(k+1);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(up(k)==1)
				  search(k+1);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(down(k)==1);
				  search(k+1);
			}
		        
			
		}
		if(base[k].operate=='R')
		{
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(left(k)==1)
				   search(k);
			}
		    if(success!=1&&k<4000)
			{
				n=k+1;
				if(up(k)==1)
				   search(k+1);
			}
		    if(success!=1&&k<4000)
			{
				n=k+1;
				if(down(k)==1)
				   search(k+1);
			}
		}
		if(base[k].operate=='U')
		{
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(left(k)==1)
				   search(k);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(right(k)==1)
				   search(k+1);
			}
		
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(down(k)==1)
				   search(k+1);
			}
			
		}
		if(base[k].operate=='D')
		{
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(left(k)==1)
				   search(k);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(right(k)==1)
				   search(k+1);
			}
		    if(success!=1&&k<4000)
			{
				n=k+1;
				if(up(k)==1)
				  search(k+1);
			}
		}
		if(base[k].operate=='N')
		{
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(left(k)==1)
				  search(k);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(right(k)==1)
				  search(k+1);
			}
		    if(success!=1&&k<4000)
			{
				n=k+1;
				if(up(k)==1)
				   search(k+1);
			}
			if(success!=1&&k<4000)
			{
				n=k+1;
				if(down(k)==1)
				  search(k+1);
			}
		}
	}
}


main()
{
   int i;
   int a[9],b[9];
   n=1;

/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/
   printf("Please input the start 9 chars:");
   for(i=0;i<9;i++)
   {
	   scanf("%d",&a[i]);
   }
   printf("\nPlease input the end 9 chars:");
   for(i=0;i<9;i++)
   {
	   scanf("%d",&b[i]);
   }
   for(i=0;i<9;i++)
   {
      start[i]=a[i];
      end[i]=b[i];
   }


   for(i=0;i<9;i++)    /*是为第一个base数组元素赋值*/
   {
      base[0].matrix[i]=start[i];
   }
   base[0].operate='N';
   base[0].extend='Y';
   base[0].father=-1;

   search(0);
}