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

#define N 3                                                 // 拼图的维度为3

typedef struct Node {
    int puzzle[N][N];    
    struct Node* parent; 
    int f, g, h;         
} Node;

Node* createNode(int puzzle[N][N])                          // 创建新的节点
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    memcpy(newnode->puzzle, puzzle, sizeof(int) * N * N);
    newnode->parent = NULL;
    newnode->f = newnode->g = 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;
        }
    }
    return true;
}

void printPuzzle(int puzzle[N][N])                          // 输出拼图状态
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf("%-2d", 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++)
        {
            if (current->puzzle[i][j] != goal->puzzle[i][j])
                h++;
        }
    }
    return h;
}

Node* move(Node* current, int dir)                          // 生成新的拼图状态
{
    int key_x, key_y; 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (current->puzzle[i][j] == 0)
            {
                key_x = i;
                key_y = j;
                break;
            }
        }
    }
    int new_x = key_x, new_y = key_y;
    switch (dir)                                          // 根据移动方向移动新块的位置
    {
    case 0:
        new_x--;
        break;
    case 1:
        new_x++;
        break;
    case 2:
        new_y--;
        break;
    case 3:
        new_y++;
        break;
    default:
        break;
    }
    if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N)
        return NULL;   
    Node* new_node = createNode(current->puzzle);                       // 创建新节点，复制当前拼图状态，并交换块的位置
    new_node->puzzle[key_x][key_y] = current->puzzle[new_x][new_y];
    new_node->puzzle[new_x][new_y] = 0;

    return new_node;
}

Node* AStar(Node* start, Node* goal)                                    // A*算法
{
    Node* OPEN[1000];   
    Node* CLOSED[1000]; 
    int OPEN_SIZE = 0;  
    int CLOSED_SIZE = 0;
    OPEN[0] = start;    
    OPEN_SIZE = 1;      
    CLOSED_SIZE = 0;   
    while (OPEN_SIZE > 0)
    {
        int min_f = OPEN[0]->f;
        int min_index = 0;      
        for (int i = 1; i < OPEN_SIZE; i++)                             // 查找开放列表中具有最小f值的节点
        {
            if (OPEN[i]->f < min_f)
            {
                min_f = OPEN[i]->f;
                min_index = i;
            }
        }
        Node* current = OPEN[min_index]; 
        if (isSamePuzzle(current->puzzle, goal->puzzle))
        {
            return current;
        }
        OPEN_SIZE--;
        Node* temp = OPEN[min_index];
        OPEN[min_index] = OPEN[OPEN_SIZE];
        OPEN[OPEN_SIZE] = temp;
        CLOSED[CLOSED_SIZE++] = current;
        int key = 0;
        for (int i = 0; i < N; i++)                                     // 查找当前节点中空白块的位置
        {
            for (int j = 0; j < N; j++)
            {
                if (current->puzzle[i][j] == 0)
                {
                    key = i * N + j;
                    break;
                }
            }
        }       
        for (int dir = 0; dir < 4; dir++)                               // 尝试四个方向的移动操作
        {
            Node* new_node = move(current, dir);

            if (new_node != NULL && !isSamePuzzle(new_node->puzzle, current->puzzle))
            {
                int gNew = current->g + 1;
                int hNew = heuristic(new_node, goal);
                int fNew = gNew + hNew;
                bool in_OPEN = false;
                int open_index = -1;                
                for (int i = 0; i < OPEN_SIZE; i++)                     // 检查新节点是否在开放列表中
                {
                    if (isSamePuzzle(new_node->puzzle, OPEN[i]->puzzle))
                    {
                        in_OPEN = true;
                        open_index = i;
                        break;
                    }
                }
                bool in_CLOSED = false;
                for (int i = 0; i < CLOSED_SIZE; i++)                   // 检查新节点是否在关闭列表中
                {
                    if (isSamePuzzle(new_node->puzzle, CLOSED[i]->puzzle))
                    {
                        in_CLOSED = true;
                        break;
                    }
                }
                if (!in_OPEN && !in_CLOSED)                             // 如果新节点均不满足，则将其添加到开放列表
                {
                    new_node->g = gNew;
                    new_node->h = hNew;
                    new_node->f = fNew;
                    new_node->parent = current;

                    OPEN[OPEN_SIZE++] = new_node;
                }
                else if (in_OPEN && fNew < OPEN[open_index]->f)         // 如果新节点在开放列表中，但新的f值更小，更新节点信息
                {
                    OPEN[open_index]->g = gNew;
                    OPEN[open_index]->h = hNew;
                    OPEN[open_index]->f = fNew;
                    OPEN[open_index]->parent = current;
                }
            }
        }
    }
    return NULL;
}

void printPath(Node* final)                                     // 输出解路径
{

    if (final == NULL)
    {
        return;
    }
    printPath(final->parent); 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf("%-2d", final->puzzle[i][j]);
        }
        printf("\n");
    }printf("------");
    printf("\n");
}

int main()
{
    int start_puzzle[N][N] = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} }; 
    int goal_puzzle[N][N] = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} }; 
    Node* start = createNode(start_puzzle); 
    Node* goal = createNode(goal_puzzle); 
    Node* final = AStar(start, goal); 
    if (final != NULL)
    {
        printf("Solution path:\n");
        printPath(final); 
    }
    else
    {
        printf("No solution found.\n");
    }
    return 0;
}