鍍金池/ 問答/C  C++/ 自己寫的馬踏棋盤算法,怎么是死循環(huán),一直沒找到原因。。

自己寫的馬踏棋盤算法,怎么是死循環(huán),一直沒找到原因。。

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

#define MAX_VERTEX_NUM 10
#define X 8
#define Y 8    
int chess[X][Y];

int nextxy(int *x, int *y, int count) {
    switch (count)
    {
    case 0:
        if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
        {
            *x += 1;
            *y -= 2;
            return 1;
        }
        break;
    case 1:
        if (*x + 2 <= X - 1 && *y - 1 >=0 && chess[*x + 2][*y - 1] == 0)
        {
            *x += 2;
            *y -= 1;
            return 1;
        }
        break;
    case 2:
        if (*x + 2 <= X - 1 && *y + 1 <= Y - 1 && chess[*x + 2][*y + 1] == 0)
        {
            *x += 2;
            *y += 1;
            return 1;
        }
        break;
    case 3:
        if (*x + 1 <= X - 1 && *y + 2 <= Y-1 && chess[*x + 1][*y + 2] == 0)
        {
            *x += 1;
            *y += 2;
            return 1;
        }
        break;
    case 4:
        if (*x - 1 >= 0 && *y + 2 <= Y-1 && chess[*x -1][*y+2] == 0)
        {
            *x -= 1;
            *y += 2;
            return 1;
        }
        break;
    case 5:
        if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0)
        {
            *x -= 2;
            *y += 1;
            return 1;
        }
        break;
    case 6:
        if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
        {
            *x -= 2;
            *y -= 1;
            return 1;
        }
        break;
    case 7:
        if (*x - 1 >= 0 && *y - 2 >=0 && chess[*x - 1][*y - 2] == 0)
        {
            *x -= 1;
            *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");
}

int TraveChessBoard(int x, int y, int tag) {
    chess[x][y] = tag;
    int x1 = x, y1 = y, flag = 0, count = 0;

    if (tag == X*Y)
    {
        print();
        return 1;
    }
    flag = nextxy(&x1, &y1, count);

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

    //find ma next(x1,y1),find ok flag=1;
    while (flag)
    {
        if (TraveChessBoard(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);
        }


    //xia yi bu zuo biao
    }

    if (flag == 0)
    {
        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 (!TraveChessBoard(2, 0, 1))
    {
        printf("bao qian,shi bai le");
    }
    finish = clock();
    printf("\nben ci ji suan shi jian:%fmiao\n\n", (double)((finish - start) / CLOCKS_PER_SEC));



    return 0;


    


}

這是代碼,感覺沒問題,但是運行在88,在起始點為2,0點一直是死循環(huán),不知道為什么,有時候棋盤小點,起始點選好又可以得出正確答案,有時候又得不出,有時候又是死循環(huán),不知道為什么,理論在88的棋盤,2,0起始點肯定有解的啊,調(diào)試了半天,算法感覺也沒寫錯,不知道怎么回事。。。。費解?。?/p>

回答
編輯回答
巫婆

你的棋盤遍歷算法有問題呀!你遞歸寫錯了吧

int TraveChessBoard(int x,int y,int count)  
{  
    int x1=x,y1=y; //新節(jié)點位置  
    if(count>X*Y) //已全部遍歷且可用,則返回。  
        return 1;  
    int flag,result,i;  
    for(i=0;i<8;i++)  
    {  
        flag=next(&x1,&y1,i); //尋找下一個可用位置  
        if(1==flag)  
        {  
            chess[x1][y1]=count; //新找到的結(jié)點標識可用,  
            result=traverse(x1,y1,count+1); //以新節(jié)點為根據(jù),再次遞歸下一個可用結(jié)點  
            if(result) //當前棋盤已全部可用  
            {  
                return 1;  
            }  
            else //新找到的結(jié)點無下一個可用位置,進行回溯  
            {  
                chess[x1][y1]=0;  
                x1=x; //結(jié)點位置也要回溯  
                y1=y;  
            }  
        }  
    }  
    return 0;  
}  
2017年7月21日 05:23
編輯回答
熟稔

唉,郁悶了,就是算法太復雜一直在走。。我以為死循環(huán)了,代碼沒錯,回溯法,不過會耗時太久啊。。。

2017年5月12日 10:08
編輯回答
溫衫

感覺沒問題...... (= =|
打斷點調(diào)試呀

2017年1月16日 17:27