#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define NONE			0x000
#define LEFT			0x001
#define RIGHT			0x002
#define UP				0x004
#define DOWN			0x008

#define MAX_VALUE		9
#define MAX_DEPTH		3			// 최대 허용 깊이
#define FIND_NODE		10
#define MAX_STACK		100
#define MAX_NODE		4			// 최대 자식 노드 수

#define TRUE			1
#define FALSE			0

typedef struct _node {
	int value[9];					// 퍼즐 데이타
	int depth;						// 노드의 깊이
	int cursorPosition;				// 커서의 현재 위치
	int fromDirection;				// 커서가 어디로부터 왔는가
	struct _node *nextNode[4];		// 자식 노드 최대 4개
} PUZZLE;

PUZZLE stack[MAX_STACK];
int current_stack;

typedef int BOOL; 
BOOL isFirst;
int tempPosition;
int callCount;

void initialize(PUZZLE *pNode, PUZZLE *gNode);
int DFS(PUZZLE *pNode[], PUZZLE *gNode, int pCount, int pDepth);
int swapNodeValue(PUZZLE *childNode[], int i, int cursorPosition);
int getChildCount(int direction);
int	comparePuzzle(PUZZLE *pNode, PUZZLE *gNode);
int findDirection(PUZZLE *node);
void showDirection(PUZZLE *node, int direction);
void printCureentNode();

void push(PUZZLE *t);
PUZZLE pop(void);
int isEmptyStack(void);
void initStack(void);

int main()
{
	PUZZLE *iPuzzle;
	PUZZLE *gPuzzle;

	int i;

	iPuzzle=(PUZZLE*)malloc(sizeof(PUZZLE));
	gPuzzle=(PUZZLE*)malloc(sizeof(PUZZLE));

	iPuzzle->value[0]=2;
	iPuzzle->value[1]=8;
	iPuzzle->value[2]=3;
	iPuzzle->value[3]=1;
	iPuzzle->value[4]=6;
	iPuzzle->value[5]=4;
	iPuzzle->value[6]=7;
	iPuzzle->value[7]=0;
	iPuzzle->value[8]=5;

	gPuzzle->value[0]=1;
	gPuzzle->value[1]=2;
	gPuzzle->value[2]=3;
	gPuzzle->value[3]=8;
	gPuzzle->value[4]=0;
	gPuzzle->value[5]=4;
	gPuzzle->value[6]=7;
	gPuzzle->value[7]=6;
	gPuzzle->value[8]=5;

	iPuzzle->depth=0;
	iPuzzle->fromDirection=NONE;
	
	for (i=0; i<MAX_NODE; i++)
		iPuzzle->nextNode[i]=NULL;

	printf("\nSOURCE : ");
	for (i=0; i<MAX_VALUE; i++) {
		printf("[%d] ",iPuzzle->value[i]);
	}
	
	printf("\nTARGET : ");
	for (i=0; i<MAX_VALUE; i++) {
		printf("[%d] ",gPuzzle->value[i]);
	}

	// 프로그램 실행후 최초 자식 노드 생성하므로 TRUE로 세팅
	isFirst=TRUE;

	// 스택 초기화
	initStack();


	initialize(iPuzzle, gPuzzle);
	//DFS(pNode, gNode, i, currentDepth); // 0,1,2,3번째 자식 노드
	
	return 1;
}

