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

#define N 4
#define TABSIZE	100000000
#define PRIME	2147483647  // Mersenne prime

char solution[N][N] = 	{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
char *board;		    // the current board config
#define	entry(y,x)  board[(y)*N+(x)]
int pred[TABSIZE];	    // predecessor configurations

/*
 * A simple ringbuffer queue.
 */
int queue[TABSIZE];
int queueh = 0, queuet = 0;
void enqueue(int which) {
    queue[queueh++] = which;
    queueh %= TABSIZE;
}
int dequeue() {
    int res = queue[queuet++];
    queuet %= TABSIZE;
    return res;
}

/*
 * The previously visited configurations.
 * Hash table with linear probing.
 */
char seen[TABSIZE*N*N];
char filled[TABSIZE];
int hash() {
    int h = 37;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
	    h = (h*127 + entry(i,j)) % PRIME;
	    if (h < 0) h += PRIME;
	}
    return h % TABSIZE;
}
/*
 * Store current entry at position pos.
 */
void store(int pos) {
    memcpy(seen+pos*N*N, board, N*N);
    filled[pos] = 1;
}
/*
 * Find position of current entry or position of next free slot.
 */
int find() {
    int h = hash();
    int start = h;
    while (filled[h]) {	// linear probing
	char *p = seen+h*N*N;
	if (p != board)	// ignore the current, temporary position
	    if (memcmp(p, board, N*N) == 0)
		return h;
	h = (h + 1) % TABSIZE;
	if (start == h) {   // check for turnovers
	    fprintf(stderr, "Memory exhausted!\n");
	    exit(1);
	}
    } while (filled[h]);
    return h;
}

/*
 * Output the board.
 */
void print() {
    int i, j;
    for (i = 0; i < N; i++) {
	for (j = 0; j < N; j++) {
	    if (entry(i,j) > 0)
		printf("%X ", entry(i,j));
	    else
		printf("  ");
	}
	printf("\n");
    }
    printf("\n");
}

/*
 * Apply moves to the current board.
 * Returns 0 if the move is not allowed
 * and 1 else.
 */
int move(int y, int x) {
    int starty	= y < 0 ? 1 : 0;
    int stopy	= y > 0 ? N-1 : N;
    int startx	= x < 0 ? 1 : 0;
    int stopx	= x > 0 ? N-1 : N;

    for (int i = starty; i < stopy; i++) {
	for (int j = startx; j < stopx; j++) {
	    if (entry(i, j) == 0) {
		entry(i, j) = entry(i+y, j+x);
		entry(i+y, j+x) = 0;
		return 1;
	    }
	}
    }
    return 0;
}

/*
 * Shortcuts for the four possible moves.
 */
int up() {
    return move(-1, 0);
}
int down() {
    return move(1, 0);
}
int left() {
    return move(0, -1);
}
int right() {
    return move(0, 1);
}
/*
 * Store the four move functions in an array funcs[],
 * set up in a way such that funcs[i] and funcs[(i+2) % 4]
 * cancel each other.
 */
int (*funcs[])() = { up, left, down, right }; 

int main(int argc, char **argv) {
    int count = 0;

    /* read input */
    board = seen;
    for (int i = 0; i < N; i++) {
    	for (int j = 0; j < N; j++) {
	    char in;
	    scanf("%c ", &in);
	    if (in == '*') entry(i, j) = 0;
	    if (in >= '0' && in <= '9') entry(i, j) = in - '0';
	    if (in >= 'A' && in <= 'F') entry(i, j) = in - 'A' + 10;
	}
    }
    filled[0] = 1;

    printf("Eingabe:\n");
    print();

    // enqueue start configuration
    enqueue(0);
    int next = 0;

    // as long as the queue is not empty
    while (queueh != queuet) {
	// get next configuration from queue
	next = dequeue();
	// setup pointer to current board config
	board = seen+next*N*N;

	// try all four directions
	for (int i = 0; i < 4; i++) {
	    int res = funcs[i]();
	    if (res == 0)   // invalid move
		continue;
	    int pos = find();
	    // stop if solution found
	    if (memcmp(board, solution, N*N) == 0) {
		// store final predecessor config
		store(pos);
		pred[pos] = next;
		next = pos;
		funcs[(i+2)%4](); // undo move
		goto stop;
	    }
	    // enqueue this configuration if not seen before
	    if (filled[pos] == 0) {
		count++;
		// some progress output
		if (count % 79000 == 0)
		    printf("\n");
		if (count % 1000 == 0) {
		    printf(".");
		    fflush(stdout);
		}
		// save new configuration and predecessor
		store(pos);
		pred[pos] = next;
		// enqueue this configuration
		enqueue(pos);
	    }
	    funcs[(i+2)%4](); // undo move
	}
    }
    printf("queue empty\n");
stop:
    // output solution by traversing predecessor array
    printf("\nLoesung: \n");
    int runs = 0;
    do {
	board = seen+next*N*N;
	print();
	next = pred[next];
	runs++;
    } while (next != 0);
    board = seen+next*N*N;
    print();
    printf("Konfigurationen besucht: %d, Schritte notwendig: %d\n", count, runs);
    return 0;
}