Total number of moves required for horse to cover all the cells in chessboard

I have seen lots of students and companies asking this question. I have wrote the complete program for horse movement in the chessboard and will find the mininmum number of moves that horse takes to cover all the cells of chessboard. It is surprised that in 64 moves horse can complete the all cells in chessboard.

/* chess 64 squares.. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 8
enum { false, true };
int chess[MAX][MAX];

int runHorse(int i,int j, int count)
{
    int r[MAX][2],k;

    r[0][0] = i-2;    r[0][1] = j-1;
    r[1][0] = i-2;    r[1][1] = j+1;
    r[2][0] = i-1;    r[2][1] = j+2;
    r[3][0] = i+1;    r[3][1] = j+2;
    r[4][0] = i+2;    r[4][1] = j+1;
    r[5][0] = i+2;    r[5][1] = j-1;
    r[6][0] = i+1;    r[6][1] = j-2;
    r[7][0] = i-1;    r[7][1] = j-2;

    if(count == 63)
    {
     chess[i][j] = count;
     return true;
    }
    for(k=0; k<8; k++)
    {
        if((r[k][0] >= 0) && (r[k][0] < MAX) &&
           (r[k][1] >= 0) && (r[k][1] < MAX) &&
             chess[r[k][0]][r[k][1]] < 0)
        {
          chess[i][j] = count;
          if(runHorse(r[k][0],r[k][1], count+1))
            return true;
        }        
    }    
    chess[i][j] = -1;
    return false;
}
int main()
{
    int i,j;
    time_t start,end;
    
    for(i=0; i<MAX; i++)
     for(j=0; j<MAX; j++)
      chess[i][j] = -1;

    start = clock();
    runHorse(0,1,0);
    end = clock();

    for(i=0; i<MAX; i++)
    {
     for(j=0; j<MAX; j++)
      printf("%d\t",chess[i][j]);
     printf("\n");
    }
    printf("Time required %ld\n",(end-start)/CLOCKS_PER_SEC);
}

Regards,
Megha
By Perry    Popularity  (843 Views)