八数码问题详解

1、八数码问题详解（用bfs实现）八数码问题也称为九宫问题。在3x3的棋盘，摆有八个棋子，每个棋子上标有1至8的某 一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空 格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标 状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。 棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所 经过的一系列中间过渡状态。如图:对这道题用bfs解决个人认为是个不错的方法，首先因为它有九个格子，那么便可以用state 数组记录他的的九个格子的数值，其中空格

2、为0,后者由于它只有九个数，因此共有9! =362880种可能性，用bfs解决较快。下面给出bfs实现的三种代码（这里的三种指的是对是否访问过已知节点的三种判断方法）：1 .用一套排列的编码和解码函数解决同一状态的再次访问用统一的编码与解码函数避免同种状态的再次出现#include #include #include #include #define len 362888状态共有362880种，数组稍微开大点define ie 9每种状态有9个数据，也可看为每种状态下又有9种状态typedefint statele; state stlen,goal;状态：表示九个格子/st为状态数组 goa

3、l为目标数组int dislenlfactlelheadlen,vislenlder42=-l,0,l,0h0,-l,0,l;/dis 为每种状态的已走的步骤 der为方向:上，下，左，右编码解码void encode()int i;for(i=fact0=l;ile;i+) facti=facti-l*i;int decode(int s)intijcodecnt;for(i=code=0;ile;i+)for(cnt=oj=i+l;jstsu)cnt+;code+=cnt*fact8-i;if(viscode) return 0;elsereturn viscode=l;) intbfs(

4、)int front=l/rear=2j/x,y,z/nx/ny/nz;encode();while(frontrear)state& s=stfront;if(memcmp(s/goal/sizeof(s)=0) 对 front 状态和目标状态进行比较 return front;for(i=0;ile;i+)找到为。的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,23.8这样的数据，。作为判断依据简单于用数据作为判断 依据if(s=o)break;x=0;y=i%3; z=i;记录空的格子的行标，列表，和所在位置,这里的位置按照从左到右从上到下依次递增for(i=0;i=0&nx

5、=0&ny3)state& t=strear;memcpy(&tz&s,sizeof(s);记录此时的状态即九个格子的数值tz=snz;tnz=sz;disrear=disfront+l; if(decode(rear)判断stear这种状态是否已经出现过rear+; ) ) front+; return 0; ) int main(void) intncasejj; scanf(,%d,/&ncase); while(ncase-) memset(head,0,sizeof(head); memset(vis,0,sizeof(vis); for(i=0;ile;i+)scanf(%d,&s

6、tli);按从左到右从上到下的顺序存储数据for(i=0;im 且 p 和 m 都为质数)用链表实现hash#include #include #include #include #define len 362888状态共有362880种，数组稍微开大点sdefine ie 9typedefint statele; state stlen,goal;每种状态有9个数据，也可看为每种状态下又有9种状态状态：表示九个格子/st为状态数组 goal为目标数组int disuenlder42=-l0,l,0,0,：,0二; /dis 为每种状态的已走的步骤 /der 为方 向:上，下，左，右typed

7、efstruct node int v;struct node *next;ore;ore *headlen;这里的 head 为 hash 表ore * create_new_node()ore *p;p=(ore *)calloc(lzsizeof(ore);p-next=null;return p;)此处为哈希函数，不理解的建议看一下算法导论，下面用3种hash函数实现“first:除法散列法int hash(state& s)inti/num,m=372001;/m为所选的余数，最好选接近装载因子a =n/m,但又远离2的k次鬲的质数for(i=num=0;ile;i+)num=num

8、*10+si;returnnum%m;) “second:乘法散列法 int hash(state& s)inti,num;这里的w为需要截取的位数 p为要截取的long iongk/w=32/ss/r0,p=14/ans; 数字长度const double a = (sqrt(5.)-l)/2;for(i=num=0;ile;i+)num=num*10+si;k=(long long)num;ss=(long long)(a*(lllw);ro=k*ss%(lllw);ans=r0(w-p);returnans;)third:全域散列 hash functionint hash(state&

9、 s)inti,num;longlong a=3,b=4,m=350001,p=360001kans;for(i=num=0;inext;/u 指向 headh的下一个元素while(u)如果找到if(memcmp(stu-v,sts/sizeof(sts)=0)return false;u=u-next;p=create_new_node();p-next=headh-next;memcmp(stu-v/sts/sizeof(sts)=0的数据项则说明该节点已经访问过访问卜一个节点原理看下面的说明创建一个新节点用头插法在散列表中插入新的节点headh-next=p;p-v=s; return

10、 true;) intbfs() int front=l/rear=2j/x,y,z/nx/ny/nz; while(frontrear)state& s=stfront;if(memcmp(s/goal/sizeof(s)=0) 对 front 状态和目标状态进行比较 return front;for(i=0;ile;i+)找到为。的元素，即空的那个格子，这里选取空的那个格子是应为相对于123,.8这样的数据，。作为判断依据简单于用数据作为判断 依据break;x=i6;y=i%3; z=i;记录空的格子的行标，列表，和所在位置,这里的位置按照从左到右从上到下依次递增 for(i=0;i=0

11、&nx=0&ny3) state& t=strear; memcpy(&t,&s,sizeof(s);记录此时的状态即九个格子的数值tz=snz;tnz=sz;disrear=disfront+l; if(find(rear)判断stear这种状态是否己经出现过rear+; ) ) front+; return 0; ) int main(void) intncase joj; scanf(,%d,/&ncase); while(ncase-) memset(head,0,sizeof(head); for(i=0;ile;i+)scanf(%d,&stli);按从左到右从上到下的顺序存储数据

12、 for(i=0;ile;i+)scanf(,%d,&goali);oj=bfs(); if(oj) printf(,%dn,disoj); else puts(-l);return 0;基于链表的用数组实现hash#include #include #include #include #define len 362888#define ie 9状态共有362880种，数组稍微开大点每种状态有9个数据，也可看为每种状态下又有9种状态typedefint statele; state stlen,goal;状态：表示九个格子/st为状态数组 goal为目标数组int disuenjheadlen

13、,nextlen,der2=-1,0/1,0,0厂1,0,1;/dis 为每种状态的己走的步骤 head为哈希表 next为链表 der为方向:上，下，左，右此处为哈希函数，不理解的建议看一下算法导论，下面用3种hash函数实现“first:除法散列法int hash(state& s)inti/num,m=372001;/m为所选的余数，最好选接近装载因子a =n/m,但又远离2的k次鬲的质数for(i=num=0;ile;i+)num=num*10+si;returnnum%m;)“second:乘法散列法int hash(state& s)inti,num;long longk,w=32

14、 /*这里的w为需要截取的位数*/,ss,r0,p=14/*p为要截取的数字长度*/ ,ans;const double a = (sqrt(5.)-l)/2;for(i=num=0;ile;i+)num=num*10+si;k=(long long)num;ss=(long long)(a*(lllw);ro=k*ss%(lllw);ans=r0(w-p);returnans;)third:全域散列 hash function int hash(state& s)inti,num;longlong a=3,b=4,m=350001,p=36000lk,ans;for(i=num=0;ile;

15、i+)num=num*10+si;k=(long long)num;ans=(a*k+b)%p%m; 此处为全域散列函数 returnans; ) 以上的三种hash function选取一种即可 bool findfint s)inth,u;h=hash(sts); 通过hash function计算出hash值，并将该元素定义为head数组 的下标u=headh;通过 u 获得 headh的值while(u)如果前面己经访问过该项数据，则说明数据已经插入该项所对应的next数组中，则继续访问if(memcmp(stu/sts/sizeof(sts)=0)如果找到memcmp(stujsts

16、jsizeof(sts)=0的数据项则说明该节点已经访问过return false;u=nextu;访问下一个节点原理看下面的说明 这里的next其实是一个个链表的集合所组成的数组，不用链表的原因是应为链表的创 建需要耗时，而且还要有多余的空间存储指针nexts=headh;这里的原理实际上是基于链表的头插法headh=s;return true;)intbfs()int front=l/rear=2j/x,y,z/nx/ny/nz;while(frontrear)state& s=stfront;if(memcmp(s/goal/sizeof(s)=0) 对 front 状态和目标状态进行比

17、较 return front;for(i=0;ile;i+)找到为。的元素，即空的那个格子，这里选取空的那个格子是应为相对于1,2,3,.8这样的数据，0作为判断依据简单于用数据作为判断 依据 if(si=o) break; x=i3;y=i%3; z=i;记录空的格子的行标，列表，和所在位置,这里的位置按照从左到右从上到下依次递增for(i=0;i=0&nx=0&ny3) state& t=strear; memcpy(&tz&s,sizeof(s);记录此时的状态即九个格子的数值tz=snz;tnz=sz;disrear=disfront+l; if(find(rear)判断stear这种

18、状态是否己经出现过rear+; ) ) front+; return 0; ) int main(void) intncase joj; scanf(,%d,/&ncase); while(ncase-) memset(head,0,sizeof(head); memsettnextasizeoffnext); for(i=0;ile;i+)scanf(%d,&stli);按从左到右从上到下的顺序存储数据 for(i=0;ile;i+)scanf(,%d,&goali);oj=bfs(); if(oj) printf(%dn,disoj); else puts(-l)； return 0; )

19、3,用stl集合避免重更访问同一状态用stl避免同一状态重更出现/include /include /include #include #include #include using namespace std; #define len 362888 #define ie 9 typedefint statele; state stlen,goal;状态共有362880种，数组稍微开大点每种状态有9个数据，也可看为每种状态下又有9种状态状态：表示九个格子/st为状态数组goal为目标数组int dislen,headlen,der2=-1,0,1,0,0厂1,0,1;/dis 为每种状态的己走的步骤der为方向:上，下，左，右structcmpbool operator()(inta,int b)constreturnmemcmp(&stal&stb,sizeof(sta)0;setvis;voidinitjookup_table()vis.clear();)inttry_tojnsert(int s)if(vis.count(s) return 0;vis.insert(s);return 1;)intbfs()int front=l/rear=2/i/x,y,z/nx,ny/nz;initjookup_table