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

好的，这是一个经典的搜索问题，下面是一个用C++实现的A*算法解决八数码难题的示例代码：

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

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

struct node{
    int a[3][3], f, g, h;
    bool operator < (const node &rhs) const {
        return f > rhs.f;
    }
};

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int h(node u){
    int res = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if(u.a[i][j] == 0) continue;
            res += abs(i - (u.a[i][j] - 1) / 3) + abs(j - (u.a[i][j] - 1) % 3);
        }
    }
    return res;
}

bool check(node u){
    int cnt = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < i; k++){
                for(int l = 0; l < 3; l++){
                    if(u.a[i][j] == u.a[k][l] && u.a[i][j] != 0) cnt++;
                }
            }
        }
    }
    if(cnt % 2 == 0) return true;
    else return false;
}

node start, goal;
int vis[MAXN], fa[MAXN];

void print(node u){
    if(fa[u.f] == -1) return;
    print(fa[u.f]);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cout << u.a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int Astar(){
    memset(vis, 0, sizeof(vis));
    memset(fa, -1, sizeof(fa));
    priority_queue<node> q;
    start.f = h(start);
    start.g = 0;
    start.h = h(start);
    q.push(start);
    while(!q.empty()){
        node u = q.top();
        q.pop();
        if(vis[u.f]) continue;
        vis[u.f] = 1;
        if(u.f == goal.f){
            print(u);
            return u.g;
        }
        for(int k = 0; k < 4; k++){
            int nx = dx[k] + (u.a[0][0] == 0 ? 1 : 0), ny = dy[k] + (u.a[0][0] == 0 ? 1 : 0);
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3){
                node v = u;
                swap(v.a[nx][ny], v.a[0][0]);
                v.f = v.g + h(v);
                v.g++;
                if(!vis[v.f]){
                    fa[v.f] = u.f;
                    q.push(v);
                }
            }
        }
    }
    return -1;
}

int main(){
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> start.a[i][j];
            if(start.a[i][j] == 0) start.a[i][j] = 9;
        }
    }
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> goal.a[i][j];
            if(goal.a[i][j] == 0) goal.a[i][j] = 9;
        }
    }
    start.f = h(start);
    goal.f = h(goal);
    if(!check(start) || !check(goal)){
        cout << "No solution" << endl;
        return 0;
    }
    int res = Astar();
    if(res == -1) cout << "No solution" << endl;
    else cout << res << endl;
    return 0;
}

这段代码实现了八数码难题的A*算法搜索，其中h函数用于计算状态u到目标状态goal的估价函数值，check函数用于判断初始状态和目标状态是否能够到达，print函数用于输出最短路径，Astar函数用于实现A*算法搜索，主函数中首先读入初始状态和目标状态，然后进行一些必要的初始化，最后调用Astar函数进行搜索。