C语言广度优先算法实现八数码

在使用广度优先算法解决八数码问题时，我们可以将八数码问题抽象成一个状态图，其中每个节点表示一个局面，每个边表示一步操作（移动一个数字）。我们需要从初始状态出发，通过不断地进行操作，最终到达目标状态。

以下是使用 C 语言实现八数码广度优先算法的示例代码：

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

#define MAX_QUEUE_SIZE 1000000 // 队列最大容量

struct node {
    int board[3][3]; // 八数码矩阵
    int zero_row; // 空格所在行
    int zero_col; // 空格所在列
    int depth; // 当前深度
    struct node *parent; // 父节点指针
};

int visited[362880]; // 记录状态是否被访问过
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

struct node *create_node(int board[3][3], int zero_row, int zero_col, int depth, struct node *parent) {
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
    memcpy(new_node->board, board, sizeof(board)); // 复制八数码矩阵
    new_node->zero_row = zero_row;
    new_node->zero_col = zero_col;
    new_node->depth = depth;
    new_node->parent = parent;
    return new_node;
}

void free_node(struct node *node) {
    free(node);
}

int get_board_index(int board[3][3]) {
    int index = 0;
    int factorial = 1;
    for (int i = 0; i < 9; i++) {
        int smaller = 0;
        for (int j = i + 1; j < 9; j++) {
            if (board[j / 3][j % 3] < board[i / 3][i % 3]) {
                smaller++;
            }
        }
        index += smaller * factorial;
        factorial *= (9 - i);
    }
    return index;
}

void print_board(int board[3][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

void print_path(struct node *node) {
    if (node == NULL) {
        return;
    }
    print_path(node->parent);
    printf("Step %d:\n", node->depth);
    print_board(node->board);
    printf("\n");
}

void bfs(struct node *start_node, struct node *target_node) {
    int front = 0; // 队首指针
    int rear = 0; // 队尾指针
    struct node *queue[MAX_QUEUE_SIZE]; // 队列
    queue[rear++] = start_node; // 将起始状态加入队列
    visited[get_board_index(start_node->board)] = 1; // 标记起始状态已被访问
    while (front != rear) { // 当队列不为空时
        struct node *cur_node = queue[front++]; // 取出队首节点
        if (memcmp(cur_node->board, target_node->board, sizeof(target_node->board)) == 0) { // 如果当前状态等于目标状态
            printf("Solution found!\n");
            print_path(cur_node);
            return;
        }
        for (int i = 0; i < 4; i++) { // 遍历四个方向
            int new_row = cur_node->zero_row + dir[i][0];
            int new_col = cur_node->zero_col + dir[i][1];
            if (new_row >= 0 && new_row < 3 && new_col >= 0 && new_col < 3) { // 新位置在边界内
                int new_board[3][3];
                memcpy(new_board, cur_node->board, sizeof(cur_node->board));
                new_board[cur_node->zero_row][cur_node->zero_col] = new_board[new_row][new_col];
                new_board[new_row][new_col] = 0;
                int index = get_board_index(new_board);
                if (!visited[index]) { // 如果新状态没有被访问过
                    visited[index] = 1; // 标记新状态已被访问
                    struct node *new_node = create_node(new_board, new_row, new_col, cur_node->depth + 1, cur_node);
                    queue[rear++] = new_node; // 将新状态加入队列
                }
            }
        }
    }
    printf("No solution found!\n");
}

int main() {
    int start_board[3][3] = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}}; // 起始状态
    int target_board[3][3] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}}; // 目标状态
    struct node *start_node = create_node(start_board, 2, 1, 0, NULL); // 创建起始节点
    struct node *target_node = create_node(target_board, 1, 1, 0, NULL); // 创建目标节点
    bfs(start_node, target_node); // 进行广度优先搜索
    free_node(start_node);
    free_node(target_node);
    return 0;
}

在上面的示例代码中，我们使用了一个队列来存储待访问的状态，使用了一个 visited 数组来记录状态是否被访问过。在搜索过程中，我们先从队列中取出队首节点，然后遍历该节点的四个方向，如果新位置在边界内且新状态没有被访问过，则将新状态加入队列中。当队列为空时，搜索结束。

在程序执行过程中，我们还需要实现一些辅助函数，如 get_board_index 函数用于计算八数码矩阵的唯一索引，print_board 函数用于打印八数码矩阵，print_path 函数用于打印路径等。