用c++利用A*算法实现八数码难题(九宫重排)的搜索。

好的，我可以为您提供一个基于C++的A*算法实现八数码难题的搜索，以下是代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int tar_pos[10][2] = {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};

struct node
{
    int x, y;
    int step;
    int f;
    char p[3][3];
    bool operator < (const node& a) const
    {
        return f > a.f;
    }
};

char tar[3][3] = {{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '0'}};
bool vis[MAXN];
int dis[MAXN], pos[MAXN];
priority_queue<node> q;

inline int h(node& a)
{
    int cnt = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (a.p[i][j] != '0')
                cnt += abs(i - tar_pos[a.p[i][j] - '0'][0]) + abs(j - tar_pos[a.p[i][j] - '0'][1]);
    return cnt;
}

inline int get_id(node& a)
{
    int id = 0, base = 1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            pos[a.p[i][j] - '0'] = id++;
            id %= 9;
        }
    for (int i = 0; i < 9; i++)
    {
        int cnt = 0;
        for (int j = i + 1; j < 9; j++)
            if (pos[j] < pos[i])
                cnt++;
        id += cnt * base;
        base *= (9 - i);
    }
    return id;
}

int main()
{
    node st;
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    st.step = 0;
    st.f = h(st);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            cin >> st.p[i][j];
            if (st.p[i][j] == '0')
            {
                st.x = i;
                st.y = j;
            }
        }
    q.push(st);
    vis[get_id(st)] = true;
    dis[get_id(st)] = 0;

    while (!q.empty())
    {
        node t = q.top();
        q.pop();
        vis[get_id(t)] = false;
        if (t.f == t.step)
        {
            cout << t.step << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = t.x + dx[i];
            int ny = t.y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
            {
                node s = t;
                swap(s.p[t.x][t.y], s.p[nx][ny]);
                s.x = nx;
                s.y = ny;
                s.step = t.step + 1;
                s.f = s.step + h(s);
                int id = get_id(s);
                if (s.step < dis[id])
                {
                    dis[id] = s.step;
                    if (!vis[id])
                    {
                        vis[id] = true;
                        q.push(s);
                    }
                }
            }
        }
    }

    return 0;
}

该代码中，我们使用了优先队列来实现A*算法的搜索过程，通过`h()`函数来计算当前状态与目标状态之间的估价函数值，再通过优先队列来计算最优解。其中，get_id()函数用于计算当前状态的哈希值，防止重复搜索。

该代码通过输入一个初始状态，计算出最小步数，使得该状态可以通过移动1~8数字到0的位置，最终变成目标状态。

希望能够对您有所帮助！如果您还有其他问题，欢迎继续提问。