c - ChessBoard C COde中的Traverse Knight

我写了一个代码，让一个骑士只能穿越一次棋盘上的所有方块。这个（下面）代码的问题是，它一直工作到7x7，在8x8之后什么也不做。代码是
这里棋盘大小定义了大小（8=>8x8）

#include<stdio.h>
#include<stdlib.h>
#define chessBoardSize 12

int chessBoard[chessBoardSize][chessBoardSize] = {0};
typedef struct point{
    int x, y;
}POINT;
int count=0;

int nextPosition(int x, int y, POINT* array){
    int m=0;
    /* finds the next possible points for the current
    position in the chess board:
    like
    _   _   _   _   _   _
    _   *   _   *   _   _
    *   _   _   _   *   _
    _   _   P   _   _   _
    *   _   _   _   *   _
    _   *   _   *   _   _

as above if 'P' is the current (x,y)
* represents the next possible points and
also checks it exists within the chess board
    */

    if( (x+2) < chessBoardSize ){
        if( (y+1) < chessBoardSize ){
            array[m].x = x+2;
            array[m++].y = y+1;
        }
        if( (y-1) >-1 ){
            array[m].x = x+2;
             array[m++].y = y-1;
        }
    }

    if( (x-2) > -1){
        if( (y+1) < chessBoardSize ){
            array[m].x = x-2;
            array[m++].y = y+1;
        }
        if( (y-1) >-1 ){
            array[m].x = x-2;
            array[m++].y = y-1;
        }
    }

    if( (y+2) < chessBoardSize){
        if( (x+1) < chessBoardSize ){
            array[m].x = x+1;
            array[m++].y = y+2;
        }
        if( (x-1) >-1 ){
            array[m].x = x-1;
            array[m++].y = y+2;
        }
    }

    if( (y-2) > -1){
        if( (x+1) < chessBoardSize ){
            array[m].x = x+1;
            array[m++].y = y-2;
        }
        if( (x-1) >-1 ){
            array[m].x = x-1;
            array[m++].y = y-2;
        }
    }
    return m;
}

void displayAnswer(){
    int i, j, k;
    printf("\n");
    for(i=0; i<chessBoardSize; i++){
        for(j=0; j<chessBoardSize; j++)
            printf("%d\t",chessBoard[i][j]);
            printf("\n\n");
    }
}

//  recursive function using backtrack method
void knightTravel(int x, int y){
    POINT array[8] = {{0, 0}, {0, 0}};
    // remainin initialized to zero automatically
    volatile int noOfPossiblePoints = nextPosition(x, y, array);
    volatile int i;

    chessBoard[x][y] = ++count;

    // base condition uses count
    if( count == chessBoardSize * chessBoardSize ){
        displayAnswer();
        exit(0);
    }

    for(i=0; i< noOfPossiblePoints; i++)
        if( chessBoard[array[i].x][array[i].y] == 0 )
            knightTravel(array[i].x, array[i].y);

    chessBoard[x][y] = 0;
    count--;
}

int main()
{
    knightTravel(0, 0);
    printf("No solution exists\n");
    return 0;
}

最佳答案

问题是，您使用的方法无法在任何合理的时间内解决8x8或以上的问题你的代码是好的，但有4E51可能的移动，所以你的程序将需要大量的时间找到一个旅游。
在您的程序中，迭代次数如下：
5x5=74301
6x6=2511583
7x7=136328
对于8x8，您的程序最多需要执行以下操作：
3926356053343005839641342729305103057127083875101072次迭代。