/* EightPuzzles problem
   本程序采用 blind breadth search, 不允許出現重復的布局，否則會很容易出現memory overflow.
   
   chenyong 2008.11.16
   
   借鑒了 http://blog.csdn.net/tiaotiaoyly/archive/2008/01/01/2008233.aspx 中的結論：
   將一個布局表示成一維的形式，求出除0之外的所有數字的逆序數之和。(所謂逆序數即為線性代數
   中概念，指排列中每個數前面比它大的數的個數之和)
   結論：若兩個布局的逆序奇偶性相同，則相互可達。
         若兩個布局的逆序奇偶性不同，則相互不可達。

   例如：
   布局A: 8 3 5 的相應逆序數為 0 1 1 
          1 2 7                3 3 1
          4 6 0                3 2    總數為14,即為偶序數。

   布局B: 1 2 3 的相應逆序數為 0 0 0 
          4 5 7                0 0 0
          7 8 0                0 0    總數為0,即為偶序數。

   布局C: 8 3 5 的相應逆序數為 0 1 1 
          1 2 6                3 3 1
          4 7 0                3 1    總數為13,即為奇序數。
   按照以上結論，有布局A與布局B相互可達到，而布局C與布局A相互不可達,布局C與布局B相互不可達。

   編程過程中發現的問題：
   <1> 我試圖聲明靜態變量：struct queueNode pQueueHead[maxQueueSize]，當maxQueueSize <= 6000時，
       可以運行通過，但是當maxQueueSize > 6000，程序就立即提示錯誤。只好用將它聲明為動態指針
       struct queueNode * pQueueHead = NULL; 問題得到解決。

   待改進之處：
   <1> 在查找重復布局時可以利用查找樹算法，以加快求解速度。
   <2> 將step以順序方式print.
*/

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define tablesize 3
#define maxQueueSize 362280

typedef struct queueNode
{
	int parentHeapNum;
	char slider_x;
	char slider_y;
	char state[tablesize][tablesize];
};

int dr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  //移動方向：右，下，左，上

