8shuma.cpp

解决8数码难题 呵呵 不错的算法哦 欢迎大家使用 有错误与我联系QQ 26267004

#include <stdio.h>
void readdata();
int search();
int emptyopen();
long takeoutofopen();
int canmoveto(int,int,int *,int*,int);
int isaim(long);
int used(long);
void addtoopen(long);
int a[100][9],b[20][20],c[9];
long change(int a[]);
long n=3,length,xin=1,result;
void init();
int open[100],head,tail,openlen=100;
long jiechen(int);
void main()
{
	long number;
	readdata();
	init();
	number=search();
	printf("%ld",number);
}
int search()
{
	int row,col,i,j=0,bushu,r,c;
	long u,num,num1;
	while(!emptyopen())
	{
	   u=takeoutofopen();
	   for(num=0;num<length;num++)
	   {
		   if(change(a[num])==u)
			   break;
	   }
	   for(num1=0;num1<9;num1++)
	   {
		   if(a[num][num1]==9)
		   {
			   break;
		   }
	   }
       row=num1/n;
	   col=num1%n;
	   bushu=b[row][col];
	   for(i=0;i<4;i++)
	   {
		   if(canmoveto(row,col,&r,&c,i))
		   {
			   if(isaim(change(a[xin-1])))
			   {
				   return(num+1);
			   }
			   if(!used(change(a[xin-1])))
			   {
				   b[r][c]=num+1;
				   addtoopen(change(a[xin-1]));
			   }
		   }
	   }
	  }
	return 0;
}
int emptyopen()
{
	if(head==tail)
	{
		return(1);
	}
	else
	{
		return 0;
	}
}
long takeoutofopen()
{
	long u;
	if(head==tail)
	{
		printf("Error:stack is empty\n");
		return -1;
	}
	u=open[head++];
	head=head%openlen;
	return u;
}
int canmoveto(int row,int col,int*p,int*q,int direction)
{
	int r,c,i;
	r=row;
	c=col;
	switch(direction)
	{
	case 0:c--;
		   if(c<0)
		   {
			   return 0;
		   }
		   *p=r;
		   *q=c;
		   for(i=0;i<n*n;i++)
		   {
              a[xin][i]=a[xin-1][i];
		   }
		   a[xin][col]=a[xin-1][c];
		   a[xin][c]=a[xin-1][col];
		   xin++;
		  return 1;
    case 1:r++;
		   if(r>=n)
		   {
			   return 0;
		   }
		   *p=r;
		   *q=c;
           for(i=0;i<n*n;i++)
		   {
              a[xin][i]=a[xin-1][i];
		   }
		   a[xin][row]=a[row-1][r];
		   a[xin][r]=a[xin-1][row];
		   xin++;
		  return 1;
    case 2:c++;
		   if(c>=n)
		   {
			   return 0;
		   }
		   *p=r;
		   *q=c;
           for(i=0;i<n*n;i++)
		   {
              a[xin][i]=a[xin-1][i];
		   }
		   a[xin][col]=a[xin-1][c];
		   a[xin][c]=a[xin-1][col];
		   xin++;
		  return 1;
    case 3:r--;
		   if(r<0)
		   {
			   return 0;
		   }
		   *p=r;
		   *q=c;
           for(i=0;i<n*n;i++)
		   {
              a[xin][i]=a[xin-1][i];
		   }
		   a[xin][row]=a[row-1][r];
		   a[xin][r]=a[xin-1][row];
		   xin++;
		 return 1;
	}
	return 0;
}
int isaim(long result1)
{
	if(result1==result)
	{
		return 1;
	}
	else 
	{
		return 0;
	}
}
int used(long use)
{
	long i;
	for(i=0;i<length;i++)
	{
		if(use==open[length])
		{
			return 1;
		}
	}
	return 0;
}
void addtoopen(long data)
{
	open[tail++]=data;
	tail=tail%openlen;
	length++;
}
void readdata()
{
	int i;
	printf("请输入初始状态\n");
	for(i=0;i<n*n;i++)
	{
		scanf("%d",&a[0][i]);
	}
	printf("请输入最终状态\n");
	for(i=0;i<n*n;i++)
	{
	   scanf("%d",&c[i]);
	}
}
void init()
{
	int s;
	result=change(c);
	s=change(a[0]);
	head=0;
	tail=1;
	open[0]=s;
}
long change(int d[])
{
	long u=0;
	int i,j,e[9]={0};
  for(i=0;i<n*n-1;i++)
  {
     for(j=1;j<n*n;j++)
	 {
		 if(d[j]<d[i])
		 {
			e[i]++;
		 }
	 }
  }
  for(i=0;i<n*n-1;i++)
  {
    u+=e[i]*(jiechen(n*n-1-i));
  }
  return u;
}
long jiechen(int k)
{
	if(k==0||k==1)
	{
		return 1;
	}
	else
	{
		return(jiechen(k-1)*k);
	}
}