用c++实现用有界深度优先搜索解决八数码难题

好的，下面是用 C++ 实现用有界深度优先搜索解决八数码难题的代码：

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

const int N = 3; // 拼图块的维度
const int MAX_DEPTH = 50; // 最大搜索深度

struct State {
    int board[N][N]; // 拼图块的当前状态
    int zero_row, zero_col; // 空格的位置
    int depth; // 当前状态的深度
    State *prev; // 前一状态
};

// 判断当前状态是否为目标状态
bool is_goal(State *s) {
    int num = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == N-1 && j == N-1) {
                if (s->board[i][j] != 0) return false;
            } else {
                if (s->board[i][j] != num) return false;
                num++;
            }
        }
    }
    return true;
}

// 复制当前状态
State *copy_state(State *s) {
    State *new_state = new State;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            new_state->board[i][j] = s->board[i][j];
        }
    }
    new_state->zero_row = s->zero_row;
    new_state->zero_col = s->zero_col;
    new_state->depth = s->depth;
    new_state->prev = s->prev;
    return new_state;
}

// 打印出拼图块的状态
void print_state(State *s) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << s->board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// 找到空格可移动的方向
vector<pair<int, int>> get_moves(State *s) {
    vector<pair<int, int>> moves;
    int r = s->zero_row, c = s->zero_col;
    if (r > 0) moves.push_back({r-1, c}); // 上
    if (r < N-1) moves.push_back({r+1, c}); // 下
    if (c > 0) moves.push_back({r, c-1}); // 左
    if (c < N-1) moves.push_back({r, c+1}); // 右
    return moves;
}

// 判断当前状态是否已被访问过
bool is_visited(State *s, unordered_set<State *> &visited) {
    return visited.find(s) != visited.end();
}

// 生成新的状态，返回是否成功
bool generate_new_state(State *s, int r, int c, State *&new_state) {
    new_state = copy_state(s);
    new_state->board[new_state->zero_row][new_state->zero_col] = new_state->board[r][c];
    new_state->board[r][c] = 0;
    new_state->zero_row = r;
    new_state->zero_col = c;
    new_state->depth = s->depth + 1;
    new_state->prev = s;
    return true;
}

// 搜索，返回是否找到解决方案
bool dfs(State *s, int depth, unordered_set<State *> &visited) {
    if (is_goal(s)) {
        return true;
    } else if (depth == 0) {
        return false;
    }
    vector<pair<int, int>> moves = get_moves(s);
    for (auto move : moves) {
        int r = move.first, c = move.second;
        State *new_state = NULL;
        if (generate_new_state(s, r, c, new_state)) {
            if (!is_visited(new_state, visited)) {
                visited.insert(new_state);
                if (dfs(new_state, depth-1, visited)) {
                    return true;
                }
            }
            delete new_state;
        }
    }
    return false;
}

int main() {
    // 初始化拼图块的状态
    State *start = new State;
    start->board[0][0] = 1;
    start->board[0][1] = 2;
    start->board[0][2] = 3;
    start->board[1][0] = 4;
    start->board[1][1] = 0;
    start->board[1][2] = 5;
    start->board[2][0] = 7;
    start->board[2][1] = 8;
    start->board[2][2] = 6;
    start->zero_row = 1;
    start->zero_col = 1;
    start->depth = 0;
    start->prev = NULL;

    unordered_set<State *> visited;
    visited.insert(start);

    for (int depth = 0; depth <= MAX_DEPTH; depth++) {
        if (dfs(start, depth, visited)) {
            cout << "Solution found at depth " << depth << endl;
            State *s = start;
            while (s != NULL) {
                print_state(s);
                s = s->prev;
            }
            return 0;
        }
    }

    cout << "Solution not found within depth " << MAX_DEPTH << endl;
    return 0;
}

在这个实现中，我们首先定义了一个 `State` 结构体，用于保存拼图块的状态和相关信息。然后定义了几个辅助函数，如判断当前状态是否为目标状态、复制当前状态、打印出拼图块的状态、找到空格可移动的方向、判断当前状态是否已被访问过、生成新的状态等。接着，定义了 `dfs` 函数，实现了有界深度优先搜索的过程。最后，在 `main` 函数中，我们初始化了拼图块的状态，并且依次调用 `dfs` 函数来搜索解决方案，直到找到或者超过最大深度限制。如果找到解决方案，我们打印出解决路径，否则打印出未找到解决方案的提示。