八数码问题c语言代码

以下是一个使用 C 语言解决八数码问题的示例代码：

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

#define SIZE 3

typedef struct State {
    int puzzle[SIZE][SIZE];
    struct State* parent;
    int f, g, h;
} State;

int goal[SIZE][SIZE] = {
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5}
};

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char move[] = {'u', 'd', 'l', 'r'};

State* create_state(int puzzle[SIZE][SIZE], State* parent, int f, int g, int h) {
    State* state = (State*)malloc(sizeof(State));
    memcpy(state->puzzle, puzzle, sizeof(state->puzzle));
    state->parent = parent;
    state->f = f;
    state->g = g;
    state->h = h;
    return state;
}

int calculate_cost(int puzzle[SIZE][SIZE]) {
    int cost = 0;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (puzzle[i][j] != goal[i][j]) {
                cost++;
            }
        }
    }
    return cost;
}

bool is_valid_move(int x, int y) {
    return (x >= 0 && x < SIZE && y >= 0 && y < SIZE);
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool is_goal_state(State* state) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (state->puzzle[i][j] != goal[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void print_path(State* state) {
    if (state->parent != NULL) {
        print_path(state->parent);
    }
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", state->puzzle[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void solve_puzzle(int puzzle[SIZE][SIZE]) {
    int f, g, h;

    State* start_state = create_state(puzzle, NULL, 0, 0, 0);

    start_state->h = calculate_cost(start_state->puzzle);
    start_state->f = start_state->g + start_state->h;

    State* open_list = start_state;
    State* closed_list = NULL;

    while (open_list != NULL) {
        State* current_state = open_list;

        if (open_list->h == 0) {
            printf("Solution Found!\n\n");
            print_path(open_list);
            return;
        }

        open_list = open_list->parent;
        current_state->parent = closed_list;
        closed_list = current_state;

        int x, y;
        for (int i = 0; i < 4; i++) {
            x = (int)(current_state->g / SIZE);
            y = current_state->g % SIZE;
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (is_valid_move(new_x, new_y)) {
                State* new_state = create_state(current_state->puzzle, current_state, 0, 0, 0);
                swap(&new_state->puzzle[x][y], &new_state->puzzle[new_x][new_y]);

                new_state->g = current_state->g + 1;
                new_state->h = calculate_cost(new_state->puzzle);
                new_state->f = new_state->g + new_state->h;

                State* temp = open_list;
                bool is_duplicate = false;
                while (temp != NULL) {
                    if (memcmp(temp->puzzle, new_state->puzzle, sizeof(new_state->puzzle)) == 0) {
                        is_duplicate = true;
                        break;
                    }
                    temp = temp->parent;
                }

                temp = closed_list;
                while (temp != NULL) {
                    if (memcmp(temp->puzzle, new_state->puzzle, sizeof(new_state->puzzle)) == 0) {
                        is_duplicate = true;
                        break;
                    }
                    temp = temp->parent;
                }

                if (!is_duplicate) {
                    new_state->parent = open_list;
                    open_list = new_state;
                } else {
                    free(new_state);
                }
            }
        }
    }

    printf("No solution found!\n");
}

int main() {
    int puzzle[SIZE][SIZE];

    printf("Enter the puzzle (3x3):\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            scanf("%d", &puzzle[i][j]);
        }
    }

    printf("\n");

    solve_puzzle(puzzle);

    return 0;
}

这个程序使用 A* 算法来解决八数码问题。输入一个 3x3 的拼图，程序将尝试找到一系列移动步骤，使得拼图最终恢复到目标状态。如果找到解决方案，程序将打印出移动步骤。如果没有解决方案，程序将打印出 "No solution found!"。