求帮忙看看马踏棋盘算法哪里错了。

gascd

代码和小甲鱼的对照了，除了nextxy()函数以外，其他的函数都差不多。然而我的nextxy()函数就算不出解来，而小甲鱼的nextxy()函数就能够算出来。
如下为代码:

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

#define X 8
#define Y 8

int chess[X][Y];

#if 0
//小甲鱼的正确的代码
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;
}
#endif

#if 1
//我的错误代码
// 判断下一步能不能走
int nextxy(int *x, int *y, int count)
{
        switch(count)
        {
        case 0:if((*x)-1>=0 && (*y)+2<=Y-1 && chess[*x-1][*y+2]==0)
                   {
                           *x = (*x)-1;
                           *y = (*y)+2;
                           return 1;
                   } break;
        case 1: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 2: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 3:if((*x)+2<=X-1 && (*y)-1>=0 && chess[*x+2][*y-1]==0)
                        {
                                *x = (*x)+2;
                                *y = (*y)-1;
                                return 1;
                   } break;
        case 4:if((*x)+1<=X-1 && (*y)-2>=0 && chess[*x+1][*y-2]==0)
                   {   
                           *x = (*x)+1;
                           *y = (*y)-2;
                           return 1;
                   } break;
        case 5:if((*x)-1>=0 && (*y)-2>=0 && chess[*x-1][*y-2]==0)
                   {   
                           *x = (*x)-1;
                           *y = (*y)-2;
                           return 1;
                   } break;
        case 6:if((*x)-2>=0 && (*y)-1>=0 && chess[*x-2][*y-1]==0)
                   {   
                           *x = (*x)-2;
                           *y = (*y)-1;
                           return 1;
                   } break;
        case 7:if((*x)-2>=0 && (*y)+1<=Y-1 && chess[*x-2][*y+1]==0)
                        {   
                                *x = (*x)-2;
                                *y = (*y)+1;
                                return 1;
                   } break;
        default:break;
        }
        return 0;
}
#endif


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");
        }
}

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

        //判断是否走完
        if(X*Y == tag)
        {
                print();
                return 1;
        }
        //判断下一步能不能走,能flag = 1
        flag = nextxy(&x1, &y1, count);
        while(0 == flag && count < 8)
        {
                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 < 8)
                {
                        count++;
                        flag = nextxy(&x1, &y1, count);
                }
        }
        //这条路不通,还原标志
        if(0 == flag)
                chess[x1][y1] = 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("\nsorry,马踏棋盘失败!\n");
        finish = clock();
        printf("\n本次计算时间为%lf秒\n",(double)(finish-start)/CLOCKS_PER_SEC);
        
        system("pause");
        return 0;
}

gascd

不是哪里错了，而是我的nextxy()函数里,case的顺序不同，导致了算法的时间大大大大大大的增加。大约需要一个多月算出来！！！！！！！！
咳咳，其实只要换个简单的点，就可以了，或者改一下case顺序。
总之，错的人不是我，错的是……这个时间太长了。

Code_mzh

gascd 发表于 2017-1-28 21:54
不是哪里错了，而是我的nextxy()函数里,case的顺序不同，导致了算法的时间大大大大大大的增加。大约需要一 ...

我的也是，不知道为啥nextxy顺序不对就会出错呢，这是什么原理，求大神解答

gascd

Code_mzh 发表于 2018-2-18 22:50
我的也是，不知道为啥nextxy顺序不对就会出错呢，这是什么原理，求大神解答

这个我搞懂了。因为nextxy顺序不对，所以马儿还在一步一步的试着跳。直到把正确的路径给找出来。这个过程需要很长的时间。