回溯法求解骑士巡游问题

采用回溯法，当有解时输出解，程序结束否则no solution

# include 
# include 
# include 

using namespace std;

typedef struct
{
    long x;
    long y;
}Step;

static long tx[]={-2-1 1 2 2 1-1-2 };		//8个方向
static long ty[]={ 1 2 2 1-1-2-2-1 };
 long CurStep = 1;							//当前步

int size;
int TotalStep;
int ** Board;
Step *step;
  
void Init（ ）											//初始化变量
{
	cout<<“Please input size of your chessboard :“;
	cin>>size;

	//size=8;
	TotalStep = size*size;
	step = new Step[TotalStep+1];

	size++;
	//cout<
	Board = new int*[size];
	for（int i = 0;i < size;++i）
		Board[i] = new int[size];
	for（int i = 0;i < size;++i）
		for（int j = 0;j < size; ++j）
			Board[i][j]=0;

	int sxsy;
	cout<<“input start position（x）:“;
	cin>>sx;
	cout<<“input start position（y）:“;
	cin>>sy;

	step[CurStep].x = sx;
	step[CurStep].y = sy;													//骑士初始位置

    Board[step[CurStep].x][step[CurStep].y] = CurStep;						//骑士初始位置

}

void Output（ ）																//输出结果 
{
    long dx dy;
    dx = step[CurStep].x - step[1].x;										//判断最后是否回到起点
    dy = step[CurStep].y - step[1].y;
    if（dx * dx + dy * dy == 5）  
    {  
       cout<<“Hamilton !!“<    }

	ofstream fout（“output.txt“）;
	if（!fout）
	{
		cerr<<“File cannot open!“<	}

	if（CurStep == TotalStep）
	{
		for（int i = 1;i<= TotalStep;++i）
		{
			fout<<“< “<“;
			if（i != TotalStep）
			{
				fout<<“ → “;
			}
			if（i % 5 == 0）
			{
				fout<			}
		}//end file-for

		for（int i = 1; i < size; i++）  
		{  
			for（int j = 1; j < size; j++）  
			{  
			   cout<			}  
			printf（“\n“）;
		}//end Screen print-for
	}
	else
	{
		cout<<“No Solution“<		fout<<“No Solution“;
	}


	fout.clear（）;
	fout.close（）;

	for（int i=0;i < size;++i）												//释放动态空间
		delete [] Board[i];
	delete [] Board;
	delete [] step;
}  
void knightTour（ ）  
{  
    long nextx nexty;
    int i;
    for（i = 0; i < 8; ++i） //8个方向上尝试，  
    {  
        nextx = step[CurStep].x + tx[i];
        nexty = step[CurStep].y + ty[i];

        if（ nextx > 0 && nextx < size && nexty > 0 && nexty < size && Board[nextx][nexty] == 0）			//如果位置未出棋盘且为空
        {
            ++CurStep;
            Board[nextx][nexty] = CurStep;									//骑士移动到下一步
            
			step[CurStep].x = nextx;
            step[CurStep].y = nexty;										//记录走过的步

			knightTour（）;													//做下一次尝试
			if（ CurStep == TotalStep）										//如果步数达到最大步数（棋盘全满），返回
			{
				return;
			}
        }
    }
	if（i == 8 && CurStep != TotalStep）
	{
		Board[step[CurStep].x][step[CurStep].y] = 0;							//如果8个方向都不满足，取消本次移动
		--CurStep;																//并且倒退1步
	}
}

int main（ ）
{
    Init（）;  

    knightTour（）;															//开始遍历

	Output（）;
	system（“pause“）;
    return 0;  
} 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      41984  2011-04-21 02:19  Knight\Debug\Knight.exe

     文件     412656  2011-04-21 02:19  Knight\Debug\Knight.ilk

     文件     617472  2011-04-21 02:19  Knight\Debug\Knight.pdb

     文件       6702  2011-04-21 02:19  Knight\Knight\Debug\BuildLog.htm

     文件        663  2011-04-20 17:46  Knight\Knight\Debug\Knight.exe.embed.manifest

     文件        728  2011-04-20 17:46  Knight\Knight\Debug\Knight.exe.embed.manifest.res

     文件        621  2011-04-21 02:19  Knight\Knight\Debug\Knight.exe.intermediate.manifest

     文件      51590  2011-04-21 02:19  Knight\Knight\Debug\Knight.obj

     文件         67  2011-04-21 02:19  Knight\Knight\Debug\mt.dep

     文件     175104  2011-04-21 02:19  Knight\Knight\Debug\vc90.idb

     文件     225280  2011-04-21 02:19  Knight\Knight\Debug\vc90.pdb

     文件       3014  2011-04-21 02:19  Knight\Knight\Knight.cpp

     文件       3934  2011-04-20 17:46  Knight\Knight\Knight.vcproj

     文件       1409  2011-04-21 02:20  Knight\Knight\Knight.vcproj.Lee-PC.Lee.user

     文件        852  2011-04-21 02:19  Knight\Knight\output.txt

     文件    2247680  2011-04-21 02:20  Knight\Knight.ncb

     文件        884  2011-04-20 17:34  Knight\Knight.sln

    ..A..H.      9216  2011-04-21 02:20  Knight\Knight.suo

     目录          0  2011-04-21 02:19  Knight\Knight\Debug

     目录          0  2011-04-21 02:19  Knight\Debug

     目录          0  2011-04-21 02:19  Knight\Knight

     目录          0  2011-04-20 23:21  Knight

----------- ---------  ---------- -----  ----

              3799856                    22