main.c

本程序采用 blind breadth search解eight puzzles问题, 且消除了重复的布局。

/* 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" );
	}
}