八数码问题c++可视化

八数码问题是一个经典的搜索问题，可以使用C++和可视化工具来实现。以下是一个简单的实现：

#include <iostream>
#include <iomanip>
#include <queue>
#include <unordered_set>

using namespace std;

// 定义状态结构体
struct State {
    int board[3][3];
    int zero_row, zero_col;
    int move; // 移动的方向，0表示不动，1表示上，2表示下，3表示左，4表示右
    State() {};
    State(const State& other) {
        memcpy(this->board, other.board, sizeof(board));
        this->zero_row = other.zero_row;
        this->zero_col = other.zero_col;
        this->move = other.move;
    }
    bool operator==(const State& other) const {
        return memcmp(board, other.board, sizeof(board)) == 0;
    }
};

// 定义哈希函数
struct Hash {
    size_t operator()(const State& state) const {
        size_t h = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                h = h * 10 + state.board[i][j];
            }
        }
        return h;
    }
};

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

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

// 判断状态是否合法
bool is_valid(const State& state) {
    int inv = 0;
    int a[9];
    int k = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            a[k++] = state.board[i][j];
        }
    }
    for (int i = 0; i < 9; i++) {
        if (a[i] == 0) {
            continue;
        }
        for (int j = 0; j < i; j++) {
            if (a[j] == 0) {
                continue;
            }
            if (a[j] > a[i]) {
                inv++;
            }
        }
    }
    return inv % 2 == 0;
}

// 计算启发函数
int heuristic(const State& state) {
    int h = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (state.board[i][j] == 0) {
                continue;
            }
            int x = (state.board[i][j] - 1) / 3;
            int y = (state.board[i][j] - 1) % 3;
            h += abs(i - x) + abs(j - y);
        }
    }
    return h;
}

// 打印状态
void print_state(const State& state) {
    cout << "Move: " << state.move << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << setw(2) << state.board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// 搜索函数
int solve(State& start_state) {
    unordered_set<State, Hash> visited;
    priority_queue<pair<int, State>> pq;
    start_state.move = 0;
    visited.insert(start_state);
    pq.push({-heuristic(start_state), start_state});
    while (!pq.empty()) {
        State state = pq.top().second;
        pq.pop();
        if (memcmp(state.board, target_board, sizeof(target_board)) == 0) {
            // 打印解
            vector<State> path;
            while (state.move != 0) {
                path.push_back(state);
                state = path.back();
            }
            path.push_back(state);
            for (int i = path.size() - 1; i >= 0; i--) {
                print_state(path[i]);
            }
            return path.size() - 1;
        }
        int zero_x = state.zero_row;
        int zero_y = state.zero_col;
        for (int i = 1; i <= 4; i++) {
            int new_zero_x = zero_x + dx[i];
            int new_zero_y = zero_y + dy[i];
            if (new_zero_x < 0 || new_zero_x >= 3 || new_zero_y < 0 || new_zero_y >= 3) {
                continue;
            }
            State new_state = state;
            swap(new_state.board[zero_x][zero_y], new_state.board[new_zero_x][new_zero_y]);
            new_state.zero_row = new_zero_x;
            new_state.zero_col = new_zero_y;
            new_state.move = i;
            if (visited.count(new_state) == 0) {
                visited.insert(new_state);
                pq.push({-heuristic(new_state), new_state});
            }
        }
    }
    return -1;
}

int main() {
    State start_state;
    cout << "请输入初始状态（用空格分隔数字，0表示空格）：" << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> start_state.board[i][j];
            if (start_state.board[i][j] == 0) {
                start_state.zero_row = i;
                start_state.zero_col = j;
            }
        }
    }
    if (!is_valid(start_state)) {
        cout << "无解" << endl;
        return 0;
    }
    int steps = solve(start_state);
    if (steps == -1) {
        cout << "无解" << endl;
    } else {
        cout << "步数：" << steps << endl;
    }
    return 0;
}

这个实现中使用了哈希表和启发式搜索来加速搜索过程，并且支持任意初始状态的输入。可以使用Qt等可视化工具来实现界面交互部分。