ACM UVA (10181)

/*
 * UVA Problem ID: 10181.
 * Use A* Algorithm to solve 15-puzzle problem.
 * Xiaofeng Ye
 */

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

char result_board[4][4] = {
    1, 2, 3, 4,
    5, 6, 7, 8,
    9, 10, 11, 12,
    13, 14, 15, 0
};

typedef struct _position {
    char x;
    char y;
} position;

position result_instance_pos[16] = {
    {3,3},
    {0,0}, {0,1}, {0,2}, {0,3},
    {1,0}, {1,1}, {1,2}, {1,3},
    {2,0}, {2,1}, {2,2}, {2,3},
    {3,0}, {3,1}, {3,2}
};
int calculate_h_value(char board[4][4])
{
    int i, j;
    char unit;
    int h_value = 0;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            unit = board[i][j];
            h_value += abs(i-result_instance_pos[unit].x) +
                       abs(j-result_instance_pos[unit].y);
            //printf("%d ", abs(i-result_instance_pos[unit].x) +

            // abs(j-result_instance_pos[unit].y));

        }
    }
    //printf("\n");


    return h_value;
}

enum DIRECTION {
    UP = 0,
    RIGHT,
    DOWN,
    LEFT,
};

typedef struct _board_instance {
    int g_value;
    int h_value;
    char board[4][4];
    char where;
    position zero_pos;
    struct _board_instance *parent;
    struct _board_instance *next;
} board_instance, instance_list;

board_instance *final_instance = NULL;

int is_board_instance_same(board_instance *ins1, board_instance *ins2)
{
    if (0 == memcmp(ins1->board, ins2->board, 16)) {
        return 1;
    } else {
        return 0;
    }
}

#define FVALUE(ins) ( ins->h_value + ins->g_value )

