#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <math.h> // 添加数学库以使用 abs 函数

#define N 3 // 定义拼图的维度，这是一个3x3的拼图

typedef struct Node { int puzzle[N][N]; // 存储拼图状态的数组 struct Node* parent; // 指向父节点的指针，用于追踪路径 int f, g, h; // A*算法中的 f, g, h 值 } Node;

// 创建新的拼图节点 Node* createNode(int puzzle[N][N]) { Node* newnode = (Node*)malloc(sizeof(Node)); // 为新节点分配内存

// 初始化拼图状态
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        newnode->puzzle[i][j] = puzzle[i][j];
    }
}

newnode->parent = NULL;  // 父节点指针初始化为NULL
newnode->f = 0;
newnode->g = 0;
newnode->h = 0;

return newnode;

} bool isSamePuzzle(int a[N][N], int b[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (a[i][j] != b[i][j]) { return false; // 存在不同的拼图块，返回false } } } return true; // 所有拼图块相同，返回true }

// 打印拼图状态 void printPuzzle(int puzzle[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", puzzle[i][j]); } printf("\n"); } printf("\n"); }

// 启发函数，计算当前状态到目标状态的估计代价 int heuristic(Node* current, Node* goal) { int h = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int value = current->puzzle[i][j]; if (value != 0) { // 不是空白块 int target_i = (value - 1) / N; // 目标位置的行坐标 int target_j = (value - 1) % N; // 目标位置的列坐标 h += abs(i - target_i) + abs(j - target_j); // 计算曼哈顿距离 } } } return h; }

// 移动操作，生成新的拼图状态

Node* move(Node* current, int dir) { Node* newnode = createNode(current->puzzle); // 创建新节点并复制当前状态

int x, y;  // 空白块的位置

// 找到空白块的位置
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (newnode->puzzle[i][j] == 0) {
            x = i;
            y = j;
        }
    }
}

// 根据移动方向进行交换操作
if (dir == 0 && x > 0) {  // 上移
    newnode->puzzle[x][y] = newnode->puzzle[x - 1][y];
    newnode->puzzle[x - 1][y] = 0;
} else if (dir == 1 && x < N - 1) {  // 下移
    newnode->puzzle[x][y] = newnode->puzzle[x + 1][y];
    newnode->puzzle[x + 1][y] = 0;
} else if (dir == 2 && y > 0) {  // 左移
    newnode->puzzle[x][y] = newnode->puzzle[x][y - 1];
    newnode->puzzle[x][y - 1] = 0;
} else if (dir == 3 && y < N - 1) {  // 右移
    newnode->puzzle[x][y] = newnode->puzzle[x][y + 1];
    newnode->puzzle[x][y + 1] = 0;
} else {
    return NULL;  // 无效移动，返回空指针
}

return newnode; } // A*算法，寻找最短路径

Node* AStar(Node* start, Node* goal) { // 创建优先队列并初始化 PriorityQueue* openSet = initPriorityQueue(1000);

// 设置起始节点的 f, g, h 值
start->g = 0;
start->h = heuristic(start, goal);
start->f = start->g + start->h;

// 将起始节点加入优先队列
enqueue(openSet, start, start->f);

while (!isEmpty(openSet)) {
    // 从优先队列中取出f值最小的节点作为当前节点
    Node* current = dequeue(openSet);

    // 如果当前节点是目标节点，则找到了最短路径，返回当前节点
    if (isSamePuzzle(current->puzzle, goal->puzzle)) {
        freePriorityQueue(openSet);  // 释放优先队列内存
        return current;
    }

    // 尝试生成当前节点的相邻节点并进行处理
    for (int dir = 0; dir < 4; dir++) {
        Node* neighbor = move(current, dir);
        if (neighbor != NULL) {
            neighbor->g = current->g + 1;
            neighbor->h = heuristic(neighbor, goal);
            neighbor->f = neighbor->g + neighbor->h;

            // 检查相邻节点是否已经在优先队列中或者已经处理过
            // ...
        }
    }

    // 更新当前节点的状态为已处理
    // ...
}

freePriorityQueue(openSet);  // 释放优先队列内存
return NULL;  // 如果无解，则返回空指针

} // 打印解路径 void printPath(Node* final) { if (final == NULL) { return; } printPath(final->parent); // 递归打印路径 printPuzzle(final->puzzle); // 打印拼图状态 } int main() { //int start[N][N] = {{2, 0, 3}, {1, 8, 4}, {7, 6, 5}}; //int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};

// int start[N][N] = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
// int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};

int start[N][N] = {{2, 8, 3}, {1, 0, 4}, {7, 6, 5}};
int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
Node* init = createNode(start);
Node* goal = createNode(target);

Node* final = AStar(init, goal);
if (final) {
    printf("This problem has a solution:\n");
    printPath(final);  // 打印解路径
} else {
    printf("This problem has no solution！\n");
}

return 0;

}