/*
 * (c) 2002 lukas schroeder <lukas@edeal.de>
 *
 * solve solitaire.
 *
 * Version: 1, 2002-02-17
 */

#include <stdio.h>

#define FALSE 0
#define TRUE 1

enum {
	DEAD = 0,
	FREE = 1,
	FULL = 2
};

enum {
	NONE = 0,
	UP = 1,
	DOWN = 2,
	LEFT = 4,
	RIGHT = 8
};

#define WIDTH 7
int __solved_board[WIDTH*WIDTH] = {
	DEAD, DEAD, FREE, FREE, FREE, DEAD, DEAD,
	DEAD, DEAD, FREE, FREE, FREE, DEAD, DEAD,
	FREE, FREE, FREE, FREE, FREE, FREE, FREE,
	FREE, FREE, FREE, FULL, FREE, FREE, FREE,
	FREE, FREE, FREE, FREE, FREE, FREE, FREE,
	DEAD, DEAD, FREE, FREE, FREE, DEAD, DEAD,
	DEAD, DEAD, FREE, FREE, FREE, DEAD, DEAD
};
int __board[WIDTH*WIDTH] = {
	DEAD, DEAD, FULL, FULL, FULL, DEAD, DEAD,
	DEAD, DEAD, FULL, FULL, FULL, DEAD, DEAD,
	FULL, FULL, FULL, FULL, FULL, FULL, FULL,
	FULL, FULL, FULL, FREE, FULL, FULL, FULL,
	FULL, FULL, FULL, FULL, FULL, FULL, FULL,
	DEAD, DEAD, FULL, FULL, FULL, DEAD, DEAD,
	DEAD, DEAD, FULL, FULL, FULL, DEAD, DEAD
};
int __moves[WIDTH*WIDTH] = { 0, };

struct move {
	struct {
		int x, y;
	} dest;
	int dir;
	int moves[WIDTH*WIDTH];
};
struct move __history[100];
int __current_move = 0;

#define FIELD(X, Y)  __board[(X)+(Y)*(WIDTH)]
#define MYFIELD(BOARD, X, Y)  BOARD[(X)+(Y)*(WIDTH)]
#define MOVES(X, Y)  __moves[(X)+(Y)*(WIDTH)]
#define MYMOVES(MOVES, X, Y)  MOVES[(X)+(Y)*(WIDTH)]
#define CURRENT()	(&__history[__current_move-1])
#define HISTORIC(I)	(&__history[I])

#define DIR_UP_X 0
#define DIR_UP_Y -1
#define DIR_UP			DIR_UP_X, DIR_UP_Y
#define DIR_DOWN_X 0
#define DIR_DOWN_Y 1
#define DIR_DOWN		DIR_DOWN_X, DIR_DOWN_Y
#define DIR_LEFT_X -1
#define DIR_LEFT_Y 0
#define DIR_LEFT		DIR_LEFT_X, DIR_LEFT_Y
#define DIR_RIGHT_X 1
#define DIR_RIGHT_Y 0
#define DIR_RIGHT		DIR_RIGHT_X, DIR_RIGHT_Y

static int can_move_in_dir(int x, int y, int dx, int dy)
{
	if (x + dx*2 >= 0 && x + dx*2 < WIDTH && y + dy*2 >= 0 && y + dy*2 < WIDTH) {
		if (FIELD(x+dx, y+dy) == FULL && FIELD(x+dx*2, y+dy*2) == FREE)
			return TRUE;
	}
	return FALSE;
}

static int moves_for_stone(int x, int y)
{
	int mask;
	switch(FIELD(x, y)) {
		case DEAD:
		case FREE:
			return NONE;
			break;
		case FULL:
			mask = NONE;
			if (can_move_in_dir(x, y, DIR_UP))
				mask |= UP;
			if (can_move_in_dir(x, y, DIR_DOWN))
				mask |= DOWN;
			if (can_move_in_dir(x, y, DIR_LEFT))
				mask |= LEFT;
			if (can_move_in_dir(x, y, DIR_RIGHT))
				mask |= RIGHT;
			break;
	}
	return mask;
}

static void get_valid_moves()
{
	int i,j;
	for (i = 0; i < WIDTH; i++)
		for (j = 0; j < WIDTH; j++) {
			MOVES(j, i) = moves_for_stone(j, i);
		}
}

