我的编程学习日志（14）--八数码问题(代码） |五十风的个人博客

终于把八数码问题解决了，先贴上代码，详解下一篇博文给出

本人测试了一下，应该没有错，如果发现有错欢迎指正

（转载代码请标明出处）

#include<iostream>
using namespace std;
#define LL __int64
#define max 362885
int fact[9]={0,1,2,6,24,120,720,5040,40320};
struct X
{
	int num[9];
};

X begin,goal,state[max];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

int xiabiao[max],temp[max];//记录下标
int thexiabiao=1;
bool vis[max];

int hash(X temp)
{
	int i,j,z,count,no=0;
	int a[9];
	bool f;
	for(i=0;i<9;i++)
	{
		count=0;
		f=true;

		for(j=0;j<9;j++)
		{
			for(z=0;z<=i;z++)
			{
				if(a[z]==j)
				{
					f=false;
					break;
				}
			}
			if(temp.num[i]>j && f==true)
				count++;
			f=true;

		}
		a[i]=temp.num[i];
		no+=count*fact[8-i];
	}
	return no;
}
bool equal(X a,X b)
{
	int i;
	for(i=0;i<9;i++)
	{
		if(a.num[i]!=b.num[i])
			return false;

	}
	return true;

}
int front=0,rear=1;
bool bfs(X first)
{

	int i,t;
	int z,x,y;
	bool f=false;
	for(i=0;i<9;i++)
	{
		if(first.num[i]==0)
			break;
	}
	z=i;
	x=z%3;
	y=z/3;
	int newz,newx,newy;
	X two;
	for(i=0;i<4;i++)
	{
		two=first;
		newx=x+dx[i];
		newy=y+dy[i];
		if(newx>2 || newx<0 || newy>2 || newy<0)
			continue;

		newz=newy*3+newx;
		two.num[newz]=first.num[z];
		two.num[z]=first.num[newz];
		t=hash(two);
		if(vis[t]==0)
		{
			state[rear]=two;
			xiabiao[thexiabiao++]=front;
			rear++;
			vis[t]=1;
			if( equal(two,goal) )
			{
				f=true;
				return 1;
			}
		}
	}
	if(f==false)
	{

			front++;
			bool ff=bfs(state[front]);
			if(ff==1)
				return 1;
		return 0;
	}
}

int main()
{
	xiabiao[0]=-1;
	bool f;
	int i,j;

	for(i=0;i<9;i++)
		scanf("%d",&begin.num[i]);
	for(i=0;i<9;i++)
		scanf("%d",&goal.num[i]);
	vis[hash(begin)]=1;
	state[front]=begin;
	f=bfs(begin);
	if(f)
	{
		j=xiabiao[--thexiabiao];

		for(i=0;j>=0;i++)
		{
			//printf("j%d  ",j);
			temp[i]=j;
			j=xiabiao[j];

		}
		i--;
		while(i>0)
		{
			for(j=0;j<9;j++)
			{
				printf("%d",state[temp[i]].num[j]);
				if((j+1)%3==0)
					printf("\n");
			}
			i--;
			printf("\n");

		}
	}
	else
		printf("no\n");

	return 0;

}