马踏棋盘

问题描述：

所谓“马踏棋盘”问题，就是指在中国象棋的棋盘上，用马的走法走遍整个棋盘，在8*8的方格中，每个格都要遍历，且只能遍历一次。

我们把棋盘抽象成一个二维数据，输入起始位置的坐标(x,y),根据马的“日”字走法，将马走的步数写入二维数组，然后输出。下面是一种走法：



解决方法：

我们从图中可以看到，一个位置的马可以有八个不同方向的下一步。如何表示下一步呢？

设当前马的坐标为(x,y)，则下一步为(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)八个方向。

我们设两个全局数组fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2}，则上面的八个方向的点可以表示为:(x+fx[i],y+fy[i])，i为0~7。


我们先设一个数组a[8][8]来存放马的遍历路径。

首先输入一个起始坐标，然后从起始点开始进行深度优先搜索。从第1步找第2步的坐标，然后从第2步找第3步，再从第3步找第4步……。直到找到第64步也就完成任务了。

当然，每一个马都有八个下一步的选择，我们在满足要求的点中任意找一个进行遍历，当八个点都不满足要求时，就回溯的上一步，找其他点进行遍历。

下一步需要满足的条件：点(x,y)要在棋盘上，即0<x,y<8，同时a[x][y]要未遍历过。


下面是我的全部代码，仅供参考：

[cpp] view plain?
  1. #include<stdio.h>  
  2.   
  3. int fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2},a[8][8];  
  4.   
  5. //Output()函数进行输出遍历结果  
  6. void Output()  
  7. {  
  8.     int i,j;  
  9.     for(i = 0;i < 8;i++,printf(" "))  
  10.         for(j = 0;j < 8;j++)  
  11.             printf("%3d",a[i][j]);  
  12. }  
  13.   
  14. /*Check()函数检查xx、yy代表的点是否满足条件，满足则返回1. 
  15.  *条件：在8*8的棋盘边界内，且该点未遍历。 
  16.  */  
  17. int check(int xx,int yy)  
  18. {  
  19.     if(xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && a[xx][yy] == 0)  
  20.         return 1;  
  21.     return 0;  
  22. }  
  23.   
  24. /*x、y表示起点的横坐标和纵坐标，dep为递归的深度，代表当前马是第几个马。 
  25.  *Find()函数搜索起点的下一个结点，然后以下一个结点为起点，进行递归搜索。 
  26.  *当深度达到64时表示遍历完成，进行输出。 
  27.  */  
  28. int Find(int x,int y,int dep)  
  29. {  
  30.     int i,xx,yy;  
  31.     for(i = 0;i < 8;i++)  
  32.     {  
  33.         xx = x + fx[i];  
  34.         yy = y + fy[i];  
  35.         if(check(xx,yy) == 1)   //检查点a[xx][yy]是否满足条件  
  36.         {  
  37.             a[xx][yy] = dep;  
  38.             if(dep == 64)  
  39.             {  
  40.                 Output();  
  41.                 return 1;  
  42.             }  
  43.             if(Find(xx,yy,dep+1) == 1)  //如果返回的是1，表示遍历完成。  
  44.                 return 1;  
  45.             else                        //如果返回的不是1，表示遍历未完成，继续搜索。  
  46.                 a[xx][yy] = 0;  
  47.         }  
  48.     }  
  49.     return 0;  
  50. }  
  51.   
  52. void main()  
  53. {  
  54.     /*x和y代表马的坐标。dep为递归的深度，代表当前马是第几个马*/  
  55.     int i,j,x,y;  
  56.     int dep = 1;  
  57.     /*数组a[8][8]代表棋盘，遍历之前先初始化*/  
  58.     for(i = 0;i < 8;i++)  
  59.         for(j = 0;j < 8;j++)  
  60.             a[i][j] = 0;  
  61.     printf("请输入x，y: ");  
  62.     scanf("%d,%d",&x,&y);  
  63.     a[x-1][y-1] = 1;  
  64.     if(Find(x-1,y-1,2) == 1)    //寻找路径，找到了则返回1，否则返回0。  
  65.         printf("Success! ");  
  66.     else  
  67.         printf("Failed! ");  
  68. }  



以上思路相对比较简单，有点类似迷宫问题，只需进行深度优先搜索和回溯就能解决。但是运行的效率很低，而且还只输出了一条路径。如果需要输出几千或者几万条路径的话，必须进行优化才行。

原文链接：http://blog.csdn.net/bone_ace/article/details/39452179

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lux-ace/p/5230998.html