马 行 天 下

//这是一个欧拉提出的问题：国际象棋的棋盘上一个马，能否走64步正好走遍64个棋盘格子。

//我用最土的办法来搜索，这是一个典型的“深度优先搜索”（Depth-First-Search)，我全部由数组来做，一个2维数组存走过的轨迹，一个数组存可

//以走的步数，再一个数组存每一层的最后一个选择，实际就是当前最底层的父亲。

//这是在McGill听Prfessor NewBurn 的课的唯一的收获，这位老教授是Game软件的专家，据说主持过IBM的“深蓝”与国际特级大师“卡斯帕罗夫”的

//对抗赛，可惜他的课程艰深，作业难做，我听课时，（当然是非法的。）加上我才7个学生，他对学生态度很好，总是说他担心学生会觉得作业太难会

//杀他。哈哈。。。也许阿。真怀念那个月的生活，一天听6门课，从8：30到4：30，每节课只有十分钟换教室，中午没吃饭，我几乎晕过去，下午困的要死，

//上一节课睡半截。不过一想到这是不要钱的，顿时觉得大赚特赚。

//这个小东东，我搞了快两天才完，还不知道对不对，哎，真失败！

//改进就是要能出结果，因为这样搜索是没有结果的因为，8^64是一个天文数字（当然，并不是每一步都有8个选择，有些出界，有些以前走过，但是可以

//看出这个问题的复杂性。）我粗略测试，估计电脑运行几万年也不会有结果，也不知道对不对。各位有兴趣不妨帮我检验一下，做做测试，很简单的，

只要下载解压缩并运行看看多长时间能有结果，在写信告诉我。

改进就是对产生的子节点排序，排序的原则是基于类似“权”值得概念，比如某一个点的权值是由能走到他的点的个数决定的，个数越多权值得优先级越低，

于是，我先将棋盘上所有点的“权”值存起来，当产生子树时候，先搜索优先级高的子树。

不过，好像还是有问题，搜索了两个结果后，（一个2百多万子节点，第二个约3千多万节点）第三个始终不出来。

#include <iostream>
#include <cstdlib>
#include <ctime>


using namespace std;

//ÕâÊÇÂíÒƶ¯µÄ×ø±ê¡£
struct Pos
{
	int x;
	int y;
}pos;

//ÕâÊÇÆðʼλ×Ó¡£
struct Pos startPos;
//ÆåÅ̵ĴóС
const boardSize =6;   //using even 7 will cost days running.


//Âí¿ÉÒÔ×ßµÄ8¸ö²½×Ó¡£
enum Move
{
	upright, upleft, downleft, downright, leftup, leftdown, rightup, rightdown
};
//¼Í¼×ߵIJ½Êý¡£
int Tour[8 * boardSize * boardSize]= {0};

//ÕâÊÇËÑË÷µÄ²ãÊý£¬Ò²¾ÍÊÇÿһ²½µÄÖ¸±ê£¬ÒòΪÿһ²½¶¼¿ÉÄÜÓÐ8¸öÑ¡Ôñ¡£ÕâÀïÖ¸Ïò×îºóÒ»¸öλÖá£
int Level[boardSize*boardSize]={0};

//ÊÇ·ñÓн⣨ȫ¾Ö±äÁ¿²»ºÃ£©
bool solution = false;

//reading way of priority
int getPriority(int x, int y);

//from direction to priority
int direction2Priority(int direction);

//×ܵļÆÊýÆ÷¡£
int Counter = 0;

//temp storage for possible move and sorting before save to Tour[];
int tempMove[8] = {0};


//storage for prioty for each square in chessboard
int priority[boardSize][boardSize] = {0};


//²ãÊýµÄ¼ÆÊýÆ÷¡£
int Step = 0;

//save possible move to tempMove[] with big to small priority
//void saveTempMove(int &x, int &y, int moveNum);

//assignment prioty for each square.
void generatePriority();

//ÕâÊÇÆåÅÌ£¬ÓÃÀ´¼Ç¼Æå×ÓÊÇ·ñ×ß¹ýijһ¸öλ×Ó£¬0ΪûÓУ¬1Ϊ×ß¹ý¡£
int board[boardSize][boardSize] = {0};

