关于鱼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 ）

#include<cstdio>
#include<ctime>

#define X 5
#define Y 5
int chess[X][Y]={0};

void printChess(){
        printf("This is horse Chess:\n");
        for(int i=0;i<X;i++){
                for(int j=0;j<Y;j++){
                        printf("%2d ",chess[i][j]);
                }
                printf("\n");
        }
}

int next(int *x,int *y,int step){
    switch(step)
    {
        case 0:
            if(*y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2]==0)
            {
                *y+=2;
                *x-=1;
                return 1;
            }
            break;
        case 1:
            if(*y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0)
            {
                *y+=2;
                *x+=1;
                return 1;
            }
            break;
        case 2:
            if(*y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0)
            {
                *y+=1;
                *x+=2;
                return 1;
            }
            break;
        case 3:
            if(*y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0)
            {
                *y-=1;
                *x+=2;
                return 1;
            }
            break;
        case 4:
            if(*y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0)
            {
                *y-=2;
                *x+=1;
                return 1;
            }
            break;
        case 5:
            if(*y-2>=0 && *x-1>=0 && chess[*x-1][*y-2]==0)
            {
                *y-=2;
                *x-=1;
                return 1;
            }
            break;
        case 6:
            if(*y-1>=0 && *x-2>=0 && chess[*x-2][*y-1]==0)
            {
                *y-=1;
                *x-=2;
                return 1;
            }
            break;
        case 7:
            if(*y+1<=Y-1 && *x-2>=0 && chess[*x-2][*y+1]==0)
            {
                *y+=1;
                *x-=2;
                return 1;
            }
            break;
        default:
            break;
    }
    return 0;
}

int horse(int x,int y,int tag){
        int x_t=x,y_t=y;
        int flag=0,count=0;
        chess[x][y]=tag;
        if(tag==X*Y){
                printChess();
                return 1;
        }
        flag=next(&x_t,&y_t,count);
        while(!flag && count<=7){
                count++;
                flag=next(&x_t,&y_t,count);
        }
        while(flag){
                if(horse(x_t,y_t,tag+1))
                        return 1;
                x_t=x,y_t=y,count++;
                flag=next(&x_t,&y_t,count);
                while(!flag && count<=7){
                        count++;
                        flag=next(&x_t,&y_t,count);
                }
        }
        if(!flag)chess[x][y]=0;
        return 0;
        
}

int main()
{
        clock_t begin,end;
        begin=clock();
        if(!horse(2,0,1)){
                printf("The horse Chess is unavailable!");
        }
        end=clock();
        printf("This time used is %lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
        return 0;
}

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

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