/* gcc -o 8puzzle 8puzzle.c `allegro-config --libs` */

#define _XOPEN_SOURCE 500

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <allegro.h>

#define TILE_SIZE 70
#define SIZE 3
#define BORDER 1

typedef int STATE[SIZE][SIZE];

int find_x(STATE, int);
int find_y(STATE, int);

int are_equal(STATE, STATE);

void r1_apply(STATE);
int r1_can_apply(STATE);
void r2_apply(STATE);
int r2_can_apply(STATE);
void r3_apply(STATE);
int r3_can_apply(STATE);
void r4_apply(STATE);
int r4_can_apply(STATE);

int main(int argc, char **argv)
{
    STATE state, goal;
    int i, j, k;
    PALETTE palette;
    BITMAP *bits[SIZE * SIZE + 1];
    void (*rules[])(STATE) = { &r1_apply,
                               &r2_apply,
                               &r3_apply,
                               &r4_apply };
    int (*ruletests[])(STATE) = { &r1_can_apply,
                                  &r2_can_apply,
                                  &r3_can_apply,
                                  &r4_can_apply };

    /* Initialise starting and goal states. */
    for (i = 0, k = 1; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            state[i][j] = goal[i][j] = k++;
    state[SIZE - 1][SIZE - 1] = goal[SIZE - 1][SIZE - 1] = 0;

    /* Randomly permute our starting state a bit. */
    srandom((unsigned int)time(NULL));
    for (i = 0; i < 50 + random() % 10; ++i) {
        k = random() % 4;
        if (ruletests[k](state))
            rules[k](state);
        else
            --i;
    }

    /* Print the starting state in a Python-compatible form. */
    printf("[");
    for (i = 0; i < SIZE; ++i) {
        printf("[");
        for (j = 0; j < SIZE; ++j)
            printf("%d%s", state[j][i], j == SIZE - 1 ? "]" : ", ");
        printf("%s", i == SIZE - 1 ? "]\n" : ", ");
    }

    /* Initialise Allegro and create the game window. */
    allegro_init();
    install_keyboard();

    if ((k = desktop_color_depth()) != 0)
        set_color_depth(k);
    if (set_gfx_mode(GFX_AUTODETECT_WINDOWED,
                     SIZE * TILE_SIZE, SIZE * TILE_SIZE,
                     0, 0) != 0)
        return 1;

    /* Load puzzle image. */
    bits[SIZE * SIZE] = load_bitmap(argc > 1 ? argv[1]
                                             : "image.pcx", palette);
    if (!bits[SIZE * SIZE]) {
        fprintf(stderr, "Could not load bitmap!\n");
        return 1;
    }

    /* Chop image into tiles, and display tiles in goal configuration. */
    for (i = 0, k = 1; i < SIZE; ++i) {
        for (j = 0; j < SIZE; ++j) {
            if (i == SIZE - 1 && j == SIZE - 1) break;
            bits[k] = create_bitmap(TILE_SIZE, TILE_SIZE);
            blit(bits[SIZE * SIZE], bits[k],
                 TILE_SIZE * i + BORDER, TILE_SIZE * j + BORDER,
                 BORDER, BORDER,
                 TILE_SIZE - 2 * BORDER, TILE_SIZE - 2 * BORDER);
            blit(bits[k], screen,
                 0, 0,
                 TILE_SIZE * i, TILE_SIZE * j,
                 TILE_SIZE, TILE_SIZE);
            ++k;
        }
    }
    bits[0] = create_bitmap(TILE_SIZE, TILE_SIZE);
    blit(bits[0], screen,
         0, 0,
         TILE_SIZE * (SIZE - 1), TILE_SIZE * (SIZE - 1),
         TILE_SIZE, TILE_SIZE);

    sleep(2);

    /* Display the starting configuration. */
    for (i = 0; i < SIZE; ++i) {
        for (j = 0; j < SIZE; ++j) {
            k = state[i][j];
            blit(bits[state[i][j]], screen, 0, 0,
                 TILE_SIZE * i, TILE_SIZE * j, TILE_SIZE, TILE_SIZE);
        }
    }

    /* Main loop. */
    while (!are_equal(state, goal)) {
        k = readkey() >> 8;
        k = k == KEY_LEFT  ? 0
          : k == KEY_UP    ? 1
          : k == KEY_RIGHT ? 2
          : k == KEY_DOWN  ? 3
          : -1;

        if (k == -1) {
            printf("Exiting.\n");
            return 0;
        }

        if (ruletests[k](state)) {
            int x1 = find_x(state, 0),
                y1 = find_y(state, 0),
                x2, y2;

            rules[k](state);

            x2 = find_x(state, 0);
            y2 = find_y(state, 0);

            blit(bits[state[x1][y1]], screen, 0, 0,
                 x1 * TILE_SIZE, y1 * TILE_SIZE, TILE_SIZE, TILE_SIZE);
            blit(bits[0], screen, 0, 0,
                 x2 * TILE_SIZE, y2 * TILE_SIZE, TILE_SIZE, TILE_SIZE);
        }
        clear_keybuf();
    }

    /* Done, so display the puzzle image and wait to exit. */
    blit(bits[SIZE * SIZE], screen,
         0, 0, 0, 0, TILE_SIZE * SIZE, TILE_SIZE * SIZE);
    while (!keypressed());

    return 0;

} END_OF_MAIN()

int find_x(STATE state, int tile)
{
    int i, j;

    for (i = 0; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            if (state[i][j] == tile)
                return i;

    return -1;
}

int find_y(STATE state, int tile)
{
    int i, j;

    for (i = 0; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            if (state[i][j] == tile)
                return j;

    return -1;
}

int are_equal(STATE s1, STATE s2)
{
    int i, j;

    for (i = 0; i < SIZE; ++i)
        for (j = 0; j < SIZE; ++j)
            if (s1[i][j] != s2[i][j])
                return 0;

    return 1;
}

void r1_apply(STATE state)
{
    int x = find_x(state, 0),
        y = find_y(state, 0);

    state[x][y] = state[x - 1][y];
    state[x - 1][y] = 0;
}
int r1_can_apply(STATE state)
{
    return find_x(state, 0) > 0;
}

void r2_apply(STATE state)
{
    int x = find_x(state, 0),
        y = find_y(state, 0);

    state[x][y] = state[x][y - 1];
    state[x][y - 1] = 0;
}
int r2_can_apply(STATE state)
{
    return find_y(state, 0) > 0;
}

void r3_apply(STATE state)
{
    int x = find_x(state, 0),
        y = find_y(state, 0);

    state[x][y] = state[x + 1][y];
    state[x + 1][y] = 0;
}
int r3_can_apply(STATE state)
{
    return find_x(state, 0) < SIZE - 1;
}

void r4_apply(STATE state)
{
    int x = find_x(state, 0),
        y = find_y(state, 0);

    state[x][y] = state[x][y + 1];
    state[x][y + 1] = 0;
}
int r4_can_apply(STATE state)
{
    return find_y(state, 0) < SIZE - 1;
}