多种方式解决八数码问题
八方块移动游戏要求从一个含 8 个数字（用 1-8 表示）的方块以及一个空格方块（用 0 表示）的 3 × 3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2个方向可移动，在其他位置上有 3 个方向可移动。例如，假设一个 3× 3 矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
8 0 3 > 8 1 3 > 8 1 3 > 0 1 3 > 1 0 3 > 1 2 3
2 1 4 > 2 0 4 > 0 2 4 > 8 2 4 > 8 2 4 > 8 0 4
7 6 5 > 7 6 5 > 7 6 5 > 7 6 5 > 7 6 5 > 7 6 5
另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为 5 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径。
input
程序需读入初始状态和目标状态，这两个状态都由 9 个数字组成（ 0 表示空格， 1-8 表示 8个数字方块），每行 3 个数字，数字之间用空格隔开。
output
如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出 -1
sample input
8 0 3
2 1 4
7 6 5
1 2 3
8 0 4
7 6 5
sample output
5
这个题做法很多,主要有以下几类
1：BFS，难点在状态的存储，及如何判重，最简单的方式是用逻辑数组，可以开8维数组
对应程序为入门OJ２４２６
#include <bits/stdc++.h>
using namespace std;
struct Point
{
char a[3][3],x,y,step;
};
Point q[100000],s,t;
bool used[9][9][9][9][9][9][9][9];
int f=1,e=0;
bool check(Point u,Point v)
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(u.a[i][j]!=v.a[i][j]) return 0;
return 1;
}
Point gen(Point u,int type)
{
Point v=u;
v.step=u.step+1;
if(type==1&&v.x!=0)
{
swap(v.a[v.x][v.y],v.a[v.x-1][v.y]);
v.x--;
}
else if(type==2&&v.x!=2)
{
swap(v.a[v.x][v.y],v.a[v.x+1][v.y]);
v.x++;
}
else if(type==3&&v.y!=0)
{
swap(v.a[v.x][v.y],v.a[v.x][v.y-1]);
v.y--;
}
else if(type==4&&v.y!=2)
{
swap(v.a[v.x][v.y],v.a[v.x][v.y+1]);
v.y++;
}
return v;
}
int main()
{
memset(used,0,sizeof(used));
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
int tmp;
cin>>tmp;
s.a[i][j]=tmp;
if(s.a[i][j]==0)
{
s.x=i,s.y =j;
}
}
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
int tmp;
cin>>tmp;
t.a[i][j]=tmp;
}
if(check(s,t))
{
cout<<0<<endl;
return 0;
}
e++;
q[e]=s;
s.step =0;
used[s.a[0][0]][s.a[0][1]][s.a[0][2]][s.a[1][0]][s.a[1][1]][s.a[1][2]][s.a[2][0]][s.a[2][1]]=1;
while(f<=e)
{
Point u=q[f];
f++;
for(int i=1;i<=4;i++)
{
Point v=gen(u,i);
if(used[v.a[0][0]][v.a[0][1]][v.a[0][2]][v.a[1][0]][v.a[1][1]][v.a[1][2]][v.a[2][0]][v.a[2][1]]==1)
continue;
if(check(v,t))
{
cout<<(int)v.step;
return 0;
}
if(v.step >=20) continue;
e++;
q[e]=v;
used[v.a[0][0]][v.a[0][1]][v.a[0][2]][v.a[1][0]][v.a[1][1]][v.a[1][2]][v.a[2][0]][v.a[2][1]]=1;
}
}
cout<<"No solution!"<<endl;
return 0;
}
2：使用MAP来进行存储
#include<bits/stdc++.h>
#define for(i,a,b) for(int i=a;i<=b;i++)//宏定义，很好用
using namespace std;
string x,y;
bool mp[9][9][9][9][9][9][9][9][9];
map<string,int> sj;
//map映射标记
queue<string> q;
//队列，BFS标配
int dir[9][4]={-1,-1,3,1, -1,0,4,2, -1,1,5,-1, 0,-1,6,4, 1,3,7,5, 2,4,8,-1, 3,-1,-1,7, 4,6,-1,8, 5,7,-1,-1};
//-1代表越界，按上左下右四个方向进行交换，与哪个位置进行交换
//例如对于[-1,-1,3,1]代表当0在目前第0个位置上即最左上角那个位置时
//如果向上走出界，向左走出界，向下走与第3个位置上的字符进行交换，
//向右走与第1个位置上的字符进行交换
void bfs(string a)
{
sj[a]=1;
q.push(a);
while(!q.empty())
{
int b;
a=q.front();
q.pop();
if(a==y)
{
cout<<sj[a]-1;
return;
}//因为初始状态为1，所以要减一
for(i,0,a.size()-1)
{
if(a[i]=='0')b=i;//记0的位置
}
for(i,0,3)
{
string aa=a;
if(dir[b][i]==-1)continue;//下标无效
swap(aa[b],aa[dir[b][i]]);//交换
if(sj[aa]==0)
{
sj[aa]=sj[a]+1;//步数加一
q.push(aa);//入队列
}
}
}
cout<<-1;//不行就输出-1
}
int main()
{
for(i,1,3)
for(j,1,3)
{
char a;
cin>>a;
x+=a; //字符串存储
}
for(i,1,3)
for(j,1,3)
{
char a;
cin>>a;
y+=a; //字符串存储
}
bfs(x);//开始搜索
return 0;
}
为了节省空间还可以使用康托展开，其实是种特殊的hash技术。
#include <iostream>
#include <cstring>
#define LEN 362888 //状态共9!=362880种
using namespace std;
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int visited[LEN]; //状态标记，步骤记录
int dis[LEN];
int state[LEN][9]; //状态池
int goal[9]; //目标状态
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};
bool Contor(int str[], int n)
{
long result = 0;
for(int i = 0; i < n; i++)
{
int counted = 0;
for(int j = i+1; j < n; j++)
{
if(str[i] > str[j]) //当前未出现的元素中是排在第几个
++counted;
}
result += counted*factory[n-i-1];
}
if(!visited[result]) //没有被访问过
{
visited[result] = 1;
return 1;
}
else
return 0;
}
int bfs()
{
int head = 1, tail = 2;
//为了节省空间，不用队列存储各个状态
int i;
while(head < tail)
//枚举完全部状态退出循环
{
//检查是否到达目标状态
for(i = 0; i < 9; i++)
{
if(state[head][i] != goal[i])
break;
}
if(i == 9)
return head;
//找到元素0
for(i = 0; i < 9; i++)
{
if(state[head][i] == 0)
break;
}
//转化为二维
int x = i/3;
int y = i%3;
int z = i;
for(i = 0; i < 4; i++)
{
//新的坐标
int nx = x+dir[i][0];
int ny = y+dir[i][1];
//转化为一维
int nz = 3*nx+ny;
if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3) //未越界
{
for(int j = 0; j < 9; j++)
state[tail][j] = state[head][j];
swap(state[tail][z], state[tail][nz]);
// for(int i = 0; i < 9; i++)
// cout << state[tail][i] ;
// cout << endl;
dis[tail] = dis[head]+1;
if(Contor(state[tail], 9)) //新状态未出现过
//cout << 1 << endl,
tail++; //队列长度+1,相当于入队
}
}
head++; //队列长度-1，相当于出队
}
return 0;
}
int main()
{
for(int i = 0; i < 9; i++)
cin >> state[1][i]; //初始状态
for(int i = 0; i < 9; i++)
cin >> goal[i]; //目标状态
int num = bfs();
if(num)
if (dis[num]<=20)
cout << dis[num] << endl;
else
printf("No solution!
");
return 0;
}
有兴趣的还可以写下循环队列或者双向BFS。。
2：使用单向DFS可以不用存状态，但要加各种优化，例如IDA*
下面程序为入门OJ2426
三行三列的数组，其元素值为0至8的数。现有如下的变换规则：
1： 将0与上面一行元素对换
2：将0与下面一行元素对换
3：将0与左面一行元素对换
4：将0与右面一行元素对换
如果已知一个三行三列元素的初始情况，问最少需几次变换，能变换为指定的一种情况？
输入
包括六行的数据，每行有三个以空格分隔的数字。 前三行为原始状态 后三行为目标状态
输出
若能在20次以内（包括20）变换得到目标状态的数组,输出最少的变换次数; 若不能在20次以内（包括20）变换得到目标状态的数组，输出No solution!
样例输入
0 4 8
2 6 3
1 7 5
0 2 3
1 8 4
7 6 5
样例输出
10
#include<bits/stdc++.h>
using namespace std;
typedef long long lt;
int read(){
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
int ans[4][4];
int a[5][5],k,judge;
int nxtx[]={0,1,-1,0};
int nxty[]={1,0,0,-1};
int check()
{
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
if(ans[i][j]!=a[i][j])return 0;
return 1;
}
int test(int step)
{
int cnt=0;
for(int i=1;i<=3;++i) //看有多少字符不在目标位置上，以此做为估价函数
for(int j=1;j<=3;++j)
if(ans[i][j]!=a[i][j])
{ if(++cnt+step>k)
return 0;
}
return 1;
}
void A_star(int step,int x,int y,int pre)
//step为深度，x,y为0的位置，Pre为上一步的操作编号，因为来回操作是没有意义的。
{
if(step==k)
{
if(check())
judge=1;
return;
}
if(judge)
return;
for(int i=0;i<4;++i)
{
int nx=x+nxtx[i],ny=y+nxty[i];
if(nx<1||nx>3||ny<1||ny>3||pre+i==3)continue;
swap(a[x][y],a[nx][ny]);
if(test(step)&&!judge)
A_star(step+1,nx,ny,i);
swap(a[x][y],a[nx][ny]);
}
}
int main()
{
int x,y;
for(int i=0;i<9;++i)
{
a[i/3+1][i%3+1]=read();
if(a[i/3+1][i%3+1]==0)
x=i/3+1,y=i%3+1;
}
for(int i=0;i<9;++i)
ans[i/3+1][i%3+1]=read();
if(check())
{
return printf("0"),0;
}
while(++k)
{
if(k>20)
{
return printf("No solution!"),0;
}
A_star(0,x,y,-1);
if(judge){printf("%d",k);break;}
}
return 0;
}
还可以双向DFS，用MAP存状态
//双向DFS，先出发状态一次，将找到的状态放到MAP中
//限定深度只找10层
//再结束状态DFS一次，看找出来的状态是否在MAP中出现
#include<bits/stdc++.h>
using namespace std;
inline void swap(int&c,int&d){c=c+d;d=c-d;c=c-d;}
int a[4][4],b[4][4];
map<int,int>s1;
int ans=21;
int t;
void dfsa(int p[4][4],int dep,int h,int l)
{
t=0;
for(int i=1,j=1;i<=9;i++,j*=10)
t+=p[(i-1)/3+1][(i-1)%3+1]*j;
if(!s1[t]||s1[t]>dep)
s1[t]=dep;
if(dep==10)return;
if(h>1){
swap(p[h][l],p[h-1][l]);
dfsa(p,dep+1,h-1,l);
swap(p[h][l],p[h-1][l]);
}
if(h<3){
swap(p[h][l],p[h+1][l]);
dfsa(p,dep+1,h+1,l);
swap(p[h][l],p[h+1][l]);
}
if(l>1){
swap(p[h][l],p[h][l-1]);
dfsa(p,dep+1,h,l-1);
swap(p[h][l],p[h][l-1]);
}
if(l<3){
swap(p[h][l],p[h][l+1]);
dfsa(p,dep+1,h,l+1);
swap(p[h][l],p[h][l+1]);
}
}
void dfsb(int p[4][4],int dep,int h,int l)
{
t=0;
for(int i=1,j=1;i<=9;i++,j*=10)
t+=p[(i-1)/3+1][(i-1)%3+1]*j;
if(s1[t])
ans=min(s1[t]+dep,ans);
if(dep==10)
return;
if(h>1){
swap(p[h][l],p[h-1][l]);
dfsb(p,dep+1,h-1,l);
swap(p[h][l],p[h-1][l]);
}
if(h<3){
swap(p[h][l],p[h+1][l]);
dfsb(p,dep+1,h+1,l);
swap(p[h][l],p[h+1][l]);
}
if(l>1){
swap(p[h][l],p[h][l-1]);
dfsb(p,dep+1,h,l-1);
swap(p[h][l],p[h][l-1]);
}
if(l<3){
swap(p[h][l],p[h][l+1]);
dfsb(p,dep+1,h,l+1);
swap(p[h][l],p[h][l+1]);
}
}
void put(){printf("No solution!
");}
main()
{
// freopen("8.in","r",stdin);
// freopen("8.out","w",stdout);
int T,F;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)
T=i,F=j;
}
dfsa(a,0,T,F);
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
{
scanf("%d",&b[i][j]);
if(b[i][j]==0)
T=i,F=j;
}
dfsb(b,0,T,F);
bool flag=1;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(a[i][j]!=b[i][j])
flag=0;
if(flag)
{
printf("0
");
return 0;
}
if(ans<21)
printf("%d
",ans);
else
put();
}