八数码问题
问题地址：http://wenku.baidu.com/view/d18a5a0e7cd184254b353598.html我用的算法是：cantor（康托展开）+ BFS 有几个问题： 我的数组不能开到10W+ 而八数码问题有362880种状态
结果打出-1
代码：
#include <stdio.h>
#include <stdlib.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int fac[]={1,1,2,6,24,120,720,5040,40320};
int visit[50000];
int dis[50000];
int cantor(int tail,int state[50000][9])//寻找状态
{
int i,j,t,sum=0;
for(i=0;i<9;i++)
{
t=0;
for (j=i+1;j<9;j++)
if(state[tail][j]<state[tail][i])
t++;
sum+=t*fac[9-i-1];
}
if(visit[sum]==1) return 0;
visit[sum]=1;
return 1;
}
int check(int now[],int goal[])//判断该状态是否为目标状态
{
int i,flag=1;
for(i=0;i<9;i++)
if(goal[i]!=now[i])
flag=0;
return flag;
}
int judge(int x,int y)//判断是否越位
{
if(x>=0&&x<3&&y>=0&&y<3)
return 1;
return 0;
}
int bfs(int state[50000][9],int goal[])
{
int head=0,tail=1,temp,x,y,pos,xx,yy,position,i,j;
int now[9];
while(head<tail)
{
for(i=0;i<9;i++)
now[i]=state[head][i];
if(check(now,goal)==1)//如果达到目标状态
{
printf("%d\n",dis[head]);
return 0;
}
//for(i=0;i<9;i++)
//printf("%d ",state[head][i]);
//printf("\n");
head++;
for(i=0;i<9;i++)//获得0的位置
if(now[i]==0)
break;
x=i/3;y=i%3;//记录坐标x，坐标y
pos=i;//记录位置
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
position=xx*3+yy;
if(judge(xx,yy)==1&&cantor(tail-1,state)==1)//判断走的路是否越位，或该状态是否在表里
{
temp=now[pos];now[pos]=now[yy];now[yy]=temp;//交换位置
for(j=0;j<9;j++) state[tail][j]=now[j];
tail++;
dis[tail]=dis[head]+1;
}
}
}
printf("-1\n");
return 0;
}
int main()
{
int i,goal[9];
int state[50000][9];
for(i=0;i<9;i++)
scanf("%d",&state[0][i]);
for(i=0;i<9;i++)
scanf("%d",&goal[i]);
bfs(state,goal);
system("pause");
return 0;
}
/*
2 8 3
1 0 4
7 6 5
1 2 3
8 0 4
7 6 5
输出：
4
*/
[ 本帖最后由 sunyh1999 于 2011-5-21 11:04 编辑 ]
