#include <stdio.h>


/******************  MUST BE OPPOSITES ******************/
#define LEFT 1
#define RIGHT -1
#define UP 2
#define DOWN -2
#define EMPTY_STACK -3

#define OPTIMIZATION

#ifdef OPTIMIZATION
#define MAX_MOVES 1000	// for large ones this may not be enough
			// However this is only used for optimization and can
			// be omitted
			// There is a way to shrink this with practicaly no loss
			// in optimization but doesn't fit in this margin
			//
			//  :-P Fermat
int move_stack[MAX_MOVES];	// for optimization
int stack_top=0;
#endif

int move_count;		// Unoptimized moves;



#define columns 3
#define rows 3

int solution[rows][columns]= { 	{ 1, 2, 3 }, 
				{ 4, 5, 6 }, 
				{ 7, 8, 0 } };

int current[rows][columns]= {	{ 4, 5, 7 },
				{ 3, 1, 2 },
				{ 6, 8, 0 } };





/*
#define columns 4
#define rows 8

int solution[rows][columns]= {  { 1, 2, 3, 4 },
				{ 5, 6, 7, 8 },
				{ 9, 10, 11, 12 },
				{ 13, 14, 15, 16 },
				{ 17, 18, 19, 20 },
				{ 21, 22, 23, 24 },
				{ 25, 26, 27, 28 },
				{ 29, 30, 31, 0 } };

int current[rows][columns]= {	{ 19, 9, 5, 14 },
				{ 8, 18, 30, 7 },
				{ 29, 4, 28, 24 },
				{ 12, 13, 1, 6 },
				{ 20, 11, 0, 15 },
				{ 2, 31, 16, 25 },
				{ 21, 17, 3, 26 },
				{ 10, 22, 23, 27 } };
*/




int b_row, b_column;	// where the blank one is
int t_row, t_column;	// target square

void get_blank() {
	int i,j;
	for(i=0; i<columns; i++) {
		for(j=0; j<rows; j++) {
			if (current[j][i]==0) {
				b_row=j;
				b_column=i;
				return;
			}
		}
	}
}

void get_target_square(int target_num) {
	int i,j;
//	printf("going for \"%d\"\n", target_num);
	for(i=0; i<columns; i++) {
		for(j=0; j<rows; j++) {
			if (current[j][i]==target_num) {
				t_row=j;
				t_column=i;
				return;
			}
		}
	}
}


