c语言求解8数码问题

C语言可以用来求解8数码问题，这是一个经典的搜索问题。8数码问题是一个在3x3的棋盘上，通过移动数字块的位置，将初始状态转化为目标状态的问题。在C语言中，可以使用广度优先搜索（BFS）或者深度优先搜索（DFS）等算法来解决这个问题。

下面是一个使用BFS算法求解8数码问题的示例代码：

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

#define N 3

// 定义状态结构体
typedef struct {
    int board[N][N];
    int zero_row;
    int zero_col;
} State;

// 定义队列节点结构体
typedef struct {
    State state;
    int depth;
} Node;

// 判断两个状态是否相等
bool is_equal(State s1, State s2) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s1.board[i][j] != s2.board[i][j]) {
                return false;
            }
        }
    }
    return true;
}

// 判断状态是否为目标状态
bool is_goal(State state) {
    int count = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (state.board[i][j] != count % (N * N)) {
                return false;
            }
            count++;
        }
    }
    return true;
}

// 复制状态
void copy_state(State* dest, State src) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dest->board[i][j] = src.board[i][j];
        }
    }
    dest->zero_row = src.zero_row;
    dest->zero_col = src.zero_col;
}

// 移动数字块
void move(State* state, int row, int col) {
    state->board[state->zero_row][state->zero_col] = state->board[row][col];
    state->board[row][col] = 0;
    state->zero_row = row;
    state->zero_col = col;
}

// 打印状态
void print_state(State state) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", state.board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

// 求解8数码问题
void solve(State initial_state) {
    // 定义队列
    Node queue[10000];
    int front = 0;
    int rear = 0;

    // 定义访问数组
    bool visited[10000] = {false};

    // 将初始状态入队
    Node initial_node;
    initial_node.state = initial_state;
    initial_node.depth = 0;
    queue[rear++] = initial_node;
    visited[0] = true;

    while (front < rear) {
        // 出队
        Node current_node = queue[front++];
        State current_state = current_node.state;

        // 判断是否为目标状态
        if (is_goal(current_state)) {
            printf("找到解答，步数为：%d\n", current_node.depth);
            return;
        }

        // 扩展当前状态的子状态
        int row = current_state.zero_row;
        int col = current_state.zero_col;

        // 上移
        if (row > 0) {
            State new_state;
            copy_state(&new_state, current_state);
            move(&new_state, row - 1, col);
            if (!visited[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]]) {
                Node new_node;
                new_node.state = new_state;
                new_node.depth = current_node.depth + 1;
                queue[rear++] = new_node;
                visited[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]] = true;
            }
        }

        // 下移
        if (row < N - 1) {
            State new_state;
            copy_state(&new_state, current_state);
            move(&new_state, row + 1, col);
            if (!visited[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]]) {
                Node new_node;
                new_node.state = new_state;
                new_node.depth = current_node.depth + 1;
                queue[rear++] = new_node;
                visited[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]] = true;
            }
        }

        // 左移
        if (col > 0) {
            State new_state;
            copy_state(&new_state, current_state);
            move(&new_state, row, col - 1);
            if (!visited[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]]) {
                Node new_node;
                new_node.state = new_state;
                new_node.depth = current_node.depth + 1;
                queue[rear++] = new_node;
                visited[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]] = true;
            }
        }

        // 右移
        if (col < N - 1) {
            State new_state;
            copy_state(&new_state, current_state);
            move(&new_state, row, col + 1);
            if (!visited[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]]) {
                Node new_node;
                new_node.state = new_state;
                new_node.depth = current_node.depth + 1;
                queue[rear++] = new_node;
                visited[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]] = true;
            }
        }
    }

    printf("未找到解答！\n");
}

int main() {
    State initial_state = {
        {{2, 8, 3},
         {1, 6, 4},
         {7, 0, 5}},
        2,
        1
    };

    solve(initial_state);

    return 0;
}

这段代码使用了一个队列来存储待搜索的状态，使用一个访问数组来记录已经访问过的状态，通过BFS算法逐步扩展状态，直到找到目标状态或者队列为空。