Intelligent Knight

Chess provides the setting for many fascinating diversions which are quite independent of the game itself. Many of these are based on the strange L shaped ( often known as two and half ) moves of the knight. A classical example is the problem of the knight's tour, which has captured the attention of mathematicians and puzzle enthusiasts since the beginning of the eighteenth century. Briefly stated, the problem is to move the knight, beginning from top left corner of the chess board, in such a manner that it travels successively to all 64 squares, touching each square once and only once. One solution to this problem was suggested by J. C. Warnsdorff in 1823. The program given below uses a different method - the one based on recursion.

The most important decisions to be made in solving a problem of this type are those concerning how the data is to be represented in the computer. Perhaps the most natural way to represent the chessboard is by an 8 x 8 array. However, I have not done so. Instead what I have used are two arrays row[64] and col[64] to record the row number and the column number as the knight travels on the chessboard.

In general a knight at position ( i, ,j ) may move to any of the squares ( i-2, j+1 ), ( i-1, j+2 ), ( i+1, j+2 ), ( i+2, ,j+1), ( i+2, ,j-1 ), ( i+1, ,j-2 ), ( i-1, ,j-2 ), ( i-2, j-1 ). Notice however that if the knight is located near one of the edges of the board, some of these possibilities could move the knight off the board, and of course this is not permitted. The eight possible moves may conveniently be represented by two arrays ktmov1[ ] and ktmov2[ ] as shown in the following program. Then a knight at ( i, j ) may move to ( i+ktmov[k], j+ktmov2[k] ), where k is some value between 0 and 7, provided that the new square is on the chessboard.

int arr[8][8], row[64], col[64] ; int ktmov1[8] = { -2, -1, 1, 2, 2, 1, -1, -2 } ;

int ktmov2[8] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;

int i, j, move_num, d ; main()

{

addknight( ) ;

}

addknight( )

{

register int a, b, e ;

/* mark the square as visited & record row and col number */

arr[i][j] = 1 ;

row[move_num] = i ;

col[move_num] = j ;

move_num++ ;

/* check one of the 8 possible moves for knight */

for ( a = 0 ; a <= 7 ; a++ )

{

/* if all squares travelled, print the moves */

if ( move_num >= 64 )

{

writeboard( ) ;

exit ( 0 ) ;

}

/* generate row and col number for next move */

b = i + ktmov1[a] ;

e = j + ktmov2[a] ;

/* check whether the move crosses the boundaries */

if ( b < 0 || b > 7 || e < 0 || e > 7 )

continue ;

/* check whether the square has already been visited */

if ( arr[b][e] == 1 )

continue ;

i = b ;j = e ;

addknight( ) ;

}

/* decrement the move counter and try different move */

move_num-- ;

/* free last position occupied by knight */

arr[row[move_num]][col[move_num]] = 0 ;

move_num-- ;

/* try next possible move */

i = row[move_num] ;j = col[move_num] ;

move_num++ ;

}

writeboard( )

{

int a ;

clrscr( ) ;gotoxy ( 1, 10 ) ;

printf ( "Hit any key for next move " );

gotoxy ( 1, 11 ) ;

for ( a = 0 ; a <= 63 ; a++ )

{

if ( a % 8 == 0 )

printf ( "\n" ) ;

printf ( "#" ) ;

}

for ( a = 0 ; a <= 63 ; a++ )

{

gotoxy ( col[a] * 3 + 1, 12 + row[a] ) ;

printf ( "%3d", a + 1 ) ;

getch( ) ;

}

}