马踏棋盘算法的实现

DFS(int x, int y, int tag)
{
    // 将该格子赋值为当前的步数
    chess[x][y] = tag;

    // 保留原来数据x y 将x1 y1代入递归
    int x1=x;
    int y1=y;

    // 结束条件
    if (tag == 棋盘格子数){
        return ture;
    }

    // 找到一个下一步可走的位置
    // 直接修改x1 y1的值
    flag = nextxy(x1,y1,count);
    while(flag == 0 && count<7){
        flag = nextxy(x1,y1,++count);
    }
    while(flag){
        // 步数+1 一直递归下去 直到结束条件
        if (DFS(x1,y1,tag+1)){
            // 然后不断地返回true 最后退出
            return true;
        }

        // 以上是理想情况
        // 如果上述不成功 则寻找本步的另外可走的下一步
        // 注意!! 这里的x1 y1要重新赋值为x y 因为由于上述的递归 x1 y1值已经改变
        x1 = x;
        y1 = y;
        count ++;
        flag = nextxy(x1,y1,count);
        while(flag == 0 && count<7){
            flag = nextxy(x1,y1,++count);
        }
    }
    // 如果下步无路可走 则遍历失败
    if (flag ==0){
        // 失败则说明当前步数不成立 即最初的chess[x][y]=tag不成立 需要归零
        chess[x][y] = 0;
        return flase;
    }
}

  1 #include <stdio.h>
  2 #include <time.h>
  3 
  4 #define X 6
  5 #define Y 6
  6 
  7 int chess[X][Y];
  8 
  9 // 找到(x,y)位置的下一个可走位置
 10 int nextxy(int *x, int *y ,int count)
 11 {
 12     switch(count)
 13     {
 14     case 0:
 15         if (*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0){
 16             *x += 2;
 17             *y -= 1;
 18             return 1;
 19         }
 20         break;
 21     case 1:
 22         if (*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0){
 23             *x += 2;
 24             *y += 1;
 25             return 1;
 26         }
 27         break;
 28     case 2:
 29         if (*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){
 30             *x -= 2;
 31             *y += 1;
 32             return 1;
 33         }
 34         break;
 35     case 3:
 36         if (*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0){
 37             *x -= 2;
 38             *y -= 1;
 39             return 1;
 40         }
 41         break;
 42     case 4:
 43         if (*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0){
 44             *x += 1;
 45             *y -= 2;
 46             return 1;
 47         }
 48         break;
 49     case 5:
 50         if (*x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0){
 51             *x += 1;
 52             *y += 2;
 53             return 1;
 54         }
 55         break;
 56     case 6:
 57         if (*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0){
 58             *x -= 1;
 59             *y += 2;
 60             return 1;
 61         }
 62         break;
 63     case 7:
 64         if (*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0){
 65             *x -= 1;
 66             *y -= 2;
 67             return 1;
 68         }
 69         break;
 70     default:
 71         break;
 72     }
 73     return 0;
 74 }
 75 
 76 // 深度优先遍历棋盘 (x,y)为位置坐标 tag是标记，每走一步tag+1
 77 int TraverChessBoard(int x, int y, int tag)
 78 {
 79     int i,j;
 80     int x1=x,y1=y,flag=0,count=0;
 81     chess[x][y] = tag;
 82 
 83     if (tag == X*Y){
 84         // 打印棋盘
 85         for (i=0; i<X; i++){
 86             for (j=0; j<Y; j++){
 87                 printf("%2d\t",chess[i][j]);
 88             }
 89             printf("\n");
 90         }
 91         printf("\n");
 92         return 1;
 93     }
 94 
 95     // 找到下一个可走位置(x1,y1)
 96     flag = nextxy(&x1,&y1,count);
 97     while(flag == 0 && count<7 ){
 98         count ++;
 99         flag = nextxy(&x1,&y1,count);
100     }
101 
102     while(flag){
103         if (TraverChessBoard(x1,y1,tag+1)){
104             return 1;
105         }
106 
107         // 找到下一个可走位置(x1,y1)
108         x1 = x;
109         y1 = y;
110         count++;
111         flag = nextxy(&x1,&y1,count);
112         while(flag == 0 && count<7){
113             count++;
114             flag = nextxy(&x1,&y1,count);
115         }
116     }
117 
118     if (flag == 0){
119         chess[x][y] = 0;
120     }
121     return 0;
122 }
123 
124 int main()
125 {
126     clock_t start,finish;
127     start = clock();
128     if (!TraverChessBoard(2,0,1)){
129         printf("马踏棋盘遍历失败!\n");
130     }
131     finish = clock();
132     printf("\n本次计算耗时%f秒\n",((double)finish-(double)start)/CLOCKS_PER_SEC);
133     return 0;
134 }