Code:
/* Knight's Tour ( recursive version ) */
#include <stdio.h>
/* 'col' = column */
int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ); /* returns the number of moves made */
int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */
int visited( int nextRow, int nextCol, int board[][ 8 ] ); /* check if next square is visited already */
int bubbleSort( int a[] );
int main()
{
int board[ 8 ][ 8 ] = { 0 };
printf( "***Knight's Tour***\n\n" );
printf( "\nNumber of moves made: %d \n\n", knights_tour( 0, 0, board));
getch();
return 0;
}
int out_of_bounds( int nextRow, int nextCol )
{
/* Returns 1 if out of bounds.
Returns 0 if O.K. */
if ( nextRow < 0 || nextRow > 7 )
return 1;
if ( nextCol < 0 || nextCol > 7 )
return 1;
/* O.K. */
return 0;
}
int visited( int nextRow, int nextCol, int board[][ 8 ] )
{
/* Returns 1 if visited.
Returns 0 if not visited. */
if ( board[ nextRow ][ nextCol ] == 1 )
return 1;
return 0;
}
int knights_tour( int startingRow, int startingCol, int board[][ 8 ] )
{
/* moveNumbers: 0 1 2 3 4 5 6 7 */
int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int temp1, temp2;
int currentRow = startingRow;
int currentCol = startingCol;
int totalMoves = 0;
int end = 0;
int moveNumber;
int arrayToSort[ 8 ] = { 0 };
int retval;
int i;
int potentialMoves;
int access[ 8 ][ 8 ] = { { 2, 3, 4, 4, 4, 4, 3, 2 },
{ 3, 4, 6, 6, 6, 6, 4, 3 },
{ 4, 6, 8, 8, 8, 8, 6, 4 },
{ 4, 6, 8, 8, 8, 8, 6, 4 },
{ 4, 6, 8, 8, 8, 8, 6, 4 },
{ 4, 6, 8, 8, 8, 8, 6, 4 },
{ 3, 4, 6, 6, 6, 6, 4, 3 },
{ 2, 3, 4, 4, 4, 4, 3, 2 } };
while ( end != 1 ) {
potentialMoves = 0; /* reset number of potential moves */
for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) {
temp1 = currentRow + vertical[ moveNumber ];
temp2 = currentCol + horizontal[ moveNumber ];
if ( out_of_bounds( temp1, temp2 ) != 1 && visited( temp1, temp2, board ) != 1 ) {
arrayToSort[ moveNumber ] = access[ temp1 ][ temp2 ];
++potentialMoves;
}
else { /* Next move not possible */
if ( moveNumber == 7 )
end = 1; /* No more possible moves... */
continue;
}
}
access[ currentRow ][ currentCol ] = potentialMoves; /* reduce accessibility number */
retval = bubbleSort( arrayToSort ); /* returns smallest accessibility number */
for ( moveNumber = 0; moveNumber < 8; moveNumber++ ) {
temp1 = currentRow + vertical[ moveNumber ];
temp2 = currentCol + horizontal[ moveNumber ];
if ( access[ temp1 ][ temp2 ] == retval ) {
board[ currentRow ][ currentCol ] = 1;
currentRow += vertical[ moveNumber ];
currentCol += horizontal[ moveNumber ];
++totalMoves;
printf( "board[ %d ][ %d ]\n", currentRow, currentCol );
printf( "%d\n", retval );
break;
}
}
}
return totalMoves;
}
int bubbleSort( int a[] )
{
/* ascending sort */
int pass, i, j, hold, arraySize = 8;
for ( pass = 1; pass <= arraySize - 1; pass++ )
for ( j = 0; j <= arraySize - 2; j++ )
if ( a[ j ] > a[ j + 1 ] ) {
hold = a[ j ];
a[ j ] = a[ j + 1 ];
a[ j + 1 ] = hold;
}
/* reusing j */
for ( j = 0; j < 8; j++ )
if ( a[ j ] != 0 )
return a[ j ];
else
continue;
}