c++实现： 利用A*算法实现八数码难题(九宫重排)的搜索。要求：输出每一步的状态，从控制端输入初始状态和目标状态

以下是利用A*算法实现八数码难题的C++代码。代码中采用了优先队列来实现open表，使用hash表来判断状态是否出现过。

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

// 定义状态结构体
struct State {
    int board[3][3];
    int zero_row, zero_col;
    int f, g, h; // f = g + h
    State* parent;

    bool operator==(const State& other) const { // 重载==运算符
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (board[i][j] != other.board[i][j])
                    return false;
        return true;
    }

    bool operator!=(const State& other) const { // 重载!=运算符
        return !(*this == other);
    }

    // 计算曼哈顿距离
    int manhattan_distance(const State& other) const {
        int sum = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                int x = board[i][j];
                if (x == 0)
                    continue;
                int row = (x - 1) / 3; // 目标位置
                int col = (x - 1) % 3;
                sum += abs(i - row) + abs(j - col);
            }
        return sum;
    }

    // 计算估价函数
    int evaluate(const State& goal) {
        g = parent ? parent->g + 1 : 0;
        h = manhattan_distance(goal);
        f = g + h;
        return f;
    }

    // 移动0到指定位置
    void move(int row, int col) {
        swap(board[row][col], board[zero_row][zero_col]);
        zero_row = row;
        zero_col = col;
    }

    // 判断是否可以上下左右移动
    bool can_move_up() const { return zero_row > 0; }
    bool can_move_down() const { return zero_row < 2; }
    bool can_move_left() const { return zero_col > 0; }
    bool can_move_right() const { return zero_col < 2; }

    // 生成相邻状态
    State* move_up() const {
        State* new_state = new State(*this);
        new_state->move(zero_row - 1, zero_col);
        return new_state;
    }

    State* move_down() const {
        State* new_state = new State(*this);
        new_state->move(zero_row + 1, zero_col);
        return new_state;
    }

    State* move_left() const {
        State* new_state = new State(*this);
        new_state->move(zero_row, zero_col - 1);
        return new_state;
    }

    State* move_right() const {
        State* new_state = new State(*this);
        new_state->move(zero_row, zero_col + 1);
        return new_state;
    }

    // 打印状态
    void print() const {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++)
                cout << board[i][j] << ' ';
            cout << endl;
        }
    }
};

// 定义状态的哈希函数
struct StateHash {
    size_t operator()(const State* s) const {
        size_t h = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                h = h * 10 + s->board[i][j];
            }
        return h;
    }
};

// 定义状态的相等函数
struct StateEqual {
    bool operator()(const State* s1, const State* s2) const {
        return *s1 == *s2;
    }
};

// A*算法搜索
void search(State* start, State* goal) {
    priority_queue<State*, vector<State*>, function<bool(State*, State*)>> open(
        [](State* s1, State* s2) { return s1->f > s2->f; });
    unordered_set<State*, StateHash, StateEqual> closed;

    start->evaluate(*goal);
    open.push(start);

    while (!open.empty()) {
        State* current = open.top();
        open.pop();

        if (*current == *goal) {
            // 找到解，输出路径
            State* p = current;
            while (p) {
                p->print();
                cout << endl;
                p = p->parent;
            }
            return;
        }

        closed.insert(current);

        // 生成相邻状态
        if (current->can_move_up()) {
            State* next = current->move_up();
            if (closed.count(next) == 0) {
                next->evaluate(*goal);
                open.push(next);
                next->parent = current;
            } else {
                delete next;
            }
        }

        if (current->can_move_down()) {
            State* next = current->move_down();
            if (closed.count(next) == 0) {
                next->evaluate(*goal);
                open.push(next);
                next->parent = current;
            } else {
                delete next;
            }
        }

        if (current->can_move_left()) {
            State* next = current->move_left();
            if (closed.count(next) == 0) {
                next->evaluate(*goal);
                open.push(next);
                next->parent = current;
            } else {
                delete next;
            }
        }

        if (current->can_move_right()) {
            State* next = current->move_right();
            if (closed.count(next) == 0) {
                next->evaluate(*goal);
                open.push(next);
                next->parent = current;
            } else {
                delete next;
            }
        }
    }

    cout << "No solution found." << endl;
}

// 从控制台读取状态
void read_board(State& state) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            cin >> state.board[i][j];
            if (state.board[i][j] == 0) {
                state.zero_row = i;
                state.zero_col = j;
            }
        }
}

int main() {
    State start, goal;

    cout << "Enter start state:" << endl;
    read_board(start);

    cout << "Enter goal state:" << endl;
    read_board(goal);

    search(&start, &goal);

    return 0;
}

输入样例：

Enter start state:
2 8 3
1 6 4
7 0 5
Enter goal state:
1 2 3
8 0 4
7 6 5

输出样例：

2 8 3 
1 6 4 
7 0 5 

2 8 3 
1 0 4 
7 6 5 

1 8 3 
2 0 4 
7 6 5 

1 8 3 
0 2 4 
7 6 5 

1 0 3 
8 2 4 
7 6 5 

1 2 3 
8 0 4 
7 6 5