关于鱼c马踏棋盘的算法

951923615

  #include <stdio.h>
#include <time.h>

#define X 8
#define Y 8

int chess[X][Y];

// 找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count)
{
        switch(count)
        {
                case 0:
                        if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
                        {
                                *x = *x + 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 1:
                        if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
                        {
                                *x = *x + 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 2:
                        if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
                        {
                                *x = *x + 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 3:
                        if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
                        {
                                *x = *x + 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                case 4:
                        if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
                        {
                                *x = *x - 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 5:
                        if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
                        {
                                *x = *x - 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 6:
                        if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
                        {
                                *x = *x - 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 7:
                        if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
                        {
                                *x = *x - 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                default:
                        break;
        }

        return 0;
}

void print()
{
        int i, j;

        for( i=0; i < X; i++ )
        {
                for( j=0; j < Y; j++ )
                {
                        printf("%2d\t", chess[i][j]);
                }
                printf("\n");
        }
        printf("\n");
}

// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量，每走一步，tag+1
int TravelChessBoard(int x, int y, int tag)
{
        int x1=x, y1=y, flag=0, count=0;
       
        chess[x][y] = tag;

        // 如果tag==X*Y，则完成整个棋盘的遍历
        if( tag == X*Y )
        {
                print();
                return 1;
        }

        flag = nextxy(&x1, &y1, count);
        while( 0==flag && count < 7 )
        {
                count++;
                flag = nextxy(&x1, &y1, count);
        }

        while( flag )
        {
                if( TravelChessBoard(x1, y1, tag+1) )
                {
                        return 1;
                }

                x1 = x;
                y1 = y;
                count++;

                flag = nextxy(&x1, &y1, count);
                while( 0==flag && count < 7 )
                {
                        count++;
                        flag = nextxy(&x1, &y1, count);
                }
        }

        if( 0 == flag )
        {
                chess[x][y] = 0;
        }

        return 0;
}

int main()
{
        int i, j;
        clock_t start, finish;

        start = clock();

        for( i=0; i < X; i++ )
        {
                for( j=0; j < Y; j++ )
                {
                        chess[i][j] = 0;
                }
        }

        if( !TravelChessBoard(2, 0, 1) )
        {
                printf("抱歉，马踏棋盘失败鸟~\n");
        }

        finish = clock();
        printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);

        return 0;
}
其中while( flag )
        {
                if( TravelChessBoard(x1, y1, tag+1) )
                {
                        return 1;
                }

                x1 = x;
                y1 = y;
                count++;
其中x1 = x，y1 = y各代表什么量，如果将
x1 = x ，y1 = y注释掉，依然可以运行，结果却不一样，为何

～风介～

高材生在此！@阴影中的曙光 @醉酒青牛

ELI_

谢谢分享

psychopath

好好学习学习

DAY

关于马踏棋盘算法的一些感悟与大家分享一下：
首先明确思路：从一个坐标出发，从下一步八中走法选择一种，走到底，当此路不通时，才回到上一步，走其他方法。
简单点说就是，路通一直走下去，路不通回溯上一步。。understanding！！！！！
还有说一下上面楼主代码的一点小错误，，，变量count<7,这点我不是很认同，我觉得应该改为count<=7吧！！
说到这里我附上代码（代码中X，Y定义为5，方便计算机计算，当然如果你的计算机配置不错，，可以把X ，Y的值定义为8 ）

1. #include<cstdio>
   
2. #include<ctime>
   
3. 
   
4. #define X 5
   
5. #define Y 5
   
6. int chess[X][Y]={0};
   
7. 
   
8. void printChess(){
   
9.         printf("This is horse Chess:\n");
   
10.         for(int i=0;i<X;i++){
    
11.                 for(int j=0;j<Y;j++){
    
12.                         printf("%2d ",chess[i][j]);
    
13.                 }
    
14.                 printf("\n");
    
15.         }
    
16. }
    
17. 
    
18. int next(int *x,int *y,int step){
    
19.     switch(step)
    
20.     {
    
21.         case 0:
    
22.             if(*y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2]==0)
    
23.             {
    
24.                 *y+=2;
    
25.                 *x-=1;
    
26.                 return 1;
    
27.             }
    
28.             break;
    
29.         case 1:
    
30.             if(*y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0)
    
31.             {
    
32.                 *y+=2;
    
33.                 *x+=1;
    
34.                 return 1;
    
35.             }
    
36.             break;
    
37.         case 2:
    
38.             if(*y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0)
    
39.             {
    
40.                 *y+=1;
    
41.                 *x+=2;
    
42.                 return 1;
    
43.             }
    
44.             break;
    
45.         case 3:
    
46.             if(*y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0)
    
47.             {
    
48.                 *y-=1;
    
49.                 *x+=2;
    
50.                 return 1;
    
51.             }
    
52.             break;
    
53.         case 4:
    
54.             if(*y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0)
    
55.             {
    
56.                 *y-=2;
    
57.                 *x+=1;
    
58.                 return 1;
    
59.             }
    
60.             break;
    
61.         case 5:
    
62.             if(*y-2>=0 && *x-1>=0 && chess[*x-1][*y-2]==0)
    
63.             {
    
64.                 *y-=2;
    
65.                 *x-=1;
    
66.                 return 1;
    
67.             }
    
68.             break;
    
69.         case 6:
    
70.             if(*y-1>=0 && *x-2>=0 && chess[*x-2][*y-1]==0)
    
71.             {
    
72.                 *y-=1;
    
73.                 *x-=2;
    
74.                 return 1;
    
75.             }
    
76.             break;
    
77.         case 7:
    
78.             if(*y+1<=Y-1 && *x-2>=0 && chess[*x-2][*y+1]==0)
    
79.             {
    
80.                 *y+=1;
    
81.                 *x-=2;
    
82.                 return 1;
    
83.             }
    
84.             break;
    
85.         default:
    
86.             break;
    
87.     }
    
88.     return 0;
    
89. }
    
90. 
    
91. int horse(int x,int y,int tag){
    
92.         int x_t=x,y_t=y;
    
93.         int flag=0,count=0;
    
94.         chess[x][y]=tag;
    
95.         if(tag==X*Y){
    
96.                 printChess();
    
97.                 return 1;
    
98.         }
    
99.         flag=next(&x_t,&y_t,count);
    
100.         while(!flag && count<=7){
     
101.                 count++;
     
102.                 flag=next(&x_t,&y_t,count);
     
103.         }
     
104.         while(flag){
     
105.                 if(horse(x_t,y_t,tag+1))
     
106.                         return 1;
     
107.                 x_t=x,y_t=y,count++;
     
108.                 flag=next(&x_t,&y_t,count);
     
109.                 while(!flag && count<=7){
     
110.                         count++;
     
111.                         flag=next(&x_t,&y_t,count);
     
112.                 }
     
113.         }
     
114.         if(!flag)chess[x][y]=0;
     
115.         return 0;
     
116.        
     
117. }
     
118. 
     
119. int main()
     
120. {
     
121.         clock_t begin,end;
     
122.         begin=clock();
     
123.         if(!horse(2,0,1)){
     
124.                 printf("The horse Chess is unavailable!");
     
125.         }
     
126.         end=clock();
     
127.         printf("This time used is %lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
     
128.         return 0;
     
129. }
     

复制代码

特别说明：因为代码没有加注释，在明白思路的前提下看才会更省力哦。。

li83126

多谢分享

0洛枫0

学习

L丶

学习学习

流月飞星

0洛枫0

学习

谦虚求学

     int x1=x, y1=y, flag=0, count=0;  这个你看懂了 ，你就知道 x1  和 y1 表示什么意思了

啊dong1992

学习下~~

天然萌

为什么程序设置横向 纵向都为7后，程序运行很久没有结果？不下15分钟，电脑i5处理器，不应该不出结果呀？设置5个，解出来速度很快，这是怎么回事呢？视频上讲的不就50多秒吗？ 难道我电脑问题？

gascd

天然萌 发表于 2017-1-13 01:31
为什么程序设置横向 纵向都为7后，程序运行很久没有结果？不下15分钟，电脑i5处理器，不应该不出结果呀？设 ...

有可能需要几天解出来。或者是一个月。

常德水鱼村

支持楼主！

whdd

whdd

whdd

whdd

whdd