#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define NONE			0x000
#define LEFT			0x001
#define RIGHT			0x002
#define UP				0x004
#define DOWN			0x008

#define MAX_VALUE		9
#define MAX_DEPTH		5			// 최대 허용 깊이
#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 direction;				// 커서의 현재 위치
	int fromDirection;				// 커서가 어디로부터 왔는가
	struct _node *nextNode[4];		// 자식 노드 최대 4개
} PUZZLE;

PUZZLE stack[MAX_STACK];
int current_stack;

int callCount;
int gCursorPosition;

int DFS(PUZZLE *pNode[], int *gNode, int pCount, int pDepth);
int swapNodeValue(PUZZLE *childNode[], int i, int cursorPosition, int *direction);
void printNodeValue(PUZZLE *childNode[], int count);
int getChildCount(int direction);
int	comparePuzzle(PUZZLE *pNode, int *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(void)
{
	int iDimension[9]={2,8,3,1,6,4,7,0,5};
	int gDimension[9]={1,2,3,8,0,4,7,6,5};

	PUZZLE *iPuzzle[MAX_NODE];

	int i;
	int j;

	// 스택 초기화
	initStack();

	for (i=0; i<MAX_NODE; i++) {
		iPuzzle[i]=(PUZZLE*)malloc(sizeof(PUZZLE));
	
		iPuzzle[i]->depth=0;
		iPuzzle[i]->fromDirection=NONE;
		iPuzzle[i]->nextNode[i]=NULL;

		/*for (j=0; j<MAX_VALUE; j++) 
			iPuzzle[i]->value[j]=iDimension[j];*/
	}

	memcpy(iPuzzle[0]->value, iDimension, 9*sizeof(int));
	//memcpy(gPuzzle.value, gDimension, 9*sizeof(int));

	printf("\nSOURCE : ");
	for (j=0; j<MAX_VALUE; j++) {
		printf("[%d] ",iPuzzle[0]->value[j]);
	}
	
	printf("\nTARGET : ");
	for (j=0; j<MAX_VALUE; j++) {
		printf("[%d] ",gDimension[j]);
	}

	printf("\n");

	DFS(iPuzzle, gDimension, 0, 0); // 0,1,2,3번째 자식 노드

	return 1;
}

int DFS(PUZZLE *pNode[], int *gNode, int pCount, int pDepth)
{
	PUZZLE *childNode[MAX_NODE];
	
	int i,j;
	
	static int direction;
	int cursorPosition;
	int exDirection;
	int makeChildNumber;
	
	// 깊이 제한에 도달하지 않았으면 자식 노드 생성
	if (pDepth != MAX_DEPTH) {
		
		printf("--------------------------------------------------------------------\n");	
		printf("  HOW MANY TIMES CALL DFS FUNCTION : %d\n", ++callCount);
		printf("--------------------------------------------------------------------\n");
		//printf("자식 노드 깊이 : %d\n", pDepth);
		
		// 부모 노드의 현재 커서 위치를 찾고, 커서가 움직일 수 있는 방향을 알아냄
		direction=findDirection(pNode[pCount]);
		cursorPosition=gCursorPosition;
		
		// Exclusive OR 연산으로 이전 노드로부터 커서가 움직였던 방향으로 되돌아가는 것을 방지함
		exDirection=direction^pNode[pCount]->fromDirection;
		printf("노드[%d]의 EXCLUSIVE 연산 후 DIRECTION : %d\n", pNode[pCount], exDirection);
		
		// 현재 커서 위치에서 어느 방향으로 갈수 있는지 체크함
		showDirection(pNode[pCount], exDirection);
		
		printf("노드[%d]의 커서가 갈 수 없는 방향 : %d\n", pNode[pCount], pNode[pCount]->fromDirection);
		
		// 깊이를 증가시키고
		pDepth=pDepth++;
		
		// 생성할 수 있는 자식 노드의 수를 구함
		makeChildNumber=getChildCount(exDirection);
		
		printf("노드[%d]의 생성 자식수 : %d\n", pNode[pCount], makeChildNumber);
		
		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;
			
			// 생성된 자식 노드에 부모 노드의 값을 저장
			for (j=0; j<MAX_VALUE; j++) {
				childNode[i]->value[j]=pNode[pCount]->value[j];
				//printf("[%d] ",childNode[i]->value[j]);
			}			
			
			printf("\n부모[%d]->[%d]번째 자식의 주소:[%d]\n", pNode[pCount], i, childNode[i]);
			printf("부모[%d]->[%d]번째 자식의 깊이:%d\n", pNode[pCount], i, childNode[i]->depth);

			// 노드안의 값을 이동하여 변경
			swapNodeValue(childNode, i, cursorPosition, &exDirection);

			// 넘겨져 온 자식 노드와 목표 노드를 비교함
			if (comparePuzzle(childNode[i], gNode) == FIND_NODE) {
				printf("\n:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::\n");
				printf("::::::::::::::::::::::::::::: 목표 노드 찾음 ::::::::::::::::::::::::::::\n");
				printf(":::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::\n\n");
				exit(0);				
			}
		}
		
		for (i=0; i<makeChildNumber; i++) {
			// RECURSIVE
			DFS(childNode, gNode, i, pDepth); // 0,1,2,3번째 자식 노드
		}
	}
	
	return 0;
}

