宽度优先搜索解决八数码c语言

以下是使用宽度优先搜索算法解决八数码问题的C语言代码：

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

#define SIZE 3

typedef struct state {
    int board[SIZE][SIZE];
    int blankRow, blankCol;
    struct state *prev;
} State;

typedef struct node {
    State *state;
    struct node *next;
} Node;

typedef struct queue {
    Node *head;
    Node *tail;
} Queue;

State *newState(int board[SIZE][SIZE], int blankRow, int blankCol, State *prev) {
    State *state = (State *) malloc(sizeof(State));
    memcpy(state->board, board, sizeof(int) * SIZE * SIZE);
    state->blankRow = blankRow;
    state->blankCol = blankCol;
    state->prev = prev;
    return state;
}

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

void printSolution(State *state) {
    int steps = 0;
    while (state->prev) {
        steps++;
        state = state->prev;
    }
    printf("Solution in %d steps:\n", steps);
    while (state) {
        printBoard(state->board);
        printf("\n");
        state = state->prev;
    }
}

void enqueue(Queue *queue, State *state) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->state = state;
    node->next = NULL;
    if (queue->tail) {
        queue->tail->next = node;
    } else {
        queue->head = node;
    }
    queue->tail = node;
}

State *dequeue(Queue *queue) {
    Node *head = queue->head;
    State *state = head->state;
    queue->head = head->next;
    free(head);
    if (!queue->head) {
        queue->tail = NULL;
    }
    return state;
}

int isGoalState(int board[SIZE][SIZE]) {
    int n = 0;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (board[i][j] != n++) {
                return 0;
            }
        }
    }
    return 1;
}

void freeState(State *state) {
    free(state);
}

void freeQueue(Queue *queue) {
    while (queue->head) {
        State *state = dequeue(queue);
        freeState(state);
    }
}

void solve(int startBoard[SIZE][SIZE]) {
    Queue *queue = (Queue *) malloc(sizeof(Queue));
    queue->head = NULL;
    queue->tail = NULL;
    State *startState = newState(startBoard, 0, 0, NULL);
    enqueue(queue, startState);
    while (queue->head) {
        State *state = dequeue(queue);
        if (isGoalState(state->board)) {
            printSolution(state);
            freeQueue(queue);
            freeState(state);
            return;
        }
        int row = state->blankRow;
        int col = state->blankCol;
        if (row > 0) {
            int newBoard[SIZE][SIZE];
            memcpy(newBoard, state->board, sizeof(int) * SIZE * SIZE);
            newBoard[row][col] = newBoard[row - 1][col];
            newBoard[row - 1][col] = 0;
            State *newState = newState(newBoard, row - 1, col, state);
            enqueue(queue, newState);
        }
        if (row < SIZE - 1) {
            int newBoard[SIZE][SIZE];
            memcpy(newBoard, state->board, sizeof(int) * SIZE * SIZE);
            newBoard[row][col] = newBoard[row + 1][col];
            newBoard[row + 1][col] = 0;
            State *newState = newState(newBoard, row + 1, col, state);
            enqueue(queue, newState);
        }
        if (col > 0) {
            int newBoard[SIZE][SIZE];
            memcpy(newBoard, state->board, sizeof(int) * SIZE * SIZE);
            newBoard[row][col] = newBoard[row][col - 1];
            newBoard[row][col - 1] = 0;
            State *newState = newState(newBoard, row, col - 1, state);
            enqueue(queue, newState);
        }
        if (col < SIZE - 1) {
            int newBoard[SIZE][SIZE];
            memcpy(newBoard, state->board, sizeof(int) * SIZE * SIZE);
            newBoard[row][col] = newBoard[row][col + 1];
            newBoard[row][col + 1] = 0;
            State *newState = newState(newBoard, row, col + 1, state);
            enqueue(queue, newState);
        }
        freeState(state);
    }
    freeQueue(queue);
    printf("No solution found\n");
}

int main() {
    int board[SIZE][SIZE] = {{1, 2, 3}, {4, 0, 5}, {6, 7, 8}};
    solve(board);
    return 0;
}

该代码使用了队列来实现宽度优先搜索。每个状态都包含一个指向前一个状态的指针，最终可以从最终状态沿着指针链回溯到初始状态，从而输出解决方案。