c - 在 ChessBoard C 代码中遍历骑士

Question

我写了一个代码，让一个骑士只走一次棋盘上的所有方格。这个(下面)代码的问题是，它一直工作到 7x7，而在 8x8 之后什么都不做。代码是这里 chessBoardSize 定义了尺寸(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;
}

Answer 1

问题是您使用的方法无法在任何合理的时间内解决 8x8 或以上问题。您的代码没有问题，但有 4e51 种可能的移动，因此您的程序将花费大量时间来寻找游览。

在您的程序中，迭代次数如下:

5x5 = 74,301

6x6 = 2,511,583

7x7 = 136,328

对于 8x8，您的程序最多需要执行以下操作:

3,926,356,053,343,005,839,641,342,729,308,535,057,127,083,875,101,072 次迭代。