Problem Description The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one 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.
这前那篇文章也介绍了一些了，那位大神的文章也写的很好了，我就是来水一下。
首先就是我写的康托展开，用来表示每一个状态，其实对于一个状态 2 3 4 1 5 x 7 6 8来说，把x当作0，就是0到8的一个全排了，那么一共就9！种，这样就是第一个＊8！，第二个＊7！。。。这样下去。。。不过每一个乘的数应该是这个数本身的值减去前面比他小的个数，也就是他在剩下的数里面是第几个。
由一个值转化为一个排列也是如此，每一次找第k个还没有用到的数，就是那个数了。因为这里就只有9个数，直接n^2过一遍就好了。。。（对于很多数，可以用数状数组来做，转化为排列的话就是二分加数状数组。）
然后是减枝，减去无解的情况。对于每一次移动，数的逆序对的奇偶性是不会改变的（这里x不算数），然后的话先求逆序数，如果为奇就直接pass掉。
首先是第一次写，
BFS+康托+剪枝，TLE了。
#include<iostream>
#include<cstring>using namespace std;const int maxn=;
const int Enum=;
const int jie[]={,,,,,,,,};int que[];
int fa[maxn];
int las,fir;
int rem[maxn];
char ans1[maxn];
int cou;int hebing(int (*m)[])
{
bool vis[]={};
int cou;
int ans=; for(int i=;i<;++i)
{
cou=;
for(int j=;j<m[i/][i%];++j)
if(vis[j])
++cou; vis[m[i/][i%]]=; ans+=(m[i/][i%]-cou)*jie[-i];
} return ans;
}void zhankai(int (*m)[],int x)
{
bool vis[]={};
int cou;
int k; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cou=x/jie[-*i-j]+; // !!!
x%=jie[-*i-j]; for(k=;k<&&cou;++k)
if(vis[k]==)
--cou; vis[k-]=; // !!!
m[i][j]=k-; // !!!
}
}void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}bool judge(int x,int y)
{
if(x<||y<||x>||y>)
return ; return ;
}void showans()
{
int temp=Enum;
char c;
cou=; while(fa[temp]!=-)
{
if(rem[temp]==)
c='d';
else if(rem[temp]==)
c='l';
else if(rem[temp]==)
c='u';
else
c='r'; ans1[cou++]=c; temp=fa[temp];
} for(int i=cou-;i>=;--i)
cout<<ans1[i]; cout<<endl;
}void solve(int (*m)[])
{
int ni=; for(int i=;i<;++i)
for(int j=;j<i;++j)
if(m[i/][i%]&&m[j/][j%])
if(m[i/][i%]<m[j/][j%])
++ni; if(ni%)
{
cout<<"unsolvable\n";
return;
} las=fir=;
memset(rem,,sizeof(rem)); bool ok=;
int temp,t1[][],temp1;
int x0,y0; temp=hebing(m); rem[temp]=-;
que[las++]=temp;
fa[temp]=-; while(las-fir)
{
temp=que[fir++]; if(temp==Enum)
{
ok=;
break;
} zhankai(t1,temp); for(int i=;i<;++i)
for(int j=;j<;++j)
if(t1[i][j]==)
x0=i,y0=j; if(judge(x0-,y0))
{
swap(t1[x0][y0],t1[x0-][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
rem[temp1]=;
fa[temp1]=temp;
que[las++]=temp1;
} swap(t1[x0][y0],t1[x0-][y0]);
}
if(judge(x0+,y0))
{
swap(t1[x0+][y0],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
rem[temp1]=;
fa[temp1]=temp;
que[las++]=temp1;
} swap(t1[x0][y0],t1[x0+][y0]);
}
if(judge(x0,y0-))
{
swap(t1[x0][y0-],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
rem[temp1]=;
fa[temp1]=temp;
que[las++]=temp1;
} swap(t1[x0][y0],t1[x0][y0-]);
}
if(judge(x0,y0+))
{
swap(t1[x0][y0+],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
rem[temp1]=;
fa[temp1]=temp;
que[las++]=temp1;
} swap(t1[x0][y0],t1[x0][y0+]);
}
} if(ok)
showans();
else
cout<<"unsolvable"<<endl;
}int main()
{
ios::sync_with_stdio(false); int m[][];
char c; while(cin>>c)
{
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-''; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cin>>c;
m[i][j]=c=='x'?:c-'';
} solve(m);
} return ;
}
然后就是
双向BFS+康托+剪枝，就过了。
#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int maxn=;
const int Enum=;
const int jie[]={,,,,,,,,};
const int step[][]={{,},{,-},{-,},{,}};int Snum,Mnum;
int fa[maxn],son[maxn];
int rem[maxn],Mrem;
int que1[maxn],que2[maxn];
int las1,las2,fir1,fir2;
char ans[maxn];int hebing(int (*m)[])
{
bool vis[]={};
int cou;
int ans=; for(int i=;i<;++i)
{
cou=;
for(int j=;j<m[i/][i%];++j)
if(vis[j])
++cou; vis[m[i/][i%]]=; ans+=(m[i/][i%]-cou)*jie[-i];
} return ans;
}void zhankai(int (*m)[],int x)
{
bool vis[]={};
int cou;
int k; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cou=x/jie[-*i-j]+; // !!!
x%=jie[-*i-j]; for(k=;k<&&cou;++k)
if(vis[k]==)
--cou; vis[k-]=; // !!!
m[i][j]=k-; // !!!
}
}void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}bool judge(int x,int y)
{
if(x<||y<||x>||y>)
return ; return ;
}void showans()
{
int cou=;
char c;
int tnum=Mnum; while(tnum!=Snum)
{
if(rem[tnum]==)
c='d';
else if(rem[tnum]==)
c='l';
else if(rem[tnum]==)
c='u';
else
c='r'; ans[cou++]=c; tnum=fa[tnum];
} for(int i=cou-;i>=;--i)
cout<<ans[i]; rem[Mnum]=Mrem;
tnum=Mnum; while(tnum!=Enum)
{
rem[tnum]=-rem[tnum];
if(rem[tnum]==)
c='u';
else if(rem[tnum]==)
c='r';
else if(rem[tnum]==)
c='d';
else
c='l'; cout<<c; tnum=son[tnum];
} cout<<endl;
}bool bfs()
{
fir1=fir2=las1=las2=; int temp,t1[][],t2[][];
int tnum1,tnum2;
int x01,y01,x02,y02; que1[las1++]=Snum;
que2[las2++]=Enum; rem[Snum]=;
rem[Enum]=-; son[Enum]=Enum;
fa[Snum]=Snum; while(las1-fir1&&las2-fir2)
{
tnum1=que1[fir1++];
tnum2=que2[fir2++]; zhankai(t1,tnum1);
zhankai(t2,tnum2); for(int i=;i<;++i)
for(int j=;j<;++j)
{
if(t1[i][j]==)
x01=i,y01=j;
if(t2[i][j]==)
x02=i,y02=j;
} for(int i=;i<;++i)
{
if(judge(x01+step[i][],y01+step[i][])==)
continue; swap(t1[x01][y01],t1[x01+step[i][]][y01+step[i][]]);
temp=hebing(t1); if(rem[temp]==)
{
rem[temp]=i+;
fa[temp]=tnum1;
que1[las1++]=temp;
}
else if(rem[temp]<)
{
fa[temp]=tnum1;
Mrem=rem[temp];
rem[temp]=i+;
Mnum=temp; return ;
} swap(t1[x01][y01],t1[x01+step[i][]][y01+step[i][]]);
} for(int i=;i<;++i)
{
if(judge(x02+step[i][],y02+step[i][])==)
continue; swap(t2[x02][y02],t2[x02+step[i][]][y02+step[i][]]);
temp=hebing(t2); if(rem[temp]==)
{
rem[temp]=-(i+);
son[temp]=tnum2;
que2[las2++]=temp;
}
else if(rem[temp]>)
{
son[temp]=tnum2;
Mrem=-(i+);
Mnum=temp; return ;
} swap(t2[x02][y02],t2[x02+step[i][]][y02+step[i][]]);
}
} return ;
}void solve(int (*m)[])
{
int ni=; for(int i=;i<;++i)
for(int j=;j<i;++j)
if(m[i/][i%]&&m[j/][j%])
if(m[i/][i%]<m[j/][j%])
++ni; if(ni%)
{
cout<<"unsolvable\n";
return;
} memset(rem,,sizeof(rem)); Snum=hebing(m); if(Snum==Enum)
{
cout<<endl;
return;
} if(bfs())
showans();
else
cout<<"unsolvable\n";
}int main()
{
ios::sync_with_stdio(false); int m[][];
char c; while(cin>>c)
{
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-''; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cin>>c;
m[i][j]=c=='x'?:c-'';
} solve(m);
} return ;
}
A＊（曼哈顿距离）+康托+剪枝。
#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
#include<cmath>
#include<cstdio>using namespace std;const int maxn=;
const int Enum=;
const int jie[]={,,,,,,,,};struct state
{
int F,G,num; state() {}
state(int a,int b,int c):F(a),G(b),num(c) {} friend bool operator < (state x,state y)
{
return x.F>y.F;
}
};int fa[maxn];
int rem[maxn];
char ans1[maxn];
int cou;int hebing(int (*m)[])
{
bool vis[]={};
int cou;
int ans=; for(int i=;i<;++i)
{
cou=;
for(int j=;j<m[i/][i%];++j)
if(vis[j])
++cou; vis[m[i/][i%]]=; ans+=(m[i/][i%]-cou)*jie[-i];
} return ans;
}void zhankai(int (*m)[],int x)
{
bool vis[]={};
int cou;
int k; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cou=x/jie[-*i-j]+; // !!!
x%=jie[-*i-j]; for(k=;k<&&cou;++k)
if(vis[k]==)
--cou; vis[k-]=; // !!!
m[i][j]=k-; // !!!
}
}void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}bool judge(int x,int y)
{
if(x<||y<||x>||y>)
return ; return ;
}void showans()
{
int temp=Enum;
char c;
cou=; while(fa[temp]!=-)
{
if(rem[temp]==)
c='d';
else if(rem[temp]==)
c='l';
else if(rem[temp]==)
c='u';
else
c='r'; ans1[cou++]=c; temp=fa[temp];
} for(int i=cou-;i>=;--i)
cout<<ans1[i]; cout<<endl;
}int getH(int (*m)[])
{
int H=; for(int i=;i<;++i)
for(int j=;j<;++j)
if(m[i][j])
H+=abs(i-(m[i][j]-)/)+abs(j-(m[i][j]-)%);
else
H+=abs(i-)+abs(j-); return H;
}void solve(int (*m)[])
{
int ni=; for(int i=;i<;++i)
for(int j=;j<i;++j)
if(m[i/][i%]&&m[j/][j%])
if(m[i/][i%]<m[j/][j%])
++ni; if(ni%)
{
cout<<"unsolvable\n";
return;
} priority_queue <state> que; memset(rem,,sizeof(rem)); bool ok=;
int temp,t1[][],temp1;
int x0,y0;
int H=,G;
state tsta; temp=hebing(m); que.push(state(H,,temp));
rem[temp]=-;
fa[temp]=-; while(!que.empty())
{
H=; tsta=que.top();
que.pop(); G=tsta.G;
temp=tsta.num; if(temp==Enum)
{
ok=;
break;
} zhankai(t1,temp); for(int i=;i<;++i)
for(int j=;j<;++j)
if(t1[i][j]==)
x0=i,y0=j; if(judge(x0-,y0))
{
swap(t1[x0][y0],t1[x0-][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
H=getH(t1);
rem[temp1]=;
fa[temp1]=temp;
que.push(state(G++H,G+,temp1));
} swap(t1[x0][y0],t1[x0-][y0]);
}
if(judge(x0+,y0))
{
swap(t1[x0+][y0],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
H=getH(t1);
rem[temp1]=;
fa[temp1]=temp;
que.push(state(G+H+,G+,temp1));
} swap(t1[x0][y0],t1[x0+][y0]);
}
if(judge(x0,y0-))
{
swap(t1[x0][y0-],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
H=getH(t1);
rem[temp1]=;
fa[temp1]=temp;
que.push(state(G+H+,G+,temp1));
} swap(t1[x0][y0],t1[x0][y0-]);
}
if(judge(x0,y0+))
{
swap(t1[x0][y0+],t1[x0][y0]);
temp1=hebing(t1); if(rem[temp1]==)
{
H=getH(t1);
rem[temp1]=;
fa[temp1]=temp;
que.push(state(G+H+,G+,temp1));
} swap(t1[x0][y0],t1[x0][y0+]);
}
} if(ok)
showans();
else
cout<<"unsolvable"<<endl;
}int main()
{
ios::sync_with_stdio(false); int m[][];
char c; while(cin>>c)
{
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-''; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cin>>c;
m[i][j]=c=='x'?:c-'';
} solve(m);
} return ;
}
双向A＊（曼哈顿距离）+康托+剪枝。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;const int maxn=;
const int Enum=;
const int jie[]={,,,,,,,,};
const int step[][]={{,},{,-},{-,},{,}};struct state
{
int F,G,num; state() {}
state(int a,int b,int c):F(a),G(b),num(c) {} friend bool operator < (state x,state y)
{
return x.F>y.F;
}
};int Snum,Mnum;
int fa[maxn],son[maxn];
int rem[maxn],Mrem;
char ans[maxn];int hebing(int (*m)[])
{
bool vis[]={};
int cou;
int ans=; for(int i=;i<;++i)
{
cou=;
for(int j=;j<m[i/][i%];++j)
if(vis[j])
++cou; vis[m[i/][i%]]=; ans+=(m[i/][i%]-cou)*jie[-i];
} return ans;
}void zhankai(int (*m)[],int x)
{
bool vis[]={};
int cou;
int k; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cou=x/jie[-*i-j]+; // !!!
x%=jie[-*i-j]; for(k=;k<&&cou;++k)
if(vis[k]==)
--cou; vis[k-]=; // !!!
m[i][j]=k-; // !!!
}
}void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}bool judge(int x,int y)
{
if(x<||y<||x>||y>)
return ; return ;
}void showans()
{
int cou=;
char c;
int tnum=Mnum; while(tnum!=Snum)
{
if(rem[tnum]==)
c='d';
else if(rem[tnum]==)
c='l';
else if(rem[tnum]==)
c='u';
else
c='r'; ans[cou++]=c; tnum=fa[tnum];
} for(int i=cou-;i>=;--i)
cout<<ans[i]; rem[Mnum]=Mrem;
tnum=Mnum; while(tnum!=Enum)
{
rem[tnum]=-rem[tnum];
if(rem[tnum]==)
c='u';
else if(rem[tnum]==)
c='r';
else if(rem[tnum]==)
c='d';
else
c='l'; cout<<c; tnum=son[tnum];
} cout<<endl;
}int getH(int (*m)[])
{
int H=; for(int i=;i<;++i)
for(int j=;j<;++j)
if(m[i][j])
H+=abs(i-(m[i][j]-)/)+abs(j-(m[i][j]-)%);
else
H+=abs(i-)+abs(j-); return H;
}bool bfs()
{
priority_queue <state> que1,que2; int temp,t1[][],t2[][];
int tnum1,tnum2;
int x01,y01,x02,y02; state tsta1,tsta2;
int H,G1,G2; que1.push(state(,,Snum));
que2.push(state(,,Enum)); rem[Snum]=;
rem[Enum]=-; son[Enum]=Enum;
fa[Snum]=Snum; while(!que1.empty()&&!que2.empty())
{
tsta1=que1.top();
tsta2=que2.top();
que1.pop();
que2.pop(); tnum1=tsta1.num;
tnum2=tsta2.num;
G1=tsta1.G;
G2=tsta2.G; zhankai(t1,tnum1);
zhankai(t2,tnum2); for(int i=;i<;++i)
for(int j=;j<;++j)
{
if(t1[i][j]==)
x01=i,y01=j;
if(t2[i][j]==)
x02=i,y02=j;
} for(int i=;i<;++i)
{
if(judge(x01+step[i][],y01+step[i][])==)
continue; swap(t1[x01][y01],t1[x01+step[i][]][y01+step[i][]]);
temp=hebing(t1); if(rem[temp]==)
{
rem[temp]=i+;
fa[temp]=tnum1;
H=getH(t1);
que1.push(state(H+G1+,G1+,temp));
}
else if(rem[temp]<)
{
fa[temp]=tnum1;
Mrem=rem[temp];
rem[temp]=i+;
Mnum=temp; return ;
} swap(t1[x01][y01],t1[x01+step[i][]][y01+step[i][]]);
} for(int i=;i<;++i)
{
if(judge(x02+step[i][],y02+step[i][])==)
continue; swap(t2[x02][y02],t2[x02+step[i][]][y02+step[i][]]);
temp=hebing(t2); if(rem[temp]==)
{
rem[temp]=-(i+);
son[temp]=tnum2;
H=getH(t2);
que2.push(state(H+G2+,G2+,temp));
}
else if(rem[temp]>)
{
son[temp]=tnum2;
Mrem=-(i+);
Mnum=temp; return ;
} swap(t2[x02][y02],t2[x02+step[i][]][y02+step[i][]]);
}
} return ;
}bool JiOujian(int (*m)[])
{
int ni=; for(int i=;i<;++i)
for(int j=;j<i;++j)
if(m[i/][i%]&&m[j/][j%])
if(m[i/][i%]<m[j/][j%])
++ni; return ni%;
}void solve(int (*m)[])
{
if(JiOujian(m))
{
cout<<"unsolvable\n";
return;
} memset(rem,,sizeof(rem)); Snum=hebing(m); if(Snum==Enum)
{
cout<<endl;
return;
} if(bfs())
showans();
else
cout<<"unsolvable\n";
}int main()
{
ios::sync_with_stdio(false); int m[][];
char c; while(cin>>c)
{
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-'';
cin>>c;
m[][]=c=='x'?:c-''; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cin>>c;
m[i][j]=c=='x'?:c-'';
} solve(m);
} return ;
}
IDA＊+剪枝。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>using namespace std;const int maxn=;
const int Enum=;
const int jie[]={,,,,,,,,};
const int Step[][]={{,},{,-},{-,},{,}};int ans[maxn];
int Deep;
int Node[][];
int x01,y01;void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}bool judge()
{
for(int i=;i<;++i)
for(int j=;j<;++j)
if(Node[i][j]&&Node[i][j]!=i*+j+)
return ; return ;
}bool JiOujian()
{
int ni=; for(int i=;i<;++i)
for(int j=;j<i;++j)
if(Node[i/][i%]&&Node[j/][j%])
if(Node[i/][i%]<Node[j/][j%])
++ni; return ni%;
}int getH()
{
int reH=; for(int i=;i<;++i)
for(int j=;j<;++j)
if(Node[i][j])
reH+=abs(i-(Node[i][j]-)/)+abs(j-(Node[i][j]-)%);
else
reH+=abs(-i)+abs(-j); return reH;
}void showans(int G)
{
for(int i=;i<G;++i)
if(ans[i]==)
cout<<'d';
else if(ans[i]==)
cout<<'l';
else if(ans[i]==)
cout<<'u';
else
cout<<'r'; cout<<endl;
}bool judgeBian(int x,int y)
{
if(x<||y<||x>||y>)
return ; return ;
}bool dfs(int G,int lasStep)
{
int H=getH(); if(H+G>Deep)
return ; if(judge())
{
showans(G);
return ;
} for(int i=;i<;++i)
{
if(i%==lasStep%&&i!=lasStep)
continue; if(judgeBian(x01+Step[i][],y01+Step[i][])==)
continue; swap(Node[x01][y01],Node[x01+Step[i][]][y01+Step[i][]]);
x01+=Step[i][];
y01+=Step[i][]; ans[G]=i; if(dfs(G+,i))
return ; x01-=Step[i][];
y01-=Step[i][];
swap(Node[x01][y01],Node[x01+Step[i][]][y01+Step[i][]]);
} return ;
}void solve()
{
if(JiOujian())
{
cout<<"unsolvable\n";
return;
} Deep=; while()
{
if(dfs(,-))
return; ++Deep;
}
}int main()
{
ios::sync_with_stdio(false); char c; while(cin>>c)
{
Node[][]=c=='x'?:c-'';
cin>>c;
Node[][]=c=='x'?:c-'';
cin>>c;
Node[][]=c=='x'?:c-''; for(int i=;i<;++i)
for(int j=;j<;++j)
{
cin>>c;
Node[i][j]=c=='x'?:c-'';
} for(int i=;i<;++i)
for(int j=;j<;++j)
if(Node[i][j]==)
x01=i,y01=j; solve();
} return ;
}
