Траверс Найт в шахматной доске C-код - PullRequest
Новая
       21

Траверс Найт в шахматной доске C-код

0 голосов
/ 24 января 2012

Я написал код для прохождения рыцаря по всем клеткам на шахматной доске только один раз.Проблема с этим (ниже) кодом заключается в том, что он работает до 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;
}

1 Ответ

2 голосов
/ 24 января 2012

Проблема в том, что используемый вами подход не может решить 8x8 или выше в любое разумное время.Ваш код в порядке, но есть 4e51 возможных ходов, поэтому вашей программе потребуется фантастическое количество времени, чтобы найти тур.

В вашей программе число итераций следующее:

5x5= 74,301

6x6 = 2,511,583

7x7 = 136,328

Для 8x8 ваша программа должна выполнить до:

3,926,356,053,343,005,839,641,342,729,101,072,025,101,072,875.

...