void initialize(PUZZLE *pNode, PUZZLE *gNode)
{
	PUZZLE *node[MAX_NODE];
	static int currentDepth=0;
	int cursorPosition;
	
	int i,j;
	int makeChildNumber;
	
	printf("\n");
	
	// 출발 노드와 목표 노드를 비교함
	if (comparePuzzle(pNode, gNode) != FIND_NODE) {
		printf("COULD NOT FIND NODE\n");
	}
	
	currentDepth=currentDepth+1;
	
	// 현재 커서 위치를 찾고, 커서가 움직일 수 있는 방향을 알아냄
	cursorPosition=findDirection(pNode);
	tempPosition=cursorPosition;
	
	// 생성할 수 있는 자식 노드의 수를 구함
	makeChildNumber=getChildCount(cursorPosition);
	printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
	
	// 깊이 제한에 도달하지 않았고, 목표노드를 찾지 못했다면
	if (currentDepth <= MAX_DEPTH) {
		for (i=0; i<makeChildNumber; i++) {
			// 자식 노드를 생성
			node[i]=(PUZZLE*)malloc(sizeof(PUZZLE));
			
			// 자식 노드의 현재 깊이 설정
			node[i]->depth=currentDepth;
			
			// 부모 노드를 자식 노드와 연결
			pNode->nextNode[i]=node[i];
			
			// 자식 노드가 가리키고 있는 것은 NULL
			node[i]->nextNode[0]=NULL;
			node[i]->nextNode[1]=NULL;
			node[i]->nextNode[2]=NULL;
			node[i]->nextNode[3]=NULL;
			
			printf("\n부모[%d]->[%d]번째 자식의 주소[%d]", pNode, i, node[i]);
			
			// 생성된 자식 노드와 임시 노드에 부모 노드의 값을 저장
			for (j=0; j<MAX_VALUE; j++) {
				node[i]->value[j]=pNode->value[j];
			}
			swapNodeValue(node, i, cursorPosition);
		}
		
		printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		//printf("\n현재 깊이 : %d", currentDepth);
		
		for (i=0; i<makeChildNumber; i++) {
			printf("\n[*]부모[%d]->%d번째 자식[%d]노드값:", pNode, i, node[i]);
			for (j=0; j<MAX_VALUE; j++) {
				printf("[%d] ",node[i]->value[j]);
			}		
			printf("[*]부모[%d]->%d번째 자식[%d] 깊이 : %d\n", pNode, i, node[i], node[i]->depth);
			
			// DFS RECURSIVE
			DFS(node, gNode, i, currentDepth); // 0,1,2,3번째 자식 노드
		}
	}
}