void print_current()
{
	int i, j;
	for(i=0; i<rows; i++) {
		for(j=0; j<columns; j++) {
			printf(" %d ", current[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

#ifdef OPTIMIZATION
void push_move(int direction) {
	if (direction == EMPTY_STACK) return;
	move_stack[stack_top++]=direction;
}

int pop_move() {
	if (stack_top==0) return(-3);
	return(move_stack[--stack_top]);
}
#endif


void move_blank (int direction)  // Only this one changes the board
{
	int b_new_row, b_new_column;
	int last;
	int printit=1;
#ifdef OPTIMIZATION
	if((last=pop_move()) != -direction) {
		push_move(last);
		push_move(direction);
	}
#endif
	move_count++;
	if(printit) printf("move: ");
	switch (direction) {
		case UP:
			b_new_row=b_row-1;
			b_new_column=b_column;
			if(printit) printf("UP\n");
			break;
		case DOWN:
			b_new_row=b_row+1;
			b_new_column=b_column;
			if(printit) printf("DOWN\n");
			break;
		case LEFT:
			b_new_row=b_row;
			b_new_column=b_column-1;
			if(printit) printf("LEFT\n");
			break;
		case RIGHT:
			b_new_row=b_row;
			b_new_column=b_column+1;
			if(printit) printf("RIGHT\n");
			break;
	}
	current[b_row][b_column]=current[b_new_row][b_new_column];
	current[b_new_row][b_new_column]=0;
	b_row=b_new_row;
	b_column=b_new_column;

}

int check_move_target(int direction)	// Stupid function... must be called
{
	int bt_row, bt_column;
	bt_row=t_row;
	bt_column=t_column;
	switch(direction) {
		case UP:
			bt_row--;
			break;
		case DOWN:
			bt_row++;
			break;
		case LEFT:
			bt_column--;
			break;
		case RIGHT:
			bt_column++;
			break;
	}
	if(bt_column!=b_column || bt_row !=b_row ) {
		printf("SCREWED UP BADLY\n");
		return(-1);
	}
	t_row=bt_row;
	t_column=bt_column;
	move_blank(-direction);		// Because they're opposites
	return(1);
}


void third_quarter()		// BS function
{
	if (b_row<t_row) {
		if(b_column==t_column) {
			if (b_column<columns-1) move_blank(RIGHT);
			else move_blank(LEFT);
		}
		while(b_row<t_row && b_row<rows-1) move_blank(DOWN);
	}
	if(b_column<t_column && b_column<columns-1) {
		if(b_row==t_row) {
			if(b_row<rows-1) move_blank(DOWN);
			else move_blank(UP);
		}
		while(b_column<t_column && b_column<columns-1) move_blank(RIGHT);
	}
}

void blank_approach_target()		// To fix a bug
{
	third_quarter();
	if(b_row>t_row) {
		while(b_row>t_row+1) move_blank(UP);
	}
	else {
		while(b_row<t_row-1) move_blank(DOWN);
	}

	if (b_column>t_column) {
		while(b_column>t_column+1) move_blank(LEFT);
	}
	else {
		while(b_column<t_column-1) move_blank(RIGHT);
	}
}


void move_target(int direction)
{
	blank_approach_target();
	switch(direction) {
		case UP:
			if (t_column==b_column && t_row<b_row) {
				// detour
				if (b_column< columns-1) 
					move_blank(RIGHT);
				else
					move_blank(LEFT);
			}
			while(t_row-1>b_row) move_blank(DOWN);
			while(t_row-1<b_row) move_blank(UP);
			while(t_column>b_column) move_blank(RIGHT);
			while(t_column<b_column) move_blank(LEFT);
			break;
		case DOWN:
			if (t_column==b_column && t_row>b_row) {
				// detour
				if (b_column< columns-1) 
					move_blank(RIGHT);
				else
					move_blank(LEFT);
			}
			while(t_row+1>b_row) move_blank(DOWN);
			while(t_row+1<b_row) move_blank(UP);
			while(t_column>b_column) move_blank(RIGHT);
			while(t_column<b_column) move_blank(LEFT);
			break;
		case LEFT:
			if (t_row==b_row && t_column<b_column) {
				// detour
				if(b_row<rows-1)
					move_blank(DOWN);
				else
					move_blank(UP);
			}
			while(t_column-1>b_column) move_blank(RIGHT);
			while(t_column-1<b_column) move_blank(LEFT);
			while(t_row>b_row) move_blank(DOWN);
			while(t_row<b_row) move_blank(UP);
			break;
		case RIGHT:
			if (t_row==b_row && t_column>b_column) {
				// detour
				if(b_row<rows-1)
					move_blank(DOWN);
				else
					move_blank(UP);
			}
			while(t_column+1>b_column) move_blank(RIGHT);
			while(t_column+1<b_column) move_blank(LEFT);
			while(t_row>b_row) move_blank(DOWN);
			while(t_row<b_row) move_blank(UP);
			break;
	}
	check_move_target(direction);
}





void solve_column(int column)
{
	int i;

	for(i=0; i<rows-2; i++) {
		if(current[i][column] != solution[i][column]) {
			get_target_square(solution[i][column]);
			while(t_row>i) move_target(UP);
			while(t_row<i) move_target(DOWN);
print_current();
			while(t_column>column) move_target(LEFT);
			while(t_column<column) move_target(RIGHT);
			if(b_column<columns-1) move_blank(RIGHT);
print_current();
		}
	}
	if(current[rows-2][column] != solution[rows-1][column]) {
		get_target_square(solution[rows-1][column]);
		while(t_row>rows-2) move_target(UP);
		while(t_row<rows-2) move_target(DOWN);
print_current();
		while(t_column>column) move_target(LEFT);
		while(t_column<column) move_target(RIGHT);
		if(b_column<columns-1) move_blank(RIGHT);
print_current();
	}
	if(b_column<columns-1) move_blank(RIGHT);
	if(b_column<columns-1) move_blank(RIGHT);
	if(current[rows-1][column] == solution[rows-2][column]) {
		// special case : known as tyflosoyrths
		while(b_row<rows-1) move_blank(DOWN);
		while(b_column<column+2) move_blank(RIGHT);
		while(b_column>column+2) move_blank(LEFT);
		move_blank(LEFT);
		move_blank(LEFT);
		move_blank(UP);
		move_blank(RIGHT);
		move_blank(RIGHT);
		move_blank(DOWN);
		move_blank(LEFT);
		move_blank(UP);
		move_blank(LEFT);
		move_blank(DOWN);
		move_blank(RIGHT);
	}
print_current();
	get_target_square(solution[rows-2][column]);
	while(t_column>column+1) move_target(LEFT);
	while(t_row>rows-2) move_target(UP);
	while(t_row<rows-2) move_target(DOWN);
	while(b_column<column+2) move_blank(RIGHT);
	while(b_row<rows-1) move_blank(DOWN);
	// small tyflosoyrths
	move_blank(LEFT);
	move_blank(LEFT);
	move_blank(UP);
	move_blank(RIGHT);
print_current();
}



void solve_row(int row)
{
	int i;

	for(i=0; i<columns-2; i++) {
		if(current[row][i] != solution[row][i]) {
			get_target_square(solution[row][i]);
			while(t_column>i) move_target(LEFT);
			while(t_column<i) move_target(RIGHT);
print_current();
			while(t_row>row) move_target(UP);
			while(t_row<row) move_target(DOWN);
			if(b_row<rows-1) move_blank(DOWN);
print_current();
		}
	}
	if(current[row][columns-1] != solution[row][columns-2]) {
		get_target_square(solution[row][columns-2]);
		while(t_column<columns-1) move_target(RIGHT);
print_current();
		while(t_row>row) move_target(UP);
		while(t_row<row) move_target(DOWN);
		if(b_row<rows-1) move_blank(DOWN);
print_current();
	}
	if(b_row<rows-1) move_blank(DOWN);
	if(b_row<rows-1) move_blank(DOWN);

	if(current[row][columns-2] == solution[row][columns-1]) {
		// special case : known as tyflosoyrths
		while(b_column<columns-2) move_blank(RIGHT);
		while(b_column>columns-2) move_blank(LEFT);

		while(b_row<row+2) move_blank(DOWN);
		while(b_row>row+2) move_blank(UP);
		move_blank(UP);
		move_blank(UP);
		move_blank(RIGHT);
		move_blank(DOWN);
		move_blank(DOWN);
		move_blank(LEFT);
		move_blank(UP);
		move_blank(RIGHT);
		move_blank(UP);
		move_blank(LEFT);
		move_blank(DOWN);
	}
print_current();
	get_target_square(solution[row][columns-1]);
	while(t_row>row+1) move_target(UP);
	while(t_column<columns-1) move_target(RIGHT);

	while(b_row<row+2) move_blank(DOWN);
	while(b_row>row+2) move_blank(UP);
	while(b_column>columns-2) move_blank(LEFT);
	while(b_column<columns-2) move_blank(RIGHT);
	// small tyflosoyrths
	move_blank(UP);
	move_blank(UP);
	move_blank(RIGHT);
	move_blank(DOWN);
print_current();

}




void main() {

	int i;
	get_blank();
//	print_current();
	for(i=0; i<columns-2; i++) {
		solve_column(i);
	}
	for(i=0; i<rows-2; i++) {
		solve_row(i);
	}
	while(b_row<rows-1) move_blank(DOWN);
	while(b_column<columns-1) move_blank(RIGHT);
	print_current();

#ifdef OPTIMIZATION
printf("\n\n This is the REAL solution\n");
	for(i=0; i<stack_top; i++) {
		switch(move_stack[i]) {
			case UP:
				printf("move: UP\n");
				break;
			case DOWN:
				printf("move: DOWN\n");
				break;
			case LEFT:
				printf("move: LEFT\n");
				break;
			case RIGHT:
				printf("move: RIGHT\n");
				break;
		}
	}
	printf("\ntotal moves: %d\n(unoptimized moves: %d)\n", stack_top, move_count);
#endif
}