//²úÉúÿһ²ãµÄ²½Êý¡£Èç²»ÄܲúÉú·µ»Ø¼Ù¡£
bool Generate();
//ÆÀ¹ÀÊÇ·ñÕÒµ½½á¹û¡£
bool Evaluate();
//²»ÄܲúÉú£¬¾ÍÍË»ØÒ»²½£¬ÖØвúÉú¡£
void Restore();

//¿´ÊÇ·ñÊÇÍ˻ص½ÉÏÒ»²ãÁË¡£
bool stepPoint();
//ÄÚ²¿·½·¨£¬²úÉúijÖÖ×ß·¨µÄ×ø±êÖµ¡£
void getMove(int direction, int &x, int &y);
//°´ÕÕ²ÎÊýµÄ×ß·¨£¬Òƶ¯ÂíµÄ×ø±êλÖá£
void stepMove(int direction);
//ÏÔʾÕýÈ·µÄ²½×Ó
void displayMove();

//to see if the direction is possible move
bool testMove(int direction);//test new move if within bound and unoccupied


//³õʼ»¯¡£
void Initialize(int, int);


int main()
{
	int startTime=0;
	long tick =0;
	generatePriority();
	for (int i =0; i< boardSize; i++)
	{
		for (int j=0; j< boardSize; j++)
		{
			tick =0;
			Initialize(i, j);
			startTime = time(0);
			while (!Evaluate())
			{		
				if (!Generate())     //²»ÄܲúÉú¾ÍÍË»ØÉÏÒ»²½¡£
				{	
					Restore();  //ÍË»ØÉÏÒ»²½¡£
					if (Counter <= 0)   //¼ìÑéÊÇ·ñÍ˻ص½Æðµã£¬±íÃ÷ÊÇ·ñÎ޽⡣
					{
						cout<<"no solution for pos.x="<<startPos.x
							<<" and pos.y="<<startPos.y<<"    total time is:"
							<<time(0) - startTime<<" tick is "<<tick<<" times"<<endl;
						break;
					}
				
				}
				tick++;
		//		displayMove();
			}
			cout<<"  pos.x="<<startPos.x
							<<" and pos.y="<<startPos.y<<"    total time is:"
							<<time(0) - startTime<<" tick is "<<tick<<" times"<<endl;
			if (solution)
				displayMove();
			else
				cout<<"no solution!"<<endl;
			
		}
	}
	
	return 0;
}

void displayMove()
{
	cout<<"  A solution is as following:"<<endl;
//	cout<<"  Starting from pos.x = "<<startPos.x<<" and pos.y = "<<startPos.y<<endl;
	cout<<"  Total moves are "<<Counter<<endl;

	for (int i =0; i <= Step; i++)
	{
		
		cout<<"   Tour["<<Level[i]<<"]  "<<Tour[Level[i]]<<endl;//Êä³ö½á¹û¡£
	}
}

int getPriority(int x, int y)
{
	return priority[x][y];
}

/*
//x, y must return the smallest move pos which is the last one in array(big-->small)
void saveTempMove(int &x, int &y, int moveNum)
{
	int temp =0;
	for (int i=0; i< moveNum; i++)
	{
		if  (getPriority(x, y) < priority[i])//???????????
		{
			temp = priority[i];
			priority[i] = 
			while (i <= moveNum)
			{
				priority[
			insertPriority(x, y);
			;
		}
	}
}
*/


void generatePriority()
{
	int moves;
	for (int i =0; i< boardSize; i++)
	{
		for (int j=0; j< boardSize; j++)
		{
			moves =0;
			for (int direction =0; direction < 8; direction++)
			{
				if (testMove(direction))
				{
					moves++;
				}
			}
			priority[i][j] = moves;
		}
	}
}

int direction2Priority(int direction)
{
	int x, y;
	getMove(direction, x, y);
	return getPriority(x, y);
}





void Initialize(int x, int y)
{

	startPos.x = x;
	startPos.y = y;
	for (int i=0; i< boardSize; i++)
	{
		for (int j=0; j < boardSize; j++)
		{
			board[i][j] =0;
		}
	}
	board[x][y] = 1;
	pos.x = x;
	pos.y = y;
	Step = 0;
	Counter = 0;
	Level[Step] = Counter;
	Tour[Counter] = -1;   //ûÒâ˼µÄ¡£
	solution = false;
}

void addStep()     //Òƶ¯µ½Ð²㡣
{
	Step++;
	Level[Step] = Counter;
}

