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

以下是C++中使用A*算法解决八数码难题的完整代码：

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

// 定义八数码矩阵大小
const int N = 3;

// 定义八数码矩阵
int matrix[N][N];

// 定义目标状态
int target[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};

// 定义节点类
class Node {
public:
    int matrix[N][N];
    int step;
    int f;
    int x, y;
    Node() {}
    Node(int m[N][N], int s, int fx, int fy) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = m[i][j];
            }
        }
        step = s;
        x = fx;
        y = fy;
        f = step + h();
    }
    int h() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 0) continue;
                int x = (matrix[i][j] - 1) / N;
                int y = (matrix[i][j] - 1) % N;
                cnt += abs(i - x) + abs(j - y);
            }
        }
        return cnt;
    }
    bool operator < (const Node& t) const {
        return f > t.f;
    }
};

// 定义状态映射
map<vector<int>, int> mp;

// 定义方向数组
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

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

// 搜索函数
int AStar() {
    priority_queue<Node> pq;
    Node start(matrix, 0, 0, 0);
    pq.push(start);
    mp[vector<int>(start.matrix[0], start.matrix[0] + N * N)] = 1;
    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        if (memcmp(t.matrix, target, sizeof(t.matrix)) == 0) {
            return t.step;
        }
        for (int i = 0; i < 4; i++) {
            int nx = t.x + dx[i];
            int ny = t.y + dy[i];
            if (check(nx, ny)) {
                Node next(t.matrix, t.step + 1, nx, ny);
                swap(next.matrix[t.x][t.y], next.matrix[nx][ny]);
                vector<int> v(next.matrix[0], next.matrix[0] + N * N);
                if (mp[v] == 0) {
                    mp[v] = 1;
                    pq.push(next);
                }
            }
        }
    }
    return -1;
}

int main() {
    // 输入八数码矩阵
    cout << "请输入八数码矩阵：" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> matrix[i][j];
        }
    }
    // A*算法搜索
    int ans = AStar();
    // 输出结果
    cout << "最少需要移动 " << ans << " 步" << endl;
    return 0;
}

在代码中，我们首先定义了八数码矩阵的大小和目标状态，然后定义了一个节点类，其中包括当前状态的矩阵、步数、估价函数f值、0的位置坐标等信息。在搜索函数中，我们使用了一个优先队列来存储节点，每次取出f值最小的节点进行扩展，并将扩展出的节点加入队列中。在扩展节点时，我们按照上、右、下、左的顺序进行扩展，并判断是否合法。如果扩展出的节点未出现过，则将其加入优先队列中，并将其状态矩阵加入状态映射中。最后，如果搜索到了目标状态，则返回步数，否则返回-1表示无解。