将很庞大的一个搜索范围收缩在一个很小的区域内
需要用到启发函数
启发函数是一个需要动脑筋好好想的一个函数

用A*算法解决八数码问题：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef pair<int,string> pis;

char op[5] = "urdl";
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};

int f(string state)     //启发函数
{
    int res = 0;
    for(int i = 0;i < state.size();i ++)
        if(state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }

    return res;
}

string bfs(string start)
{
    string end = "12345678x";
    map<string,int> dis;
    map<string,pair<char,string>> path;
    priority_queue<pis,vector<pis>,greater<pis>> h;

    dis[start] = 0;
    h.push({f(start),start});

    while(h.size())
    {
        pis t = h.top();
        h.pop();

        string state = t.second;    

        if(state == end)
            break;

        int x,y;
        for(int i = 0;i < 9;i ++)
            if(state[i] == 'x')
                x = i / 3,y = i % 3;

        string source = state;
        for(int i = 0;i < 4;i ++)
        {
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                state = source;
                swap(state[x * 3 + y],state[a * 3 + b]);
                if(!dis.count(state) || dis[state] > dis[source] + 1)
                {
                    dis[state] = dis[source] + 1;
                    path[state] = {op[i],source};
                    h.push({dis[state] + f(state),state});
                }
            }
        }

    }

    string res;
    while(end != start)
    {
        res += path[end].first;
        end = path[end].second;
    }
    reverse(res.begin(),res.end());

    return res;
}

int main()
{
    string start,seq;
    for(int i = 0;i < 9;i ++)
    {
        char c;
        cin >> c;

        start += c;

        if(c != 'x')
            seq += c;
    }

    int cnt = 0;
    for(int i = 0;i < 8;i ++)
        for(int j = i;j < 8;j ++)
            if(seq[i] > seq[j]) 
                cnt ++;

    if(cnt & 1)
        cout << "unsolvable";
    else
        cout << bfs(start);

    return 0;
}