int DFS(PUZZLE *pNode[], PUZZLE *gNode, int pCount, int pDepth)
{
	PUZZLE *childNode[MAX_NODE];
	
	int i,j;
	
	static int cursorPosition;
	int exCursorPosition;
	int makeChildNumber;
	
	callCount++;
	tempPosition=0;

	printf("--------------------------------------------------------------------\n");	
	printf("  HOW MANY TIMES CALL DFS FUNCTION : %d\n", callCount);
	printf("--------------------------------------------------------------------\n");
	//printf("자식 노드 깊이 : %d\n", pDepth);
		
	// 넘겨져 온 자식 노드와 목표 노드를 비교함
	for (i=pCount; i<=pCount; i++) {
		if (comparePuzzle(pNode[i], gNode) == FIND_NODE) {
			printf("[#%d NODE] FOUND!\n", i);
			return 1;
		}
	}
	
	// 부모 노드의 현재 커서 위치를 찾고, 커서가 움직일 수 있는 방향을 알아냄
	cursorPosition=findDirection(pNode[pCount]);
	tempPosition=cursorPosition;
	exCursorPosition=cursorPosition;

	// Exclusive OR 연산으로 이전 노드로부터 커서가 움직였던 방향으로 되돌아가는 것을 방지함
	exCursorPosition=cursorPosition^pNode[pCount]->fromDirection;
	printf("노드[%d]의 EXCLUSIVE 연산 후 커서 위치 : %d\n", pNode[pCount], exCursorPosition);

	// 현재 커서 위치에서 어느 방향으로 갈수 있는지 체크함
	showDirection(pNode[pCount], cursorPosition);

	printf("노드[%d]의 커서가 갈 수 없는 방향 : %d\n", pNode[pCount], pNode[pCount]->fromDirection);

	// 깊이를 증가시키고
	pDepth=pDepth++;
	
	// 생성할 수 있는 자식 노드의 수를 구함
	makeChildNumber=getChildCount(exCursorPosition);
	
	printf("노드[%d]의 생성가능 자식수 : %d\n", pNode[pCount], makeChildNumber);
	
	// 깊이 제한에 도달하지 않았으면 자식 노드 성
	if (pDepth <= MAX_DEPTH) {
		for (i=0; i<makeChildNumber; i++) {
			childNode[i]=(PUZZLE*)malloc(sizeof(PUZZLE));
			
			// 자식 노드의 현재 깊이 설정
			childNode[i]->depth=pDepth;
			
			// 부모 노드를 자식 노드와 연결
			pNode[pCount]->nextNode[i]=childNode[i];
			
			// 자식 노드가 가리키고 있는 것은 NULL로 지정
			childNode[i]->nextNode[0]=NULL;
			childNode[i]->nextNode[1]=NULL;
			childNode[i]->nextNode[2]=NULL;
			childNode[i]->nextNode[3]=NULL;
			
			printf("\n부모[%d]->[%d]번째 자식의 주소[%d]", pNode[pCount], i, childNode[i]);
			
			// 생성된 자식 노드에 부모 노드의 값을 저장
			for (j=0; j<MAX_VALUE; j++) {
				childNode[i]->value[j]=pNode[pCount]->value[j];
				//printf("[%d] ",childNode[i]->value[j]);
			}			
			
			// 노드안의 값을 이동하여 변경
			swapNodeValue(childNode, i, cursorPosition);
		}
		
		printf("\n--------------------------------------------------------------------\n");
		
		for (i=0; i<makeChildNumber; i++) {
			printf("부모[%d]->[%d]번째 자식[%d] 노드값:", pNode[pCount], i, childNode[i]);
			for (j=0; j<MAX_VALUE; j++) {
				printf("[%d] ",childNode[i]->value[j]);
			}		
			printf("부모[%d]->[%d]번째 자식[%d] 깊이: %d\n", pNode[pCount], i, childNode[i], childNode[i]->depth);
			
			// DFS RECURSIVE
			DFS(childNode, gNode, i, pDepth); // 0,1,2,3번째 자식 노드
		}
	}
	
	return 0;
}

// 이웃하는 퍼즐 데이타를 교환하기 위한 함수
int swapNodeValue(PUZZLE *childNode[], int count, int cursorPosition)
{
	PUZZLE *tempNode;
	int temp1;
	int temp2;
	int i;

	// 임시 노드 생성
	tempNode=(PUZZLE*)malloc(sizeof(PUZZLE));

	// 임시 노드에 값을 복사
	for (i=0; i<MAX_VALUE; i++) {
		tempNode->value[i]=childNode[count]->value[i];
	}
	
	// 커서 위치와 그 이웃에 위치한 값을 교체
	temp1 = tempNode->value[cursorPosition];
	
	if ((tempPosition&LEFT) == LEFT) {
		temp2 = tempNode->value[cursorPosition-1];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition-1]=temp1;
		childNode[count]->cursorPosition=cursorPosition&LEFT;
		childNode[count]->fromDirection=RIGHT;
		
		// 이미 실행한 구문은 Skip 하기 위함임
		tempPosition=tempPosition-LEFT;
		return 0;
	}
	else if ((tempPosition&UP) == UP) {
		temp2 = tempNode->value[cursorPosition-3];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition-3]=temp1;
		childNode[count]->cursorPosition=cursorPosition&UP;
		childNode[count]->fromDirection=DOWN;
		tempPosition=tempPosition-UP;
		return 0;
	}
	else if ((tempPosition&RIGHT) == RIGHT) {
		temp2 = tempNode->value[cursorPosition+1];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition+1]=temp1;
		childNode[count]->cursorPosition=cursorPosition&RIGHT;
		childNode[count]->fromDirection=LEFT;
		tempPosition=tempPosition-RIGHT;
		return 0;
	}
	else if ((tempPosition&DOWN) == DOWN) {
		temp2 = tempNode->value[cursorPosition+3];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition+3]=temp1;
		childNode[count]->cursorPosition=cursorPosition&DOWN;
		childNode[count]->fromDirection=UP;
		tempPosition=tempPosition-DOWN;
		return 0;
	}
	return 0;
}