// 이웃하는 퍼즐 데이타를 교환하기 위한 함수
int swapNodeValue(PUZZLE *childNode[], int count, int cursorPosition, int *direction)
{
	PUZZLE tempNode;
	int temp1;
	int temp2;
	int i;

	printf("\n==:======:==\n");
	printf("\n스왑 전 : ");

	// 임시 노드에 값을 복사
	for (i=0; i<MAX_VALUE; i++) {
		tempNode.value[i]=childNode[count]->value[i];
		if ((i%3) == 0)
			printf("\n");
		printf("[%d] ", childNode[count]->value[i]);
	}

	// 커서 위치와 그 이웃에 위치한 값을 교체
	temp1 = tempNode.value[cursorPosition];
	
	if ((*direction&LEFT) == LEFT) {
		temp2 = tempNode.value[cursorPosition-1];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition-1]=temp1;
		childNode[count]->direction=*direction&LEFT;
		childNode[count]->fromDirection=RIGHT;
		
		// 이미 실행한 구문은 Skip 하기 위함임
		*direction=*direction-LEFT;

		//printf("\nDirection:::LEFT:::\t count:%d\t cursorPosition:%d", count, cursorPosition);

		// 스왑 후 노드값 출력
		printNodeValue(childNode, count);

		return 0;
	}
	else if ((*direction&UP) == UP) {
		temp2 = tempNode.value[cursorPosition-3];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition-3]=temp1;
		childNode[count]->direction=*direction&UP;
		childNode[count]->fromDirection=DOWN;

		*direction=*direction-UP;

		//printf("\nDirection:::UP:::\t count:%d\t cursorPosition:%d", count, cursorPosition);
		// 스왑 후 노드값 출력
		printNodeValue(childNode, count);

		return 0;
	}
	else if ((*direction&RIGHT) == RIGHT) {
		temp2 = tempNode.value[cursorPosition+1];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition+1]=temp1;
		childNode[count]->direction=*direction&RIGHT;
		childNode[count]->fromDirection=LEFT;
		*direction=*direction-RIGHT;

		//printf("\nDirection:::RIGHT:::\t count:%d\t cursorPosition:%d", count, cursorPosition);
		// 스왑 후 노드값 출력
		printNodeValue(childNode, count);

		return 0;
	}
	else if ((*direction&DOWN) == DOWN) {
		temp2 = tempNode.value[cursorPosition+3];
		childNode[count]->value[cursorPosition]=temp2;
		childNode[count]->value[cursorPosition+3]=temp1;
		childNode[count]->direction=*direction&DOWN;
		childNode[count]->fromDirection=UP;
		*direction=*direction-DOWN;

		//printf("\nDirection:::DOWN:::\t count:%d\t cursorPosition:%d", count, cursorPosition);
		// 스왑 후 노드값 출력
		printNodeValue(childNode, count);

		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) {
			gCursorPosition=direction=i;

			// 0 [BLANK]이 위치한 곳을 찾아 전역 변수에 저장
			printf("노드[%d]의 커서 위치 [0 1 2 | 3 4 5 | 6 7 8] : %d\n", node, gCursorPosition);

			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, int *gNode)
{
	int i;
	
	for (i=0; i<MAX_VALUE; i++) {
		if (pNode->value[i] != gNode[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 printNodeValue(PUZZLE *childNode[], int count)
{
	int i;
	
	printf("\n\n스왑 후 : ");
	
	// 임시 노드에 값을 복사
	for (i=0; i<MAX_VALUE; i++) {
		if ((i%3) == 0)
			printf("\n");
		printf("[%d] ",childNode[count]->value[i]);
	}
	printf("\n");

}
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);
}