每日一算法:骑士遍历问题

素颜马尾好姑娘i 2022-09-18 06:58 167阅读 0赞

**说明**骑士旅游（Knight tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完\[所有的位置？

**解法**骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C. Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步。」，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。

显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事：  
1.当前步的行列位置  
2.当前步已经试探过哪些方向了，以便回溯回来时能够选择一个新的方向进行试探

对于骑士游历问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，  
当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。  
也就是说在当前位置优先选一个走起来比"艰难"的方向来推进。加入这种启发式规则之后，从运行的效果看，在求解的过程中几乎不回溯。

#include <stdio.h> 
    
    int travel(int x, int y);
    int board[8][8] = {0}; 
    
    int main(void) 
    {
    	int startx, starty;
    	int i, j;
    	printf("输入起始点：");
    	scanf("%d %d", &startx, &starty);
    	if(travel(startx, starty)) 
    	{
    		printf("游历完成！\n");
    		for(i = 0; i < 8; i++) 
    		{
    			for(j = 0; j < 8; j++)
    			{
    				printf("%2d ", board[i][j]);
    			}
    			printf("\n");
    		}
    	}
    	else 
    	{
    		printf("游历失败！\n");
    	}
    
    	return 0;
    } 
    
    
    
    int travel(int x, int y) 
    {
    	// 对应骑士可走的八个方向 ,按顺时针方向查找
    	int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};//左右方向
    	int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};//上下方向
    	// 测试下一步的出路
    	int nexti[8] = {0};//左右方向
    	int nextj[8] = {0};//上下方向
    	// 记录出路的个数，最少的个数即为我们所求
    	int exists[8] = {0};
    	int i, j, k, m, l;
    	int tmpi, tmpj;
    	int count, min, tmp;
    	i = x;
    	j = y;
    	board[i][j] = 1;//设置入口处为1
    	for(m = 2; m <= 64; m++) 
    	{//2...64
    		for(l = 0; l < 8; l++)
    		{//出路的个数初始为0
    			exists[l] = 0;
    		}
    		l = 0;
    		// 试探八个方向
    		for(k = 0; k < 8; k++)
    		{
    			tmpi = i + ktmove1[k];
    			tmpj = j + ktmove2[k];
    			// 如果是边界了，不可走
    			if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)
    			{
    				continue;
    			}
    			// 如果这个方向可走，记录下来
    			if(board[tmpi][tmpj] == 0)
    			{//记录方向
    				nexti[l] = tmpi;
    				nextj[l] = tmpj;
    				// 可走的方向加一个
    				l++;
    			}
    		}
    		count = l;
    		// 如果可走的方向为0个，返回
    		if(count == 0)
    		{
    			return 0;
    		}
    		else if(count == 1) 
    		{
    			// 只有一个可走的方向
    			// 所以直接是最少出路的方向
    			min = 0;
    		}
    		else
    		{
    			// 找出下一个位置的出路数
    			for(l = 0; l < count; l++)
    			{
    				for(k = 0; k < 8; k++) 
    				{
    					tmpi = nexti[l] + ktmove1[k];
    					tmpj = nextj[l] + ktmove2[k];
    					if(tmpi < 0 || tmpj < 0 || 
    						tmpi > 7 || tmpj > 7) 
    					{
    						continue;
    					}
    					if(board[tmpi][tmpj] == 0)
    					{//记录下一个位置的出路数
    						exists[l]++;
    					}
    				}
    			}
    			tmp = exists[0];
    			min = 0;
    			// 从可走的方向中寻找最少出路的方向
    			for(l = 1; l < count; l++) 
    			{
    				if(exists[l] < tmp) 
    				{
    					tmp = exists[l];
    					min = l;
    				}
    			}
    		}
    		// 走最少出路的方向
    		i = nexti[min];
    		j = nextj[min];
    		board[i][j] = m;
    	}
    	return 1;
    }