马的Hamilton周游路线问题

关于这道题，很多博客中都有相应的解法，我也看了很多篇，但是我发现，大多数都没有做到回到起点这个要求，所以我写一写自己的解法，如有错误欢迎指出。

问题描述：

8*8的国际象棋棋盘上的一只马（日字走法），恰好走过除起点外的其他63个位置各一次，最后回到起点，这条路线称为马的一条Hamilton周游路线。对于给定的m*n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|≤2，试设计一个分治算法找出马的一条Hamilton周游路线。

 

问题分析：

起初，一直在思考怎么用分治法解决这个问题，后来越想越不对劲，分治算法的其中一个要求是分解的每个子问题相互独立。在这道题中，马的日字型走法贯穿每个格子，也就是说将棋盘分解成若干个小的棋盘然后求解是不可能的，因为日字型的走法使得每个小的棋盘不可能成为独立的问题。所以这道题分治法是算不出的（个人看法，错误勿喷，如果有大神求大神告知一下分治法怎么解决，感激不尽）。所以最后用了递归解决了。首先要明确两个条件一定要满足：

1、不能越界，及应该有一个函数判断马是否跑出棋盘。

2、不能重走。及马不能重复所走过的路线。

这两点无论用什么方法解决这道题都是必须遵守的。

其次判断是否能够回到原点：

这里因为马是从坐标（0,0）开始，所以，根据马的走法问题，即判断最后的一步坐标是否是（2,1）或（1,2）即可。比起其他博客中用for循环判断，可以省下不少时间。如下图，在（0,0）坐标下，能到达的只有（2,1）和（1,2）坐标，同理，只有（1,2），（2,1）坐标才能到达（0,0），所以，只有最后一步坐标落在这两点上才可能是最终解，否则则不是。

在得出这个结论后，再判断当前所走的步数是否为最后一步，则可得到递归的终止条件。

其次，再补充递归内容即可解决问题：

及保证上文所写的1,2点，即可移动棋子。至此，问题解决。

源代码：

#include<iostream>
#include<string.h>
using namespace std;

int a[101][101];
int movex[8]={1,2,2,1,-1,-2,-2,-1};
int movey[8]={-2,-1,1,2,2,1,-1,-2};
int count=0;


int judge(int x,int y,int m,int n)//判断是否越界，即走出棋盘 
{
	if(x>=m||x<0||y>=n||y<0)
	    return 1;
	return 0;
}

int end(int x,int y)
{
    if((x==1&&y==2)||(x==2&&y==1))
	    return 1;
	return 0;
}

int gone(int x,int y)//判断是否已经走过 
{
	if(a[x][y]!=0)
	{
		return 1;
	}
	return 0;
}

void print(int m,int n)
{
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
}


void move(int x,int y,int k,int m,int n)
{
	if(k==n*m+1&&end(x,y))//结束条件
	{
		//输出矩阵 
		cout<<"第"<<++count<<"种解"<<endl;
		print(m,n);
		cout<<endl;
	}
	else
	{
		for(int i=0;i<8;i++)
		{
			if((!judge(x+movex[i],y+movey[i],m,n))&&(!gone(x+movex[i],y+movey[i])))
			{
				a[x+movex[i]][y+movey[i]]=k;
				move(x+movex[i],y+movey[i],k+1,m,n);
				a[x+movex[i]][y+movey[i]]=0;
			}
		}
		
	 } 
}

int main()
{	
	int m,n;
	memset(a,0,sizeof(int)*101*101);
	cout<<"请输入棋盘的行数（大于5的偶数）:";
	cin>>m;
	cout<<"请输入棋盘的列数（大于5的偶数）:";
	cin>>n;
	a[0][0]=1;
	move(0,0,2,m,n);
	return 0;	
 } 

在这里，我只测试了6*6的小矩阵，因为太大可能跑不出来...

小小的6*6矩阵跑了40分钟后...最终结果有19724种：