/* 15 puzzle */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

typedef enum _Boolean { False = 0, True = -1 } Boolean;

Boolean confirm(char const *msg) {
	char str[256];
	for (;;) {
		if (msg != NULL) {
			printf(msg);
		}
		printf(" [y/n]? ");
		fgets(str, 256, stdin);
		str[0] = tolower(str[0]);
		if (str[0] == 'y') {
			return True;
		} else if (str[0] == 'n') {
			return False;
		}
	}
}

void initPuzzle(int puzzle[4][4]) {
	int i, j, n = 1;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++) {
			puzzle[i][j] = n & 0xF;
			n++;
		}
	}
}

Boolean checkPuzzle(int const puzzle[4][4]) {
	int i, j, n = 1;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++) {
			if (puzzle[i][j] != (n & 0xF)) {
				return False;
			}
			n++;
		}
	}
	return True;
}

int movePanels(int puzzle[4][4], int const number) {
	int xs = -1, ys = -1, xn = -2, yn = -2;
	int i, j, m;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++) {
			if (puzzle[i][j] == number) {
				xn = j;
				yn = i;
			} else if (puzzle[i][j] == 0) {
				xs = j;
				ys = i;
			}
		}
	}
	if (xs != xn && ys != yn) {
		return 0;
	}
	if (xs > xn) {
		for (j = xs; j > xn; j--) {
			puzzle[ys][j] = puzzle[ys][j - 1];
		}
		m = xs - xn;
	} else if (xs < xn) {
		for (j = xs; j < xn; j++) {
			puzzle[ys][j] = puzzle[ys][j + 1];
		}
		m = xn - xs;
	} else if (ys > yn) {
		for (i = ys; i > yn; i--) {
			puzzle[i][xs] = puzzle[i - 1][xs];
		}
		m = ys - yn;
	} else /* if (ys < yn) */ {
		for (i = ys; i < yn; i++) {
			puzzle[i][xs] = puzzle[i + 1][xs];
		}
		m = yn - ys;
	}
	puzzle[yn][xn] = 0;
	return m;
}

void shuffle(int puzzle[4][4], int const times) {
	int i, j, t;
	int xs, ys;
	int p, k = 0;
	
	for (t = 0; t < times; t++) {
		
		for (i = 0; i < 4; i++) {
			for (j = 0; j < 4; j++) {
				if (puzzle[i][j] == 0) {
					xs = j;
					ys = i;
					goto loopescape;
				}
			}
		}
		loopescape:
		
		p = rand() % 3;
		
		if (k == 0) {
			for (i = 0; i < 4; i++) {
				if (puzzle[i][xs] == 0) {
					continue;
				}
				if (p == 0) {
					movePanels(puzzle, puzzle[i][xs]);
					break;
				} else {
					p--;
				}
			}
		} else {
			for (j = 0; j < 4; j++) {
				if (puzzle[ys][j] == 0) {
					continue;
				}
				if (p == 0) {
					movePanels(puzzle, puzzle[ys][j]);
					break;
				} else {
					p--;
				}
			}
		}
		k = !k;
	}
}

void printPuzzle(int const puzzle[4][4]) {
	int i, j;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++) {
			if (j > 0) {
				putchar(' ');
			}
			if (puzzle[i][j] > 0) {
				printf("%2d", puzzle[i][j]);
			} else {
				putchar(' ');
				putchar('*');
			}
		}
		putchar('\n');
	}
}

Boolean game(void) {
	Boolean complete = False;
	int n, p, t, m;
	int puzzle[4][4];
	char str[256];
	
	initPuzzle(puzzle);
	
	shuffle(puzzle, 1000);
	
	t = 0;
	
	for (;;) {
		
		loophead:
		
		printf("---------------------- %d moves\n", t);
		printPuzzle(puzzle);
		printf("move number [1-15]? ");
		fgets(str, 256, stdin);
		
		for (p = 0; isprint(str[p]); p++) {
			if (!isdigit(str[p])) {
				if (confirm("do you give up") == True) {
					puts("gave up");
					goto gameend;
				} else {
					goto loophead;
				}
			}
		}
		
		if (strlen(str) > 3) {
			puts("illegal number");
			continue;
		}
		
		n = atoi(str);
		
		m = movePanels(puzzle, n);
		
		if (m == 0) {
			if (n > 0 && n < 16) {
				puts("cannot move");
			} else {
				puts("illegal number");
			}
			continue;
		} else {
			t += m;
		}
		
		if (checkPuzzle(puzzle) == True) {
			printf("complete (total %d moves)", t);
			complete = True;
			goto gameend;
		}
	}
	gameend:
	
	return complete;
}

int main(void) {
	
	srand((unsigned)time(NULL));
	
	puts("* 15 puzzle *");
	
	do {
		if (game() == False) {
			break;
		}
	} while (confirm("do you continue") == True);
	
	return 0;
}