static void do_move(int x, int y, int dir)
{
	int can = FALSE;
	int dx, dy;
	switch(dir) {
		case UP:
			can = can_move_in_dir(x, y, DIR_UP);
			dx = DIR_UP_X;
			dy = DIR_UP_Y;
			break;
		case DOWN:
			can = can_move_in_dir(x, y, DIR_DOWN);
			dx = DIR_DOWN_X;
			dy = DIR_DOWN_Y;
			break;
		case LEFT:
			can = can_move_in_dir(x, y, DIR_LEFT);
			dx = DIR_LEFT_X;
			dy = DIR_LEFT_Y;
			break;
		case RIGHT:
			can = can_move_in_dir(x, y, DIR_RIGHT);
			dx = DIR_RIGHT_X;
			dy = DIR_RIGHT_Y;
			break;
	};
	if (!can || FIELD(x, y) != FULL)
		return;

	FIELD(x, y) = FREE;
	FIELD(x+dx, y+dy) = FREE;
	FIELD(x+2*dx, y+2*dy) = FULL;


	__current_move++;

	CURRENT()->dest.x = x + 2*dx;
	CURRENT()->dest.y = y + 2*dy;
	CURRENT()->dir = dir;

	get_valid_moves();
	memcpy(CURRENT()->moves, __moves, sizeof(__moves));
}

static void undo_move()
{
	int x, y, dx, dy;

	if (__current_move <= 0)
		return;

	x = CURRENT()->dest.x;
	y = CURRENT()->dest.y;

	switch(CURRENT()->dir) {
		case UP:
			dx = DIR_UP_X;
			dy = DIR_UP_Y;
			break;
		case DOWN:
			dx = DIR_DOWN_X;
			dy = DIR_DOWN_Y;
			break;
		case LEFT:
			dx = DIR_LEFT_X;
			dy = DIR_LEFT_Y;
			break;
		case RIGHT:
			dx = DIR_RIGHT_X;
			dy = DIR_RIGHT_Y;
			break;
	}

	FIELD(x, y) = FREE;
	FIELD(x-dx, y-dy) = FULL;
	FIELD(x-2*dx, y-2*dy) = FULL;

	get_valid_moves();
	__current_move--;
}

static void dump_board(int *board, int *moves)
{
	int i, j;

	for (i = 0; i < WIDTH; i++) {
		for (j = 0; j < WIDTH; j++) {
			switch(MYFIELD(board, j, i)) {
				case DEAD:
					printf("x");
					break;
				case FREE:
					printf("*");
					break;
				case FULL:
					printf("%x", MYMOVES(moves, j, i));
					break;
			}
		}
		printf("\n");
	}
}

static void dump_history()
{
	char *dirstr;
	int x, y, dx, dy;
	int m;

	if (__current_move <= 0)
		return;

	for (m = 0; m < __current_move; m++) {
		x = HISTORIC(m)->dest.x;
		y = HISTORIC(m)->dest.y;
	
		switch(HISTORIC(m)->dir) {
			case UP:
				dirstr = "UP";
				dx = DIR_UP_X;
				dy = DIR_UP_Y;
				break;
			case DOWN:
				dirstr = "DOWN";
				dx = DIR_DOWN_X;
				dy = DIR_DOWN_Y;
				break;
			case LEFT:
				dirstr = "LEFT";
				dx = DIR_LEFT_X;
				dy = DIR_LEFT_Y;
				break;
			case RIGHT:
				dirstr = "RIGHT";
				dx = DIR_RIGHT_X;
				dy = DIR_RIGHT_Y;
				break;
		}
		printf("[%02d] %i, %i  %s\n", 1+m, 1+x-2*dx, 1+y-2*dy, dirstr);
	}
}

static int board_solved()
{
	return !memcmp(__board, __solved_board, sizeof(__solved_board));
}

static int get_next_move(int *moves, int *x, int *y, int *dir)
{
	int i, j;

	for (i = 0; i < WIDTH; i++)
		for (j = 0; j < WIDTH; j++) {
			if (FIELD(j, i) == FULL) {
				*dir = NONE;
				if (MYMOVES(moves, j, i) & UP)
					*dir = UP;
				else if (MYMOVES(moves, j, i) & DOWN)
					*dir = DOWN;
				else if (MYMOVES(moves, j, i) & LEFT)
					*dir = LEFT;
				else if (MYMOVES(moves, j, i) & RIGHT)
					*dir = RIGHT;

				if (*dir != NONE) {
					MYMOVES(moves, j, i) &= ~(*dir);
					*x = j;
					*y = i;
					return TRUE;
				}
			}
		}
	return FALSE;
}

static void bruteforce()
{
	int x, y, dir;

	while (get_next_move(CURRENT()->moves, &x, &y, &dir)) {
		do_move(x, y, dir);

		if (board_solved()) {
			printf("Game Solved.\n");
			dump_history();
			printf("\n");
			dump_board(__board, CURRENT()->moves);
			exit(0);
		}

		bruteforce();
		undo_move();
	}

}


int main(int argc, char **argv)
{
	int init_moves[WIDTH*WIDTH];
	int x, y, dir;

	setbuf(stdout, NULL);

	__current_move = 0;

	get_valid_moves();
	memcpy(init_moves, __moves, sizeof(__moves));

	printf("\n");
	while (get_next_move(init_moves, &x, &y, &dir)) {
		do_move(x, y, dir);
		dump_board(__board, __moves);
		printf("\n");
		bruteforce();
		undo_move();
	}

	return 0;
}