用C语言实现深度优先搜索算法的八数码问题

八数码问题是经典的搜索问题，其中涉及了深度优先搜索算法。下面是用C语言实现深度优先搜索算法的八数码问题的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DEPTH 25 // 深度优先搜索的最大深度

// 八数码状态结构体
typedef struct {
    int board[3][3];
    int blank_x, blank_y; // 空格的位置
} State;

int visited[400000]; // 记录已经访问过的状态，避免重复搜索

// 判断当前状态是否为目标状态
int is_goal(State state) {
    int i, j;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (state.board[i][j] != i * 3 + j)
                return 0;
        }
    }
    return 1;
}

// 复制状态
void copy_state(State *dst, State src) {
    memcpy(dst, &src, sizeof(State));
}

// 移动空格，返回新状态
State move(State state, int dx, int dy) {
    State new_state;
    copy_state(&new_state, state);
    new_state.board[state.blank_x][state.blank_y] = state.board[state.blank_x + dx][state.blank_y + dy];
    new_state.board[state.blank_x + dx][state.blank_y + dy] = 0;
    new_state.blank_x += dx;
    new_state.blank_y += dy;
    return new_state;
}

// 深度优先搜索
int dfs(State state, int depth) {
    if (is_goal(state)) {
        return 1;
    }
    if (depth >= MAX_DEPTH) {
        return 0;
    }
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    int i;
    for (i = 0; i < 4; i++) {
        if (state.blank_x + dx[i] < 0 || state.blank_x + dx[i] >= 3
            || state.blank_y + dy[i] < 0 || state.blank_y + dy[i] >= 3)
            continue;
        State new_state = move(state, dx[i], dy[i]);
        int hash = new_state.board[0][0] * 1000000 + new_state.board[0][1] * 100000 + new_state.board[0][2] * 10000
                    + new_state.board[1][0] * 1000 + new_state.board[1][1] * 100 + new_state.board[1][2] * 10 + new_state.board[2][0];
        if (visited[hash])
            continue;
        visited[hash] = 1;
        if (dfs(new_state, depth + 1))
            return 1;
        visited[hash] = 0;
    }
    return 0;
}

int main() {
    State init_state;
    printf("请输入八数码初始状态：\n");
    int i, j;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            scanf("%d", &init_state.board[i][j]);
            if (init_state.board[i][j] == 0) {
                init_state.blank_x = i;
                init_state.blank_y = j;
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    int hash = init_state.board[0][0] * 1000000 + init_state.board[0][1] * 100000 + init_state.board[0][2] * 10000
                + init_state.board[1][0] * 1000 + init_state.board[1][1] * 100 + init_state.board[1][2] * 10 + init_state.board[2][0];
    visited[hash] = 1;
    if (dfs(init_state, 0)) {
        printf("可以解决\n");
    } else {
        printf("无解\n");
    }
    return 0;
}

在上面的代码中，`State` 结构体表示八数码状态，其中 `board` 数组表示八数码的位置，`blank_x` 和 `blank_y` 表示空格的位置。`visited` 数组用于记录已经访问过的状态，避免重复搜索。`is_goal` 函数用于判断当前状态是否为目标状态，`copy_state` 函数用于复制状态，`move` 函数用于移动空格并返回新状态。`dfs` 函数是深度优先搜索的核心部分，其中使用了上述函数。在 `main` 函数中，首先读入八数码的初始状态，然后进行深度优先搜索，判断是否可以解决八数码问题。