/*
	16 puzzle problem

		- 8~9는 옳다고 가정하고 1~7에 대해서만 적용
		- 1과 2의 위치만 바뀌었을 때 1...7 순서를 찾는 프로그램

	1...7 을 'A'...'G'로 mapping하여 구현 --> 15까지 확장하려면
	비어있는 cell은 '@' 문자
*/
#include <stdio.h>
#include <string.h>

#define N_SYMBOLS	8
#define EMPTY_SYMBOL	'@'
#define MAX_STATES	50000

#define SOURCE	"@BACDEFG"
#define TARGET	"@ABCDEFG"

/*
	- Breadth-First Search 알고리즘
	- 초기상태로부터 도달 가능한 모든 상태를 저장
*/
long n=0;	/* number of entries for 's' */
char s[MAX_STATES][N_SYMBOLS+1];	/* 도달 가능한 모든 상태를 저장 */

int move_up(int i, char x[])
{
	x[i] = x[i-4];
	x[i-4] = EMPTY_SYMBOL;
	return i-4;
}

int move_down(int i, char x[])
{
	x[i] = x[i+4];
	x[i+4] = EMPTY_SYMBOL;
	return i+4;
}

int move_left(int i, char x[])
{
	x[i] = x[i-1];
	x[i-1] = EMPTY_SYMBOL;
	return i-1;
}

int move_right(int i, char x[])
{
	x[i] = x[i+1];
	x[i+1] = EMPTY_SYMBOL;
	return i+1;
}

put_cells(char *space, char x[])
{
	int i;

	printf("%s", space);
	for (i = 0; i < 4; i++) printf("%d", x[i]-EMPTY_SYMBOL);
	printf("\n");

	printf("%s", space);
	for (i = 4; i < 8; i++) printf("%d", x[i]-EMPTY_SYMBOL);
	printf(":%s\n", x);
}

/*
	if 'x' doesn't exist, added it.
*/
void add_new_state(char x[])
{
	long i;

	if (!strcmp(x, TARGET)) {
		printf("O.K.");
		exit(0);
	}

	for (i = 0; i < n; i++)
		if (!strcmp(x, s[i])) return;

	if (n < MAX_STATES-1) strcpy(s[n++], x);
	else { puts("STACK OVERFLOW!"); exit(0); }

	put_cells("\t", x);
}

void expand(long k)	/* expand s[k] */
{
	char x[N_SYMBOLS+1];
	int i;	/* empty-cell position */

	strcpy(x, s[k]);
	for (i = 0; i < N_SYMBOLS; i++)
		if (x[i] == EMPTY_SYMBOL) break;

put_cells("", x);

	switch (i) {
	case 0:
		i = move_down(i, x);
		add_new_state(x);
		i = move_up(i, x);

		i = move_right(i, x);
		add_new_state(x);
		break;
	case 1:
	case 2:
		i = move_down(i, x);
		add_new_state(x);
		i = move_up(i, x);

		i = move_left(i, x);
		add_new_state(x);
		i = move_right(i, x);

		i = move_right(i, x);
		add_new_state(x);
		break;
	case 3:
		i = move_down(i, x);
		add_new_state(x);
		i = move_up(i, x);

		i = move_left(i, x);
		add_new_state(x);
		break;
	case 4:
		i = move_up(i, x);
		add_new_state(x);
		i = move_down(i, x);

		i = move_right(i, x);
		add_new_state(x);
		break;
	case 5:
	case 6:
		i = move_up(i, x);
		add_new_state(x);
		i = move_down(i, x);

		i = move_left(i, x);
		add_new_state(x);
		i = move_right(i, x);

		i = move_right(i, x);
		add_new_state(x);
		break;
	case 7:
		i = move_up(i, x);
		add_new_state(x);
		i = move_down(i, x);

		i = move_left(i, x);
		add_new_state(x);
		break;
	}
}

/*
	'n' is increased by 'expand()'
*/
void BFS()
{
	long i;

	for (i = 0; i < n; i++) expand(i);	/* expand s[i] */
}

void main()
{
	strcpy(s[n++], SOURCE);
	BFS();
	puts("BFS ended!");
}