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

显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事：
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;
     
    
   

    

     

    
    

     

      }  
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/15340761