Eight
tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x r-> d-> r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
2 3 4 1 5 x 7 6 8
ullddrurdllurdruldr
//Memory 20908K Time 687MS #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #define maxn 370000 using namespace std; int fac[15]= {40320,5040,720,120,24,6,2,1,1}; //康拖展开判重 int vis[maxn]; int cnt=0; string anspath[maxn],ans; int dx[4]={-1,1,0,0}; // up down left right int dy[4]={0,0,-1,1}; char dir[5]="durl"; struct Tnode { char s[9]; int loc; //“0”的位置 int val; //康拖展开的值 string path; //路径 } cur,now; queue<Tnode> q; int kangtuo(char *ss) // 求康拓展开的值 { int i,j,t,sum=0; for(i=0; i<9; i++) { t=0; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]) t++; } sum+=t*fac[i]; } return sum+1; } void bfs() { int i,j,t,t1; int tempv,x,y,nx,ny; char temps[9]; memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); for(i=0;i<8;i++) cur.s[i]=i+1-0+'0'; cur.s[8]='0'; cur.loc=9; cur.path=""; cur.val=kangtuo(cur.s); vis[cur.val]=1; anspath[cur.val]=cur.path; q.push(cur); while(!q.empty()) { now=q.front(); t=now.loc; y=t%3; if(y==0) y=3; x=(t-y)/3+1; q.pop(); for(i=0;i<4;i++) { nx=x+dx[i]; ny=y+dy[i]; t1=(nx-1)*3+ny; memcpy(temps,now.s,sizeof(temps)); temps[t-1]=now.s[t1-1]; temps[t1-1]='0'; tempv=kangtuo(temps); if(nx>=1&&nx<=3&&ny>=1&&ny<=3&&!vis[tempv]) { vis[tempv]=1; cur.loc=t1; cur.path=now.path+dir[i]; memcpy(cur.s,temps,sizeof(temps)); cur.val=tempv; q.push(cur); anspath[cur.val]=cur.path; // 每次将情况存下来 } } } } int main() { int i,j,temp1; char c; bfs(); // 从结果倒着搜 将各种情况存下来 while(cin>>c) { if(c=='x') { cur.loc=1; cur.s[0]='0'; } else cur.s[0]=c; for(i=1; i<9; i++) { cin>>c; if(c=='x') { cur.loc=i+1; cur.s[i]='0'; } else cur.s[i]=c; } cur.val=kangtuo(cur.s); if(vis[cur.val]) // 若存在则倒着输出路径就够了 { temp1=anspath[cur.val].length(); for(i=temp1-1;i>=0;i--) printf("%c",anspath[cur.val][i]); } else printf("unsolvable"); printf("\n"); } return 0; }
// Memory 5548K Time 344MS #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #define maxn 370000 using namespace std; int ans; int fac[]= {40320,5040,720,120,24,6,2,1,1}; //康拖展开判重 bool vis[maxn]; int dx[]= {-1,1,0,0}; // up down left right int dy[]= {0,0,-1,1}; char dir[]="udlr"; struct Tnode { char s[9]; int loc; // “0”的位置 int val; // 康拖展开的值 char d; // 方向 int fa; } cur,now,q[maxn]; bool judge(char *ss) // 根据逆序数是否为奇数判断是否有解 { int i,j,t=0; for(i=0; i<9; i++) { if(ss[i]=='0') continue ; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]&&ss[j]!='0') t++; } } if(t&1) return false ; return true ; } int kangtuo(char *ss) // 求康拓展开的值 { int i,j,t,sum=0; for(i=0; i<9; i++) { t=0; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]) t++; } sum+=t*fac[i]; } return sum+1; } bool bfs() { int i,j,t,t1; int head=0,tail=-1; int tempv,x,y,nx,ny,nval,npos; char temps[9]; memset(vis,0,sizeof(vis)); cur.fa=-1; cur.val=kangtuo(cur.s); vis[cur.val]=1; q[++tail]=cur; while(head<=tail) { now=q[head]; t=now.loc; nval=now.val; if(nval==46234) { ans=head; return true ; } y=t%3; if(y==0) y=3; x=(t-y)/3+1; for(i=0; i<4; i++) { nx=x+dx[i]; ny=y+dy[i]; if(!(nx>=1&&nx<=3&&ny>=1&&ny<=3)) continue ; t1=(nx-1)*3+ny; for(j=0; j<9; j++) { temps[j]=now.s[j]; } temps[t-1]=now.s[t1-1]; temps[t1-1]='0'; tempv=kangtuo(temps); if(!vis[tempv]) { vis[tempv]=1; cur.loc=t1; cur.d=dir[i]; cur.fa=head; for(j=0; j<9; j++) { cur.s[j]=temps[j]; } cur.val=tempv; q[++tail]=cur; } } head++; } return false ; } void output(int k) // 递归输出答案 { if(k==0) return ; else { output(q[k].fa); printf("%c",q[k].d); } } int main() { int i,j,temp1,vv; char c; while(cin>>c) { if(c=='x') { cur.loc=1; cur.s[0]='0'; } else cur.s[0]=c; for(i=1; i<9; i++) { cin>>c; if(c=='x') { cur.loc=i+1; cur.s[i]='0'; } else cur.s[i]=c; } if(judge(cur.s)&&bfs()) { output(ans); printf("\n"); } else printf("unsolvable\n"); } return 0; }
// Memory 4040K Time 32MS #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #define maxn 370000 using namespace std; int ans1,ans2; int fac[]= {40320,5040,720,120,24,6,2,1,1}; //康拖展开判重 bool vis1[maxn],vis2[maxn]; int dx[]= {-1,1,0,0}; // up down left right int dy[]= {0,0,-1,1}; int mp1[maxn],mp2[maxn]; char dir1[]="udlr"; char dir2[]="durl"; struct Tnode { char s[9]; int loc; // “0”的位置 int val; // 康拖展开的值 char d; // 方向 int fa; int step; } cur,now,q1[maxn],q2[maxn]; bool judge(char *ss) // 根据逆序数是否为奇数判断是否有解 { int i,j,t=0; for(i=0; i<9; i++) { if(ss[i]=='0') continue ; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]&&ss[j]!='0') t++; } } if(t&1) return false ; return true ; } int kangtuo(char *ss) // 求康拓展开的值 { int i,j,t,sum=0; for(i=0; i<9; i++) { t=0; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]) t++; } sum+=t*fac[i]; } return sum; } bool bfs() { int i,j,t,t1,step1,step2; int head1=0,tail1=-1,head2=0,tail2=-1; int tempv,x,y,nx,ny,nval,npos; char temps[9]; memset(vis1,0,sizeof(vis1)); memset(vis2,0,sizeof(vis2)); cur.step=0; cur.val=kangtuo(cur.s); vis1[cur.val]=1; mp1[cur.val]=0; q1[++tail1]=cur; strcpy(cur.s,"123456780"); cur.val=kangtuo(cur.s); cur.loc=9; vis2[cur.val]=1; mp2[cur.val]=0; q2[++tail2]=cur; step1=step2=0; while(1) { while(q1[head1].step<=step1&&head1<=tail1) { now=q1[head1]; t=now.loc; nval=now.val; if(vis2[nval]) { ans1=head1; ans2=mp2[nval]; return true ; } y=t%3; if(y==0) y=3; x=(t-y)/3+1; for(i=0; i<4; i++) { nx=x+dx[i]; ny=y+dy[i]; if(!(nx>=1&&nx<=3&&ny>=1&&ny<=3)) continue ; t1=(nx-1)*3+ny; for(j=0; j<9; j++) { temps[j]=now.s[j]; } temps[t-1]=now.s[t1-1]; temps[t1-1]='0'; tempv=kangtuo(temps); if(!vis1[tempv]) { vis1[tempv]=1; cur.loc=t1; cur.d=dir1[i]; cur.fa=head1; cur.step=now.step+1; for(j=0; j<9; j++) { cur.s[j]=temps[j]; } cur.val=tempv; q1[++tail1]=cur; mp1[tempv]=tail1; } } head1++; } step1++; while(q2[head2].step<=step2&&head2<=tail2) { now=q2[head2]; t=now.loc; nval=now.val; if(vis1[nval]) { ans1=mp1[nval]; ans2=head2; return true ; } y=t%3; if(y==0) y=3; x=(t-y)/3+1; for(i=0; i<4; i++) { nx=x+dx[i]; ny=y+dy[i]; if(!(nx>=1&&nx<=3&&ny>=1&&ny<=3)) continue ; t1=(nx-1)*3+ny; for(j=0; j<9; j++) { temps[j]=now.s[j]; } temps[t-1]=now.s[t1-1]; temps[t1-1]='0'; tempv=kangtuo(temps); if(!vis2[tempv]) { vis2[tempv]=1; cur.loc=t1; cur.d=dir2[i]; cur.fa=head2; cur.step=now.step+1; for(j=0; j<9; j++) { cur.s[j]=temps[j]; } cur.val=tempv; q2[++tail2]=cur; mp2[tempv]=tail2; } } head2++; } step2++; } } void output1(int k) // 递归输出答案 { if(k==0) return ; else { output1(q1[k].fa); printf("%c",q1[k].d); } } void output2(int k) // 递归输出答案 { if(k==0) return ; else { printf("%c",q2[k].d); output2(q2[k].fa); } } int main() { int i,j,temp1,vv; char c; while(cin>>c) { if(c=='x') { cur.loc=1; cur.s[0]='0'; } else cur.s[0]=c; for(i=1; i<9; i++) { cin>>c; if(c=='x') { cur.loc=i+1; cur.s[i]='0'; } else cur.s[i]=c; } if(judge(cur.s)&&bfs()) { output1(ans1); output2(ans2); printf("\n"); } else printf("unsolvable\n"); } return 0; }
当前所在位置和本应该所在位置的行列之差的绝对值之和 },另外还有一个剪枝见代码。
// 168K 0MS #include <cstdio> #include <cstring> #include <cmath> #define maxn 10 #define INF 0x3f3f3f3f using namespace std; int depth,flag,mi; int a[maxn]; int dx[]= {-1,1,0,0}; // up down left right int dy[]= {0,0,-1,1}; char dir[]="udlr"; char s[maxn],anss[1005]; bool judge() // 根据逆序数是否为奇数判断是否有解 { int i,j,t=0; for(i=0; i<9; i++) { if(a[i]==9) continue ; for(j=i+1; j<9; j++) { if(a[i]>a[j]) t++; } } if(t&1) return false ; return true ; } int h() // 最少还需多少步达到目标状态 { int i,j,nx,ny,tx,ty,t=0; for(i=0; i<9; i++) { if(a[i]==9) continue ; nx=i/3,ny=i%3; tx=(a[i]-1)/3,ty=(a[i]-1)%3; t=t+abs(nx-tx)+abs(ny-ty); } return t; } void dfs(int x,int d) { int i,j,t,nx,ny,tx,ty; t=h(); if(mi>t) mi=t; if(d+t>depth||flag) return ; if(!t) { flag=1; anss[d]='\0'; printf("%s\n",anss); return ; } nx=x/3,ny=x%3; for(i=0; i<4; i++) { tx=nx+dx[i]; ty=ny+dy[i]; if(tx<0||tx>=3||ty<0||ty>=3) continue ; if((d>0)&&(i==0&&anss[d-1]=='d'||i==1&&anss[d-1]=='u'||i==2&&anss[d-1]=='r'||i==3&&anss[d-1]=='l')) continue ; // 剪枝 相邻两步不来回走 t=a[nx*3+ny],a[nx*3+ny]=a[tx*3+ty],a[tx*3+ty]=t; anss[d]=dir[i]; dfs(tx*3+ty,d+1); t=a[nx*3+ny],a[nx*3+ny]=a[tx*3+ty],a[tx*3+ty]=t; } } void IDAX(int x) { int i,j; depth=h(); flag=0; while(!flag) { mi=INF; dfs(x,0); depth+=mi; // 每次加上最小需移动的步数(也可以++,稍稍慢一点) } } int main() { int i,j,x; while(~scanf("%s",s)) { if(s[0]=='x') x=0,a[0]=9; else a[0]=s[0]-'0'; for(i=1; i<=8; i++) { scanf("%s",s); if(s[0]=='x') x=i,a[i]=9; else a[i]=s[0]-'0'; } if(!judge()) { printf("unsolvable\n"); continue ; } IDAX(x); } return 0; }
// 912K 32MS #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #define maxn 370000 using namespace std; int ans,sx; int fac[]= {40320,5040,720,120,24,6,2,1,1}; //康拖展开判重 bool vis[maxn]; int dx[]= {-1,1,0,0}; // up down left right int dy[]= {0,0,-1,1}; char dir[]="udlr"; struct Node { char d; int fa; }anss[maxn]; struct Tnode { char s[9]; int loc; // “0”的位置 int val; // 康拖展开的值 int hh; // 到达目标状态最小步数 bool operator < (const Tnode&xx)const { return hh>xx.hh; } } cur,now; priority_queue<Tnode>q; bool judge(char *ss) // 根据逆序数是否为奇数判断是否有解 { int i,j,t=0; for(i=0; i<9; i++) { if(ss[i]=='0') continue ; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]&&ss[j]!='0') t++; } } if(t&1) return false ; return true ; } int kangtuo(char *ss) // 求康拓展开的值 { int i,j,t,sum=0; for(i=0; i<9; i++) { t=0; for(j=i+1; j<9; j++) { if(ss[i]>ss[j]) t++; } sum+=t*fac[i]; } return sum+1; } int h(char *ss) // 最少还需多少步达到目标状态 { int i,j,nx,ny,tx,ty,t=0; for(i=0; i<9; i++) { if(ss[i]=='0') continue ; nx=i/3,ny=i%3; tx=(ss[i]-'1')/3,ty=(ss[i]-'1')%3; t=t+abs(nx-tx)+abs(ny-ty); } return t; } bool bfs() { int i,j,t,t1; int tempv,x,y,nx,ny,nval,npos; char temps[9]; memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); cur.hh=h(cur.s); cur.val=kangtuo(cur.s); sx=cur.val; vis[cur.val]=1; q.push(cur); while(!q.empty()) { now=q.top(); q.pop(); t=now.loc; nval=now.val; y=t%3; if(y==0) y=3; x=(t-y)/3+1; for(i=0; i<4; i++) { nx=x+dx[i]; ny=y+dy[i]; if(!(nx>=1&&nx<=3&&ny>=1&&ny<=3)) continue ; t1=(nx-1)*3+ny; for(j=0; j<9; j++) { temps[j]=now.s[j]; } temps[t-1]=now.s[t1-1]; temps[t1-1]='0'; tempv=kangtuo(temps); if(!vis[tempv]) { if(tempv==46234) { anss[tempv].d=dir[i]; anss[tempv].fa=nval; return true ; } vis[tempv]=1; cur.loc=t1; anss[tempv].d=dir[i]; anss[tempv].fa=nval; for(j=0; j<9; j++) { cur.s[j]=temps[j]; } cur.hh=h(cur.s); cur.val=tempv; q.push(cur); } } } return false ; } void output(int k) // 递归输出答案 { if(k==sx) return ; else { output(anss[k].fa); printf("%c",anss[k].d); } } int main() { int i,j,temp1,vv; char c; ans=46234; while(cin>>c) { if(c=='x') { cur.loc=1; cur.s[0]='0'; } else cur.s[0]=c; for(i=1; i<9; i++) { cin>>c; if(c=='x') { cur.loc=i+1; cur.s[i]='0'; } else cur.s[i]=c; } if(judge(cur.s)&&bfs()) { output(ans); printf("\n"); } else printf("unsolvable\n"); } return 0; }