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

enum move_type {up, down, left, right};
enum Bool_type {trues, falses};

struct node_struct
{
int state[3][3];
int hole[2];
enum move_type move;
int heuristic;
struct node_struct *parent;
struct node_struct *next_in_leaf_list;
};
typedef struct node_struct node_type;
typedef enum Bool_type Boolean;
char buf[80];
node_type *head_leaf_list;
Boolean solved;

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

int heuristic (node_type *node)
{
    int i, j, z = 0;
    for(i = 0; i < 3; i++)
    {
        for(j = 0; j < 3; j++)
        {
            if (node -> state[i][j] != goal_state[i][j] &&  (node -> state[i][j] !=0))
                z++;
        }
    }
    return(z);
}

node_type *get_start_state()
{
    int i, j;
    char c;
    node_type *node;

    node = (node_type *) malloc(sizeof(node_type));
    printf("\n 8-Puzzle Solve \n");
    do
    {
        printf("Enter the configuration of the pizzle that \n");
        printf("you wish to havw solved one row at a time \n");
        printf("with at least one blank between each tile \n");
        printf("number. Use a zero to represent the hole. \n");
        printf("Example: \n1 2 3\n");
        printf("4 0 5\n");
        printf("7 8 6\n\n");
        for (i = 0; i < 3; i++)
        {
            scanf("%d %d %d%c", &(node -> state[i][0]), &(node -> state[i][1]), &(node -> state[i][2]), &c);
            printf("\n");
            for (j = 0; j < 3; j++)
                if (node -> state[i][j] == 0)
                {
                    node -> hole[0] = i;
                    node -> hole[1] = j;
                }
        }
        printf("\nstarting configuration is: \n");
        for (i = 0; i < 3; i++)
        {
            printf(" ");
            for (j = 0; j < 3; j++)
                printf("%d ", node -> state[i][j]);
            printf("\n");
        }
        printf("\nls that corret? (Y/N): ");
        gets(buf);
    } while((buf[0] != 'Y') && (buf[0] != 'y'));
    node -> parent = NULL;
    node -> heuristic = heuristic(node);
    return(node);
}

Boolean at_goal(node_type *node)
{
    int i, j;
    Boolean at_goal = trues;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            if((node -> state[i][j]) != goal_state[i][j])
                at_goal = falses;
            return(at_goal);
}

void insert (node_type *new_node)
{
    node_type *last, *next;
    Boolean found;
    if (head_leaf_list == NULL)
    {
        head_leaf_list = new_node;
        new_node -> next_in_leaf_list = NULL;
    }
    else
    {
        if (new_node -> heuristic < head_leaf_list -> heuristic)
        {
            new_node -> next_in_leaf_list = head_leaf_list;
            head_leaf_list = new_node;
        }
        else
        {
            last = head_leaf_list;
            next = head_leaf_list -> next_in_leaf_list;
            found = falses;
            while ((next != NULL) && (found == falses))
            {
                if (new_node -> heuristic < next -> heuristic)
                    found = trues;
                else
                {
                    last = next;
                    next = next -> next_in_leaf_list;
                }
            }
            new_node -> next_in_leaf_list = next;
            last -> next_in_leaf_list = new_node;
        }
    }
}

void expand (node_type *node, node_type **final_node)
{
    node_type *child;
    enum move_type trys;
    int i, j, k, l, x, y, prev1, prev2;
    if(node -> parent == NULL)
    {
        prev1 = -1;
        prev2 = -1;
    }
    else
    {
        prev1 = node -> parent -> hole[0];
        prev2 = node -> parent -> hole[1];
    }
    i = node -> hole[0];
    j = node -> hole[1];
    for (trys = up; trys <= right; trys)
    {
        switch (trys)
        {
        case up: k = 1 - 1;
            l = j;
            break;
        case down: k = i + 1;
            l = j;
            break;
        case left: k = i;
            l = j - 1;
            break;
        case right: k = i;
            l = j + 1;
            break;
        }
        if ((-1 < k) && (k <3) && (-1 < l ) && (l < 3) &&
            ((prev1 != k) || (prev2 != l)) && solved == falses)
        {
            child = (node_type *) malloc(sizeof(node_type));
            child -> parent = node;
            for (x = 0; y < 3; y++)
                for (y = 0; y < 3; y++)
                    child -> state[x][y] = node -> state[x][y];
                child -> hole[0] = k;
                child -> hole[1] = l;
                child -> state[i][j] = child -> state[k][l];
                child -> state[k][l] = 0;
                child -> move = trys;
                child -> heuristic = heuristic(child);
                insert(child);
                solved = at_goal(child);
                if (solved == trues) *final_node = child;
        }
    }
}

void report_solution (node_type *node)
{
    if(node -> parent != NULL)
    {
        report_solution (node -> parent);
        switch (node -> move)
        {
        case up: printf("Move a tile down.\n");break;
        case down: printf("Move a tile up.\n");break;
        case left: printf("Move a tile right.\n");break;
        case right: printf("Move a tile left\n");break;
        }
    }
}

void main(void)
{
    int count, total;
    node_type *current, *final_node;

    current = get_start_state();
    printf("\nSearch has begun.\n");
    solved = at_goal(current);
    head_leaf_list = current;
    current -> next_in_leaf_list = NULL;
    count = 0;
    total = 0;
    while ((count < 500) && solved == falses)
    {
        current = head_leaf_list;
        head_leaf_list = head_leaf_list -> next_in_leaf_list;
        expand (current, &final_node);
        count++;
        if((count == 500) && solved == falses)
        {
            total = total + count;
            printf("%d nodes have been expanded", total);
            printf("without reaching the goal.\n");
            printf("Continue searchinf? (Y/N): ");
            gets(buf);
            if ((buf[0] == 'Y') || (buf[0] == 'y'))
                count = 0;
        }
    }
    if (solved == trues)
    {
        printf("\n");
        printf("Solution found.\n");
        printf("Steps are as follows: \n");
        if(current -> parent == NULL)
            printf("No moves required.\n");
        else
            report_solution (current);
    }
    else
    {
        printf("Execution terminated without reaching goal.\n\n");
        printf("press <Enter> to continue.");
        gets(buf);
    }
}