void main()
{
	int i, j, k;
	int slider_x, slider_y;
	int iSucceed = 0;         //匹配成功標志。0:未成功，1：成功
	char tmp_layout[tablesize * tablesize];

	int iTotalSteps = 0;
	int iRepetition = 0;
	int iRepeated = 0;

	int iReversal_startLayout = 0;
	int iReversal_endLayout = 0;

	int iQueueHead = 0;
	int iQueueSize = 0;
	struct queueNode * pQueueHead = NULL;
	struct queueNode * pQueueNode = NULL;
	struct queueNode * p = NULL;
	struct queueNode * q = NULL;

	char start_layout[tablesize][tablesize] = {8,3,5,1,2,7,4,6,0};  //棋盤起始狀態。
	//char end_layout[tablesize][tablesize]   = {1,2,3,4,5,6,7,8,0};  //棋盤目標狀態。
    char end_layout[tablesize][tablesize]   = {4,3,2,1,0,5,6,7,8};  //棋盤目標狀態。

	if (0 == memcmp(start_layout, end_layout, tablesize * tablesize))
	{
		iSucceed = 1;
	}
	if (iSucceed)
		printf("Find Answer. step = %d\n", iTotalSteps);

	//計算start_layout的逆序。
	memcpy(tmp_layout, start_layout, tablesize * tablesize);
	for (i = 1; i < tablesize * tablesize; i++)
	{
		if (0 != tmp_layout[i])
		{
			for (j = 0; j < i; j++)
				if (tmp_layout[j] > tmp_layout[i])
					iReversal_startLayout++;
		}
	}

	//計算end_layout的逆序。
	memcpy(tmp_layout, end_layout, tablesize * tablesize);
	for (i = 1; i < tablesize * tablesize; i++)
	{
		if (0 != tmp_layout[i])
		{
			for (j = 0; j < i; j++)
				if (tmp_layout[j] > tmp_layout[i])
					iReversal_endLayout++;
		}
	}

	if ( ((0 == iReversal_startLayout % 2) && (1 == iReversal_endLayout % 2)) ||
		 ((1 == iReversal_startLayout % 2) && (0 == iReversal_endLayout % 2)) )
	{
		printf("布局的奇偶性不同，No Answer. \n");
		exit(1);
	}
	
	pQueueHead = (struct queueNode *)malloc(maxQueueSize * sizeof(struct queueNode));	
	printf("*** debug: memory = %d ***\n", maxQueueSize * sizeof(struct queueNode));
	printf("the execution may take several minutes, please be patience..... :-)\n");

	//put the first node into queue.
    pQueueNode = pQueueHead + iQueueSize;
	pQueueNode->parentHeapNum = -1;
	memcpy(pQueueNode->state, start_layout, tablesize * tablesize);
	for (i = 0; i < tablesize; i++)
		for (j = 0; j < tablesize; j++)
		{
			if (0 == pQueueNode->state[i][j])
			{
				pQueueNode->slider_x = i;
                pQueueNode->slider_y = j;
			}
		}
    iQueueSize++;

	while ((!iSucceed) && (iQueueHead < iQueueSize))   //若未找到目標節點且queue非空，循環
	{
		pQueueNode = pQueueHead + iQueueHead;
		for (k = 0; k < 4; k++)
		{
			slider_x = pQueueNode->slider_x + dr[k][0];
			slider_y = pQueueNode->slider_y + dr[k][1];
			if ( (slider_x >= 0) && (slider_x < tablesize) && 
				 (slider_y >= 0) && (slider_y < tablesize) )
			{   //valid position.
				//try to put a new node into queue.
				if (iQueueSize <= maxQueueSize - 1)
				{
					q = pQueueHead + iQueueSize;
					memcpy(q, pQueueNode, sizeof(struct queueNode));
					q->parentHeapNum = iQueueHead;
					q->state[q->slider_x][q->slider_y] = q->state[slider_x][slider_y];
                    q->state[slider_x][slider_y] = 0;
					
					q->slider_x = slider_x;
					q->slider_y = slider_y;

					//if it equal to an existing node, then do nothing.
					iRepeated = 0;
					for (i = 0; i < iQueueHead; i++)
					{
						p = pQueueHead + i;
						if (0 == memcmp(q->state, p->state, tablesize * tablesize))
						{
							iRepeated = 1;
							iRepetition++;
							break;
						}
					}
					if (!iRepeated)
						iQueueSize++;
				}
				else
				{
					printf("queue overflow, please retry after adjust length of queue.\n");
					for (k = 0; k < 20; k++)
					{
						q = pQueueHead + k;
						printf("[id = %d]: parent = %d, ", k, q->parentHeapNum);
						printf("[%d, %d] ", q->slider_x, q->slider_y);
						for (i = 0; i < tablesize; i++)
							for (j = 0; j < tablesize; j++)
							{
								 printf("%d,", q->state[i][j]);
							}
						printf("\n");
					}
					if (pQueueHead != NULL)
					{
						free(pQueueHead);
					    pQueueHead = NULL;
						printf("*** debug: memory released. ***\n" );
					}
					exit(1);
				}

				//check if the newnode is what we pursue.
				if (0 == memcmp(q->state, end_layout, tablesize * tablesize))
				{
					iSucceed = 1;
					break;
				}
			}
		}

		iQueueHead++;
	}

	if (!iSucceed)
		printf("\n No Answer.\n");
	else
	{
		printf("\n find Answer. 共使用節點:%d, repeated nodes:%d\n", iQueueSize, iRepetition);
		pQueueNode = pQueueHead + iQueueSize - 1;
		while (-1 != pQueueNode->parentHeapNum )
		{
			iTotalSteps++;
			printf("<%d>:\n", iTotalSteps);
			for (i = 0; i < tablesize; i++)
			{
				for (j = 0; j < tablesize; j++)
				{
					printf("%d ", pQueueNode->state[i][j]);
				}
				printf("\n");
			}
			printf("\n");

			pQueueNode = pQueueHead + pQueueNode->parentHeapNum;
		}
        				
		printf("initial state:\n");		
		for (i = 0; i < tablesize; i++)
		{
			for (j = 0; j < tablesize; j++)
			{
				printf("%d ", pQueueNode->state[i][j]);
			}
			printf("\n");
		}
		printf("\n");

		printf("totol steps = %d\n", iTotalSteps);
	}
    
	if (pQueueHead != NULL)
	{
		free(pQueueHead);
		pQueueHead = NULL;
		printf("*** debug: memory released. ***\n" );
	}
}