问题描述

八数码问题。不清楚的可以百度一下

输入

总共一行,9个数,按位置顺序依次给出。
如果它是x则代表该位置是空的。

输出

如果该情况无解输出’unsolvable’
否则输出操作方案,对于一次操作输出一个字母。
u,d,l,r四个字母分别对应向上,下,左,右移动。

思路

八数码问题当然是用搜索去解啦。

首先考虑有解的情况。裸的搜索肯定是会TLE的,于是这道题可以使用启发式搜索。启发式搜索的重点便是估值函数,这道题估值函数有两种设计方法。

第一种是当前状态与目标状态不同的数字数,详细见代码吧:

int h()
{
    int cnt=0;
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            if(map[i][j]!=aim[i][j]) cnt++ //map为当前状态,aim为目标状态
    return cnt;
}

第二种是当前状态到目标状态数字需要移动的曼哈顿距离之和,显然第二种的估值函数是更加准确的,代码:

int h()
{
    int cnt=0, nx[9], ny[9];
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            nx[map[i][j]]=i;
            ny[map[i][j]]=j;
        }
    }
    for(int i=1; i<9; i++) cnt+=abs(nx[i]-hx[i])+abs(ny[i]-hy[i]);
    return cnt;
}

估值函数设计好了,实现应该就不难了。考虑到代码量和效率,IDA* 是更优秀的。

还要注意特判无解的情况,如果该情况序列的逆序数是奇数则无解,原因每一次移动都会增加或减少2个逆序数。

细节

  1. 要注意无解的特判 其实该题数据没有unsolvable的数据
  2. 自己写的距离数组不要弄错了

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int dx[5]={1, 0, -1, 0}, dy[5]={0, -1, 0, 1};
const int hx[9]={3, 1, 1, 1, 2, 2, 2, 3, 3}, hy[9]={3, 1, 2, 3, 1, 2, 3, 1, 2};

int map[5][5], act[100], ans, sx, sy;
char temp;
bool flag;

int h() //估值函数
{
    int cnt=0, nx[9], ny[9];
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            nx[map[i][j]]=i;
            ny[map[i][j]]=j;
        }
    }
    for(int i=1; i<9; i++) cnt+=abs(nx[i]-hx[i])+abs(ny[i]-hy[i]);
    return cnt;
}

void print() //输出答案
{
    for(int i=0; ians || flag)  return;
    if(h()==0)  {flag=1; print(); return;}
    for(int i=0; i<4; i++)
    {
        int rx=x+dx[i], ry=y+dy[i];
        if(rx<1 || ry<1 || rx>3 || ry>3)  continue;
        act[g]=i;
        swap(map[x][y], map[rx][ry]);
        dfs(rx, ry, g+1);
        swap(map[x][y], map[rx][ry]);
    }
}

bool unsolve()
{
    int cnt=0;
    for(int i=1; i<=3; i++) for(int j=1; j<=3; j++)
    {
        if(map[i][j]==0) continue;
        for(int x=1; x<=i; x++) for(int y=1; y<=3; y++)
        {
            if(x==i && y>=j) break;
            if(map[x][y]==0) continue;
            if(map[x][y]>map[i][j]) cnt++;
        }
    }
    return cnt%2;
}

int main()
{
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            cin>>temp;
            if(temp=='x') sx=i, sy=j;
            else map[i][j]=temp-'0';
        }
    }
    if(unsolve()) {printf("unsolvable\n"); return 0;} //无解特判
    for(ans=0; ; ans++) //迭代加深
    {
        dfs(sx, sy, 0);
        if(flag) break;
    }
} 

发表评论

邮箱地址不会被公开。 必填项已用*标注