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

下面是一个用C++实现的八数码问题A*算法搜索代码，其中使用了曼哈顿距离作为估价函数：

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

// 数码状态结构体
struct Node {
    int state[3][3];
    int x, y;   // 空格的位置
    int f, g, h;    // f=g+h
    Node *father;   // 父状态指针

    // 构造函数
    Node(int s[3][3], int x, int y, int g, Node *father) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                state[i][j] = s[i][j];
        this->x = x;
        this->y = y;
        this->g = g;
        this->h = 0;
        this->father = father;
        calcH();    // 计算估价函数值
        calcF();    // 计算f值
    }

    // 拷贝构造函数
    Node(const Node &rhs) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                state[i][j] = rhs.state[i][j];
        this->x = rhs.x;
        this->y = rhs.y;
        this->g = rhs.g;
        this->h = rhs.h;
        this->father = rhs.father;
        calcF();
    }

    // 计算估价函数值
    void calcH() {
        int cnt = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                if (state[i][j] == 0) continue;
                int x = (state[i][j] - 1) / 3;
                int y = (state[i][j] - 1) % 3;
                cnt += abs(x - i) + abs(y - j);
            }
        this->h = cnt;
    }

    // 计算f值
    void calcF() {
        this->f = this->g + this->h;
    }
};

// 重载小于运算符，用于优先队列排序
bool operator < (Node a, Node b) {
    return a.f > b.f;
}

// 判断状态是否合法
bool isLegal(Node *p) {
    int cnt = 0;
    for (int i = 0; i < 9; i++) {
        int x1 = i / 3, y1 = i % 3;
        if (p->state[x1][y1] == 0) continue;
        for (int j = i + 1; j < 9; j++) {
            int x2 = j / 3, y2 = j % 3;
            if (p->state[x2][y2] == 0) continue;
            if (p->state[x1][y1] > p->state[x2][y2]) cnt++;
        }
    }
    return cnt % 2 == 0;
}

// 判断状态是否为目标状态
bool isGoal(Node *p) {
    int cnt = 1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            if (cnt == 9) return true;
            if (p->state[i][j] != cnt++) return false;
        }
    return true;
}

// 打印状态
void printState(Node *p) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << p->state[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// A*算法搜索
void AStar(Node *start) {
    priority_queue<Node> open;  // open表，按f值从小到大排序
    map<string, bool> closed;   // closed表，用于判重

    open.push(*start);
    closed[string((char *)start->state, 9)] = true;

    while (!open.empty()) {
        Node cur = open.top();
        open.pop();

        if (isGoal(&cur)) {
            cout << "Find the goal state:" << endl;
            printState(&cur);
            return;
        }

        // 生成下一层状态
        int dx[] = {0, 0, -1, 1};
        int dy[] = {-1, 1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;

            Node next(cur);
            swap(next.state[cur.x][cur.y], next.state[nx][ny]);
            next.x = nx;
            next.y = ny;
            next.g++;
            next.father = &cur;

            // 判断状态是否合法和是否已经访问过
            if (isLegal(&next) && !closed[string((char *)next.state, 9)]) {
                open.push(next);
                closed[string((char *)next.state, 9)] = true;
            }
        }
    }

    cout << "Can't find the goal state!" << endl;
}

int main() {
    // 初始状态
    int startState[3][3] = {
        {2, 8, 3},
        {1, 6, 4},
        {7, 0, 5}
    };

    Node *start = new Node(startState, 1, 2, 0, NULL);
    AStar(start);

    return 0;
}

注意，在该代码中，使用了一个`map`容器来进行状态的判重。此外，为了使用`map`容器，还需要重载`Node`结构体的`<`运算符和构造函数。