八数码问题详解（用bfs实现）注:下面要介绍的方法是LRJ大神首创的，笔者只是在巨人的肩膀上归纳总结了一下，有错误的还希望众大牛指点，本人定将不胜感激。
八数码问题也称为九宫问题。
在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。
棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。
棋子移动后，状态就会发生改变。
解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
如图：对这道题用bfs解决个人认为是个不错的方法，首先因为它有九个格子，那么便可以用state 数组记录他的的九个格子的数值，其中空格为0，后者由于它只有九个数，因此共有9！=362880种可能性，用bfs解决较快。
下面给出bfs实现的三种代码(这里的三种指的是对是否访问过已知节点的三种判断方法): 1.//用一套排列的编码和解码函数解决同一状态的再次访问//用统一的编码与解码函数避免同种状态的再次出现#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define len 362888 //状态共有362880种，数组稍微开大点#define le 9 //每种状态有9个数据,也可看为每种状态下又有9种状态typedefint state[le]; //状态：表示九个格子state st[len],goal; //st为状态数组goal为目标数组int dis[len],fact[le],head[len],vis[len],der[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //dis为每种状态的已走的步骤//der为方向:上，下，左，右void encode(){ //编码int i;for(i=fact[0]=1;i<le;i++)fact[i]=fact[i-1]*i;}int decode(int s){ //解码inti,j,code,cnt;for(i=code=0;i<le;i++){for(cnt=0,j=i+1;j<le;j++)if(st[s][i]>st[s][j])cnt++;code+=cnt*fact[8-i];}if(vis[code]) return 0;else return vis[code]=1;}intbfs(){int front=1,rear=2,i,x,y,z,nx,ny,nz;encode();while(front<rear){state& s=st[front];if(memcmp(s,goal,sizeof(s))==0) //对front状态和目标状态进行比较return front;for(i=0;i<le;i++) //找到为0的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,...8这样的数据，0作为判断依据简单于用数据作为判断依据if(s[i]==0)break;x=i/3; y=i%3; z=i; //记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0;i<4;i++){ //按照上，下，左，右四个方向进行搜索nx=x+der[i][0];ny=y+der[i][1];nz=nx*3+ny;if(nx>=0&&nx<3&&ny>=0&&ny<3){state& t=st[rear];memcpy(&t,&s,sizeof(s)); //记录此时的状态即九个格子的数值t[z]=s[nz]; t[nz]=s[z];dis[rear]=dis[front]+1;if(decode(rear)) //判断st[rear]这种状态是否已经出现过rear++;}}front++;}return 0;}int main(void){intncase,i,oj;scanf("%d",&ncase);while(ncase--){memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));for(i=0;i<le;i++) scanf("%d",&st[1][i]); //按从左到右从上到下的顺序存储数据for(i=0;i<le;i++) scanf("%d",&goal[i]);oj=bfs();if(oj)printf("%d\n",dis[oj]);elseputs("-1");}return 0;}2.//用hash避免同一状态的再次访问在讲这种方法之前建议读者先看一下算法导论中有关hash的介绍为了方便自己以后看的时候方便，先写一下有关hash的内容Hash表解决冲突三种hash函数：first：除法散列函数: h(k)=k mod m(m为所选的余数,最好选接近装载因子α=n/m，但又远离2的k次幂的质数)second：乘法散列法函数: 看图:具体代码实现下面有介绍third：全域散列函数h a,b(k)=((ak+b) mod p) mod m (p>m 且p和m都为质数)//用链表实现hash#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define len 362888 //状态共有362880种，数组稍微开大点#define le 9 //每种状态有9个数据,也可看为每种状态下又有9种状态typedefint state[le]; //状态：表示九个格子state st[len],goal; //st为状态数组goal为目标数组int dis[len],der[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //dis为每种状态的已走的步骤//der为方向:上，下，左，右typedefstruct node {int v;struct node *next;}ore;ore *head[len]; //这里的head为hash表ore * create_new_node(){ore *p;p=(ore *)calloc(1,sizeof(ore));p->next=NULL;return p;}//此处为哈希函数，不理解的建议看一下算法导论，下面用3种hash函数实现//first:除法散列法int hash(state& s){inti,num,m=372001; //m为所选的余数,最好选接近装载因子α=n/m，但又远离2的k次幂的质数for(i=num=0;i<le;i++)num=num*10+s[i];returnnum%m;}//second:乘法散列法int hash(state& s){inti,num;long longk,w=32,ss,r0,p=14,ans; //这里的w为需要截取的位数//p为要截取的数字长度const double A = (sqrt(5.)-1)/2;for(i=num=0;i<le;i++)num=num*10+s[i];k=(long long)num;ss=(long long)(A*(1LL<<w));r0=k*ss%(1LL<<w);ans=r0>>(w-p);returnans;}//third:全域散列hash functionint hash(state& s){inti,num;longlong a=3,b=4,m=350001,p=360001,k,ans;for(i=num=0;i<le;i++)num=num*10+s[i];k=(long long)num;ans=(a*k+b)%p%m; //此处为全域散列函数returnans;}//以上的三种hash function选取一种即可bool find(int s){int h;ore *u,*p;h=hash(st[s]); //通过hash function计算出hash值，并将该元素定义为head数组的下标u=create_new_node();if(!head[h]) //如果head[h]未创建，即未访问过，则创建一个新节点head[h]=create_new_node();u=head[h]->next; //u指向head[h]的下一个元素while(u){if(memcmp(st[u->v],st[s],sizeof(st[s]))==0) //如果找到memcmp(st[u->v],st[s],sizeof(st[s]))==0 的数据项则说明该节点已经访问过return false;u=u->next; //访问下一个节点//原理看下面的说明}p=create_new_node(); //创建一个新节点p->next=head[h]->next; //用头插法在散列表中插入新的节点head[h]->next=p;p->v=s;return true;}intbfs(){int front=1,rear=2,i,x,y,z,nx,ny,nz;while(front<rear){state& s=st[front];if(memcmp(s,goal,sizeof(s))==0) //对front状态和目标状态进行比较return front;for(i=0;i<le;i++) //找到为0的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,...8这样的数据，0作为判断依据简单于用数据作为判断依据if(s[i]==0)break;x=i/3; y=i%3; z=i; //记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0;i<4;i++){ //按照上，下，左，右四个方向进行搜索nx=x+der[i][0];ny=y+der[i][1];nz=nx*3+ny;if(nx>=0&&nx<3&&ny>=0&&ny<3){state& t=st[rear];memcpy(&t,&s,sizeof(s)); //记录此时的状态即九个格子的数值t[z]=s[nz]; t[nz]=s[z];dis[rear]=dis[front]+1;if(find(rear)) //判断st[rear]这种状态是否已经出现过rear++;}}front++;}return 0;}int main(void){intncase,i,oj;scanf("%d",&ncase);while(ncase--){memset(head,0,sizeof(head));for(i=0;i<le;i++) scanf("%d",&st[1][i]); //按从左到右从上到下的顺序存储数据for(i=0;i<le;i++) scanf("%d",&goal[i]);oj=bfs();if(oj)printf("%d\n",dis[oj]);elseputs("-1");}return 0;}//基于链表的用数组实现hash#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define len 362888 //状态共有362880种，数组稍微开大点#define le 9 //每种状态有9个数据,也可看为每种状态下又有9种状态typedefint state[le]; //状态：表示九个格子state st[len],goal; //st为状态数组goal为目标数组int dis[len],head[len],next[len],der[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //dis为每种状态的已走的步骤//head为哈希表//next为链表//der为方向:上，下，左，右//此处为哈希函数，不理解的建议看一下算法导论，下面用3种hash函数实现//first:除法散列法int hash(state& s){inti,num,m=372001; //m为所选的余数,最好选接近装载因子α=n/m，但又远离2的k次幂的质数for(i=num=0;i<le;i++)num=num*10+s[i];returnnum%m;}//second:乘法散列法int hash(state& s){inti,num;long longk,w=32 /*这里的w为需要截取的位数*/ ,ss,r0,p=14 /*p为要截取的数字长度*/ ,ans;const double A = (sqrt(5.)-1)/2;for(i=num=0;i<le;i++)num=num*10+s[i];k=(long long)num;ss=(long long)(A*(1LL<<w));r0=k*ss%(1LL<<w);ans=r0>>(w-p);returnans;}//third:全域散列hash functionint hash(state& s){inti,num;longlong a=3,b=4,m=350001,p=360001,k,ans;for(i=num=0;i<le;i++)num=num*10+s[i];k=(long long)num;ans=(a*k+b)%p%m; //此处为全域散列函数returnans;}//以上的三种hash function选取一种即可bool find(int s){inth,u;h=hash(st[s]); //通过hash function计算出hash值，并将该元素定义为head数组的下标u=head[h]; //通过u获得head[h]的值while(u){ //如果前面已经访问过该项数据，则说明数据已经插入该项所对应的next数组中，则继续访问if(memcmp(st[u],st[s],sizeof(st[s]))==0) //如果找到memcmp(st[u],st[s],sizeof(st[s]))==0 的数据项则说明该节点已经访问过return false;u=next[u]; //访问下一个节点//原理看下面的说明}//这里的next其实是一个个链表的集合所组成的数组，不用链表的原因是应为链表的创建需要耗时，而且还要有多余的空间存储指针next[s]=head[h]; //这里的原理实际上是基于链表的头插法head[h]=s;return true;}intbfs(){int front=1,rear=2,i,x,y,z,nx,ny,nz;while(front<rear){state& s=st[front];if(memcmp(s,goal,sizeof(s))==0) //对front状态和目标状态进行比较return front;for(i=0;i<le;i++) //找到为0的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,...8这样的数据，0作为判断依据简单于用数据作为判断依据if(s[i]==0)break;x=i/3; y=i%3; z=i; //记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0;i<4;i++){ //按照上，下，左，右四个方向进行搜索nx=x+der[i][0];ny=y+der[i][1];nz=nx*3+ny;if(nx>=0&&nx<3&&ny>=0&&ny<3){state& t=st[rear];memcpy(&t,&s,sizeof(s)); //记录此时的状态即九个格子的数值t[z]=s[nz]; t[nz]=s[z];dis[rear]=dis[front]+1;if(find(rear)) //判断st[rear]这种状态是否已经出现过rear++;}}front++;}return 0;}int main(void){intncase,i,oj;scanf("%d",&ncase);while(ncase--){memset(head,0,sizeof(head));memset(next,0,sizeof(next));for(i=0;i<le;i++) scanf("%d",&st[1][i]); //按从左到右从上到下的顺序存储数据for(i=0;i<le;i++) scanf("%d",&goal[i]);oj=bfs();if(oj)printf("%d\n",dis[oj]);elseputs("-1");}return 0;}3.用stl集合避免重复访问同一状态//用stl避免同一状态重复出现#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <iostream>#include <set>using namespace std;#define len 362888 //状态共有362880种，数组稍微开大点#define le 9 //每种状态有9个数据,也可看为每种状态下又有9种状态typedefint state[le]; //状态：表示九个格子state st[len],goal; //st为状态数组goal为目标数组int dis[len],head[len],der[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //dis为每种状态的已走的步骤//der为方向:上，下，左，右structcmp{bool operator()(inta,int b)const{returnmemcmp(&st[a],&st[b],sizeof(st[a]))<0;}};set<int,cmp>vis;voidinit_lookup_table(){vis.clear();}inttry_to_insert(int s){if(vis.count(s)) return 0;vis.insert(s);return 1;}intbfs(){int front=1,rear=2,i,x,y,z,nx,ny,nz;init_lookup_table();while(front<rear){state& s=st[front];if(memcmp(s,goal,sizeof(s))==0) //对front状态和目标状态进行比较return front;for(i=0;i<le;i++) //找到为0的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,...8这样的数据，0作为判断依据简单于用数据作为判断依据if(s[i]==0)break;x=i/3; y=i%3; z=i; //记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右从上到下依次递增for(i=0;i<4;i++){ //按照上，下，左，右四个方向进行搜索nx=x+der[i][0];ny=y+der[i][1];nz=nx*3+ny;if(nx>=0&&nx<3&&ny>=0&&ny<3){state& t=st[rear];memcpy(&t,&s,sizeof(s)); //记录此时的状态即九个格子的数值t[z]=s[nz]; t[nz]=s[z];dis[rear]=dis[front]+1;if(try_to_insert(rear)) //判断st[rear]这种状态是否已经出现过rear++;}}front++;}return 0;}int main(void){intncase,i,oj;scanf("%d",&ncase);while(ncase--){memset(head,0,sizeof(head));for(i=0;i<le;i++) scanf("%d",&st[1][i]); //按从左到右从上到下的顺序存储数据for(i=0;i<le;i++) scanf("%d",&goal[i]);oj=bfs();if(oj)printf("%d\n",dis[oj]);elseputs("-1");}return 0;}。
