问题陈述：

　　骑士游历(Knight tour)在十八世纪初备受数学家与拼图迷的注意，究竟它是什么时候被提出已不可考。骑士的走法为国际象棋的走法，类似中国象棋的马，骑士可以由任意一个位置出发，他如何走完所有的位置？

 

问题解法：

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

 

代码详解：

1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5   6 int pos[8][8] = {
   0};  7   8 int travel(int, int);  9  10 int main() 11 { 12     int i, j, startX, startY; 13     printf("Please input a starting point: "); 14     scanf("%d%d", &startX, &startY); 15     if(travel(startX, startY)) { 16         printf("Travel finished\n"); 17     }else { 18         printf("Travel failed\n"); 19     } 20     for(i=0; i<8; i++) { 21         for(j=0; j<8; j++) { 22             printf("%2d ", pos[i][j]); 23         } 24         printf("\n"); 25     } 26     return 0; 27 } 28  29 int travel(int x, int y) { 30     int i, j, k, l, m; 31     int tmpX, tmpY; 32     int count, min, tmp; 33  34     //骑士可走的八个方向(顺时针) 35     int ktmoveX[8] = {
   1, 2, 2, 1, -1, -2, -2, -1}; 36     int ktmoveY[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 37  38     //下一步坐标 39     int nextX[8] = {
   0}; 40     int nextY[8] = {
   0}; 41  42     //记录每个方向的出路的个数 43     int exists[8] = {
   0}; 44  45     //起始用1标记位置 46     i = x; 47     j = y; 48     pos[i][j] = 1; 49  50     //遍历棋盘 51     for(m=2; m<=64; m++) { 52         //初始化八个方向出口个数 53         for(l=0; l<8; l++) { 54             exists[l] = 0; 55         } 56         l = 0; //计算可走方向 57  58         //试探八个方向 59         for(k=0; k<8; k++) { 60             tmpX = i + ktmoveX[k]; 61             tmpY = j + ktmoveY[k]; 62             //边界 跳过 63             if(tmpX<0 || tmpY<0 || tmpX>7 || tmpY>7) { 64                 continue; 65             } 66             //可走 记录 67             if(pos[tmpX][tmpY] == 0) { 68                 nextX[l] = tmpX; 69                 nextY[l] = tmpY; 70                 l++;    //可走方向加1 71             } 72         } 73         count = l; 74         //无路可走 返回 75         if(count == 0) { 76             return 0; 77         //一个方向可走 标记 78         }else if(count == 1) { 79             min = 0; 80         //找出下个位置出路个数 81         }else { 82             for(l=0; l
       
        7 || tmpY>7) { 87                         continue; 88                     } 89                     if(pos[tmpX][tmpY] == 0) { 90                         exists[l]++; 91                     } 92                 } 93             } 94             //找出下个位置出路最少的方向 95             min = 0; 96             tmp = exists[0]; 97             for(l=0; l
       
      
     

 

测试效果图：

测试数据：startX = 2, startY = 2

 

转载请注明出处：