bool Evaluate()
{
	if (Counter < 0)
	{
		cout<<"no";
		solution =false;
		return true;
	}
	return (solution =(Step == boardSize * boardSize - 1));
}

bool Generate()
{
	int findPriority(int tempPriority, int start);
	void insertPriority(int curPos, int direction);
	void addStep();
	int curPos=0, tempPriority;
	
	bool result = false;
	int row, col;
	int temp = Counter + 1;
	for (int direction =0; direction < 8; direction ++)  
	{
		if (testMove(direction))   //²âÊÔ8¸ö·½Ïò¡£
		{
			result = true;
			Counter ++;
			tempPriority = direction2Priority(direction);
			curPos = findPriority(tempPriority, temp);
			insertPriority(curPos, direction);			
		}
	}
	if (result)    //Òƶ¯µ½×îºóÒ»¸ö×ß·¨¡£
	{	
//		copyMoves();
		getMove(Tour[Counter], row, col);
		pos.x = row;
		pos.y = col;
		board[row][col] = 1;   //this is the point to move to.
		addStep();
	}
	return result;
}


int findPriority(int tempPriority, int start)
{
	for (int i=start; i < Counter; i++)
	{
		if (tempPriority >direction2Priority(Tour[i]))
			break;
	}
	return i;
}

void insertPriority(int curPos, int direction)
{
	int hold=0, temp =0;
	hold = Tour[curPos];
	Tour[curPos] = direction;
	for (int i = curPos + 1; i <= Counter + 1; i++)
	{
		temp = Tour[i];
		Tour[i]= hold;
		hold = temp;
	}
}


	


bool stepPoint()
{
	return (Counter == Level[Step - 1]);   //²âÊÔÊÇ·ñÍ˻ص½ÉÏÒ»²ã¡£
}

void Restore()
{
	void counterMove(int lastMove);
	void moveStep();

	board[pos.x][pos.y] = 0;  //make unoccupied erase track
	counterMove(Tour[Counter]);  //restore to parent pos

	Counter --; 
	if (Counter <= 0)
		return;
	
	//back
	if (stepPoint())   //if it is parent
	{
		Step--;       //use the upper level step
		Restore();  //keep going
	}
	else
		moveStep();  //simply make current node the step point
}


void moveStep()
{
	Level[Step] = Counter;
	stepMove(Tour[Counter]);
	board[pos.x][pos.y] = 1;   //Òƶ¯µ½ÐµľÍÒª±íʾÒѾ­Õ¼ÓÃÁË¡£
}


void getMove(int direction, int &x, int &y)
{
	switch (direction)
	{
	case upleft:
		x = pos.x - 1;
		y = pos.y - 2;
		break;
	case upright:
		x = pos.x + 1;
		y = pos.y - 2;
		break;
	case downleft:
		x = pos.x - 1;
		y = pos.y + 2;
		break;
	case downright:
		x = pos.x + 1;
		y = pos.y + 2;
		break;
	case leftup:
		x = pos.x - 2;
		y = pos.y - 1;
		break;
	case leftdown:
		x = pos.x - 2;
		y = pos.y + 1;
		break;
	case rightup:
		x = pos.x + 2;
		y = pos.y - 1;
		break;
	case rightdown:
		x = pos.x + 2;
		y = pos.y + 1;
		break;
	}
}

bool testMove(int direction)
{
	int x, y;
	getMove(direction, x, y);
	if ((x < boardSize)&&(x >= 0)&&(y < boardSize)&&(y >= 0))   //ÊÇ·ñ³ö½ç
	{
		if (board[x][y]== 0)   //prevent x, y out of bound of board[][] if they are minus. so don't put logic op above.
		{		
			return true;
		}
	}
	return false;
}
	
void stepMove(int direction)
{
	int x, y;
	getMove(direction, x, y);
	pos.x = x;
	pos.y = y;
}

void counterMove(int lastMove)
{
	int newMove;
	switch(lastMove)
	{
	case upleft:
		newMove = downright;
		break;
	case upright:
		newMove = downleft;
		break;
	case downleft:
		newMove = upright;
		break;
	case downright:
		newMove = upleft;
		break;
	case leftup:
		newMove = rightdown;
		break;
	case leftdown:
		newMove = rightup;
		break;
	case rightup:
		newMove = leftdown;
		break;
	case rightdown:
		newMove = leftup;
		break;
	}
	stepMove(newMove);
}