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

好的，以下是基于A*算法实现八数码难题的C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

// 定义状态结构体
struct State {
    vector<int> board; // 当前状态的棋盘
    int space; // 空格位置
    int cost; // 当前状态的代价
    int estimate; // 估计代价
    int pre; // 父状态的索引
};

// 定义比较函数，用于优先队列中的排序
struct Compare {
    bool operator()(State &a, State &b) {
        return a.cost + a.estimate > b.cost + b.estimate;
    }
};

// 定义全局变量
const int N = 3; // 棋盘边长
const int SIZE = 9; // 棋盘大小
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<State> states; // 状态数组
priority_queue<State, vector<State>, Compare> q; // 优先队列
map<vector<int>, int> mp; // 哈希表

// 判断状态是否合法
bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 计算当前状态的估计代价
int calcEstimate(vector<int> &board) {
    int res = 0;
    for (int i = 0; i < SIZE; i++) {
        if (board[i] == SIZE) continue;
        int x = i / N, y = i % N;
        int nx = (board[i] - 1) / N, ny = (board[i] - 1) % N;
        res += abs(x - nx) + abs(y - ny);
    }
    return res;
}

// 打印路径
void print(int cur) {
    if (states[cur].pre != -1) print(states[cur].pre);
    for (int i = 0; i < SIZE; i++) {
        cout << states[cur].board[i] << " ";
        if (i % N == N - 1) cout << endl;
    }
    cout << endl;
}

void solve() {
    // 初始化起始状态
    State s;
    s.board.resize(SIZE);
    for (int i = 0; i < SIZE; i++) {
        cin >> s.board[i];
        if (s.board[i] == SIZE) s.space = i;
    }
    s.cost = 0;
    s.estimate = calcEstimate(s.board);
    s.pre = -1;
    states.push_back(s);
    mp[s.board] = 0;
    q.push(s);

    // A*算法
    while (!q.empty()) {
        State cur = q.top();
        q.pop();
        if (cur.estimate == 0) {
            // 找到目标状态，打印路径
            print(states.size() - 1);
            return;
        }
        int x = cur.space / N, y = cur.space % N;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (isValid(nx, ny)) {
                int npos = nx * N + ny;
                State next = cur;
                swap(next.board[cur.space], next.board[npos]);
                next.space = npos;
                if (mp.find(next.board) == mp.end()) {
                    // 新状态，加入状态数组和哈希表
                    next.cost = cur.cost + 1;
                    next.estimate = calcEstimate(next.board);
                    next.pre = states.size() - 1;
                    states.push_back(next);
                    mp[next.board] = states.size() - 1;
                    q.push(next);
                } else {
                    // 已存在的状态，更新代价
                    int idx = mp[next.board];
                    if (states[idx].cost > cur.cost + 1) {
                        states[idx].cost = cur.cost + 1;
                        states[idx].pre = states.size() - 1;
                        q.push(states[idx]);
                    }
                }
            }
        }
    }
}

int main() {
    solve();
    return 0;
}

以上代码实现了A*算法求解八数码难题，其中包括求解过程中的估价函数、哈希表以及优先队列等重要操作。在实际应用中，可以通过修改估价函数来改进搜索效率，也可以使用其他搜索算法如IDA*等。