void show_instance(board_instance *ins)
{
    int i, j;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            printf("%d\t", ins->board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int is_possible(char board[4][4])
{
    char *p_unit = (char *)board;
    int i;
    int j;
    int n_inverse = 0;
    int zero_index;

    for (i = 0; i < 16; i++) {
        if (*(p_unit+i) == 0) {
            zero_index = i;
            continue;
        }
        for (j = i+1; j < 16; j++) {
            if (*(p_unit+j) != 0 && *(p_unit+j) < *(p_unit+i)) {
                n_inverse++;
            }
        }
    }

    n_inverse += zero_index/4 + 1;

    if (n_inverse % 2 == 0) {
        return 1;
    } else {
        return 0;
    }
}

instance_list *instance_list_add_front(instance_list *list, board_instance *instance)
{
    if (NULL == list) {
        list = instance;
        list->next = NULL;
        return list;
    } else {
        instance->next = list->next;
        list->next = instance;
        return instance;
    }
}

board_instance *instance_list_get_smallest(instance_list *list)
{
    board_instance *instance = list;
    board_instance *cursor = list;

    while (cursor->next != NULL) {
        cursor = cursor->next;
        if ((cursor->g_value + cursor->h_value) <
            (instance->g_value + instance->h_value)){
            instance = cursor;
        }
    }
    return instance;
}

board_instance *board_instance_new(char board[4][4])
{
    board_instance *new_instance;
    char *p_unit = (char *)board;
    int i;

    for (i = 0; i < 16; i++) {
        if (*p_unit++ == 0) {
            break;
        }
    }
    if (16 == i) {
        return NULL;
    }

    new_instance = (board_instance *)malloc(sizeof(board_instance));
    new_instance->g_value = 0;
    memcpy(new_instance->board, board, 16);
    new_instance->parent = NULL;
    new_instance->next = NULL;
    new_instance->zero_pos.x = i / 4;
    new_instance->zero_pos.y= i % 4;
    new_instance->h_value = calculate_h_value(new_instance->board);

    return new_instance;
}

board_instance *board_instance_new_child(board_instance *parent, enum DIRECTION where)
{
    board_instance *child;
    char tmp_val;
    position old_pos = parent->zero_pos;

    child = (board_instance *)malloc(sizeof(board_instance));
    memcpy(child, parent, sizeof(board_instance));
    child->g_value++;
    child->next = NULL;
    child->parent = parent;
    switch (where) {
    case UP:
        child->zero_pos.x--;
        child->where = 'U';
        break;
    case RIGHT:
        child->zero_pos.y++;
        child->where = 'R';
        break;
    case DOWN:
        child->zero_pos.x++;
        child->where = 'D';
        break;
    case LEFT:
        child->zero_pos.y--;
        child->where = 'L';
        break;
    default:
        /* NOTREACHED */
        assert(0);
    }
    tmp_val = child->board[child->zero_pos.x][child->zero_pos.y];
    child->board[child->zero_pos.x][child->zero_pos.y] = 0;
    child->board[old_pos.x][old_pos.y] =tmp_val;

    child->h_value = calculate_h_value(child->board);
    return child;
}

void init_h_value(board_instance *instance)
{
}

instance_list *open_list = NULL;
instance_list *close_list = NULL;

int close_list_find(board_instance *ins)
{
    board_instance *cursor = close_list;
    while (cursor != NULL) {
        if (0 == memcmp(ins->board, cursor->board, 16)) {
            return 1;
        }
        cursor = cursor->next;
    }

    return 0;
}

void close_list_add(board_instance *ins)
{
    if (NULL == close_list) {
        close_list = ins;
        close_list->next = NULL;
    } else {
        ins->next = close_list->next;
        close_list = ins;
    }
}

void open_list_add(board_instance *ins)
{
    board_instance *cursor = open_list;
    board_instance *pre_cursor = open_list;

    if (NULL == open_list) {
        open_list = ins;
        return;
    } else {
        if (is_board_instance_same(ins, cursor)) {
            if (FVALUE(ins) < FVALUE(cursor)) {
                ins->next = cursor->next;
                free(cursor);
            }
            return;
        }
        cursor = cursor->next;
        while (cursor != NULL) {
            if (is_board_instance_same(ins, cursor)) {
                if (FVALUE(ins) < FVALUE(cursor)) {
                    ins->next = cursor->next;
                    free(cursor);
                    pre_cursor->next = ins;
                }
                return;
            }
            pre_cursor = cursor;
            cursor = cursor->next;
        }
        pre_cursor->next = ins;
        ins->next = NULL;
    }
}

board_instance *open_list_remove_smallest()
{
    board_instance *smallest = open_list;
    board_instance *pre_smallest = open_list;
    board_instance *pre_cursor = open_list;
    board_instance *cursor = open_list;

    if (NULL == cursor->next) {
        open_list = NULL;
        return smallest;
    } else {
        cursor = cursor->next;
        while (cursor != NULL) {
            if (FVALUE(smallest) > FVALUE(cursor)) {
                smallest = cursor;
                pre_smallest = pre_cursor;
            }
            pre_cursor = cursor;
            cursor = cursor->next;
        }
        if (smallest == open_list) {
            open_list = smallest->next;
        }
        pre_smallest->next = smallest->next;
        smallest->next = NULL;
        return smallest;
    }
}

int is_result_instance(board_instance *ins)
{
    if (0 == memcmp(ins->board, result_board, 16)) {
        //__asm int 3

        return 1;
    } else {
        return 0;
    }
}


/* DEBUG */
void open_list_show()
{
    int i, j;
    board_instance *cursor = open_list;

    printf("-------------------------------------------\n");
    while (cursor != NULL) {
        printf("**************\n");
        printf("g_value+h_value=%d\n", cursor->h_value+cursor->g_value);
        for (i = 0; i < 4; i++) {
            for (j = 0; j < 4; j++) {
                printf("%d\t", cursor->board[i][j]);
            }
            printf("\n");
        }
        cursor = cursor->next;
    }
}

/*
 * Return 0: The open list is empty.
 * Return 1: Expand successfully.
 * Return 2: Reach the end.
 */
int open_list_expand()
{
    board_instance *smallest;
    board_instance *tmp_instance;

    smallest = open_list_remove_smallest();
    if (NULL == smallest) {
        return 0;
    }
    printf("%d\n", smallest->h_value+smallest->g_value);
    show_instance(smallest);
    if (smallest->zero_pos.y != 0) {
        tmp_instance = board_instance_new_child(smallest, LEFT);
        if (is_result_instance(tmp_instance)) {
            final_instance = tmp_instance;
            return 2;
        }
        if (!close_list_find(tmp_instance)) {
            open_list_add(tmp_instance);
        } else {
            free(tmp_instance);
        }
    }
    if (smallest->zero_pos.y != 3) {
        tmp_instance = board_instance_new_child(smallest, RIGHT);
        if (is_result_instance(tmp_instance)) {
            final_instance = tmp_instance;
            return 2;
        }
        if (!close_list_find(tmp_instance)) {
            open_list_add(tmp_instance);
        } else {
            free(tmp_instance);
        }
    }
    if (smallest->zero_pos.x != 0) {
        tmp_instance = board_instance_new_child(smallest, UP);
        if (is_result_instance(tmp_instance)) {
            final_instance = tmp_instance;
            return 2;
        }
        if (!close_list_find(tmp_instance)) {
            open_list_add(tmp_instance);
        } else {
            free(tmp_instance);
        }
    }
    if (smallest->zero_pos.x != 3) {
        tmp_instance = board_instance_new_child(smallest, DOWN);
        if (is_result_instance(tmp_instance)) {
            final_instance = tmp_instance;
            return 2;
        }
        if (!close_list_find(tmp_instance)) {
            open_list_add(tmp_instance);
        } else {
            free(tmp_instance);
        }
    }

    close_list_add(smallest);

    return 1;
}


void show_the_path()
{
    board_instance *ins = final_instance;

    while (ins != NULL) {
        //show_instance(ins);

        //printf("----------------------------\n");

        printf("%c", ins->where);
        ins = ins->parent;
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    char input_board[4][4];
    int val;
    char *p_unit = (char *)input_board;
    int i;
    int rc;
    board_instance *start_instance = NULL;
    board_instance *tmp_instance = NULL;
    board_instance *cur_instance = NULL;

    for (i = 0; i < 16; i++) {
        scanf("%d", &val);
        *(p_unit+i) = (char)val;
    }

    /* DEBUG */
    //printf("%d\n", calculate_h_value(input_board));

    //exit(0);


    if (!is_possible(input_board)) {
        printf("This puzzle is not solvable.\n");
        return 1;
    }

    start_instance = board_instance_new(input_board);
    cur_instance = start_instance;
    open_list_add(cur_instance);

    //open_list_show();

    while (1) {
        rc = open_list_expand();
        //open_list_show();

        if (rc == 0) {
            printf("Open list is empty.\n");
            exit(1);
        }
        if (2 == rc) {
            printf("Get the result.\n");

            show_the_path();
            exit(0);
        }
    }

    return 0;
}