// 생성할 수 있는 자식 노드의 수를 구하기 위한 함수
int getChildCount(int direction)
{
	int makeChildCount;

	// 생성 할 수 있는 자식 노드의 수를 구하기 위해 체크
	if (direction == 1 || direction == 2 || direction == 4 || direction == 8)
		makeChildCount=1;
	else if (direction == 3 || direction == 5 || direction == 6 || direction == 9 || direction == 10 || direction == 12)
		makeChildCount=2;
	else if (direction == 7 || direction == 11 || direction == 13 || direction == 14)
		makeChildCount=3;
	else if (direction == 15)
		makeChildCount=4;

	return makeChildCount;
}

// 현재 커서의 위치를 구함
int findDirection(PUZZLE *node)
{
	int direction;
	int i;

	for (i=0; i<MAX_VALUE; i++) {
		if (node->value[i] == 0) {
			direction=i;
			printf("노드[%d]의 커서 위치 : %d\n", node, direction);

			break;
		}
	}

	if ((i/3) == 0) {
		direction=DOWN;
	}
	else if ((i/3) == 1) {
		direction=UP | DOWN;
	}
	else if ((i/3) == 2) {
		direction=UP;
	}

	if ((i%3) == 0) {
		direction=direction | RIGHT;
	}
	else if ((i%3) == 1) {
		direction=direction | LEFT | RIGHT;
	}
	else if ((i%3) == 2) {
		direction=direction | LEFT;
	}
	
	return direction;
}

// 출발 노드와 목표 노드를 비교함
int	comparePuzzle(PUZZLE *pNode, PUZZLE *gNode)
{
	int i;
	
	for (i=0; i<MAX_VALUE; i++) {
		if (pNode->value[i] != gNode->value[i])
			return -1;
	}

	if (i == 9)
		return FIND_NODE;

	return 0;
}

// 커서가 움직일 수 있는 방향을 표시
void showDirection(PUZZLE *node, int direction)
{
	switch(direction) {
	case 1 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT\n", node);
				break;
	case 2 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : RIGHT\n", node);
				break;
	case 3 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | RIGHT\n", node);
				break;
	case 4 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : UP\n", node);
				break;
	case 5 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | UP\n", node);
				break;
	case 6 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : RIGHT | UP\n", node);
				break;
	case 7 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | RIGHT | UP\n", node);
				break;
	case 8 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : DOWN\n", node);
				break;
	case 9 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | DOWN\n", node);
				break;
	case 10 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : RIGHT | DOWN\n", node);
				break;
	case 11 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | RIGHT | DOWN\n", node);
				break;
	case 12 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : UP | DOWN\n", node);
				break;
	case 13 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | UP | DOWN\n", node);
				break;
	case 14 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : RIGHT | UP | DOWN\n", node);
				break;
	case 15 : 
			printf("노드[%d]의 커서 위치로부터 움직일수 있는 방향 : LEFT | RIGHT | UP | DOWN\n", node);
				break;
	}
}

void printCurrentNode()
{
	int i;

	printf("\n");

	for(i=0;i<9;i++){
		printf("%d\t", stack[current_stack-1].value[i]);
	}
}

void push(PUZZLE *t)
{
	if (current_stack >= MAX_STACK -1) {
		printf("\nStack Overflow!\n");
		exit(1);
	}
	else 
		stack[current_stack] = *t;
	
	current_stack++;
}

PUZZLE pop(void)
{
	PUZZLE ptr;
	if (current_stack < 0) {
		printf("\nStack Underflow\n");
		exit(1);
	}
	else {
		ptr=stack[current_stack];
		current_stack--;
	}

	return ptr;
}

void initStack(void)
{
	current_stack=-1;
}

int isEmptyStack(void)
{
	return (current_stack == -1);
}