I first read about the Knight’s Tour when I was a kid. My mom bought the Time Life series of books on computers. It it, the Knight’s Tour program is presented, which fascinated me. After all this time, I finally set out to code the tour myself.

The goal of the knight’s tour is to move a knight around a chessboard in a pattern where the knight never visits the same square twice. You can read up on the details on the all-knowing Wikipedia.

To me, it seemed obvious that coding the knight’s tour involves some sort of recursion. When the knight can no longer move, it must be backed out and try a different path. But according to the mathematicians who study these things, such as an approach might take a painfully long time to complete.

To be expedient, I opted to use Warnsdorff’s rule. (See the Wikipedia article.) This heuristic states that the knight should move to the square that has the fewest number of subsequent moves.

For example, in Figure 1, the knight is in row three, column seven. It has six potential moves: Two of them have eight subsequent moves, two have four, one has six, and one valid move has only two subsequent moves. (Technically that last location has only one subsequent move as the knight shouldn’t move back to its starting square – but first things first!)

Figure 1. The knight at a random position, its six valid moves, and count of subsequent moves.

According to Warnsdorff’s rule, the knight should move to the first row, eighth column, where it has only two (one) valid subsequent moves. This process continues, mapping out the knight’s tour around the chessboard. Before implementing this solution, I need to update the code from last week’s Lesson to add a forward move count forecast. This improvement involves changes to the main() and chess_board() functions.

To update the main() function, two new arrays are added: next[] and tally[].

The next[] array holds the knight’s next series of moves from potential new locations.

The tally[] array holds the move count for each of the subsequent, subsequent moves.

Here is the updated main() function:

/* set the knight at a random location
   and show the valid moves */
int main()
{
    int knight,x;
    int moves[KM],next[KM],tally[KM];

    /* seed the randomizer */
    srand( (unsigned)time(NULL) );

    /* pluck out a random square
       for the knight */
    knight = rand() % (SIZE*SIZE);

    /* calculate where the piece can move */
    moveto(knight,moves);

    /* calculate next moves */
    for( x=0; x<KM; x++ )
    {
        /* only plot valid moves */
        if( moves[x] != -1 )
        {
            moveto(moves[x],next);
            tally[x] = movecount(next);
        }
        else
        {
            /* copy over the -1 */
            tally[x] = moves[x];
        }
    }

    /* output the board */
    chess_board(knight,moves,tally);

    return(0);
}

A for loop processes all potential moves obtained from the moveto(knight,moves); call. For each valid location in the moves[] array, the knight is pretend-relocated to the given position. A second call is made to moveto() to find the subsequent moves from the new square. These are stored in the next[] array. Then the tally[] array is filled with results from the movecount() function.

The chess_board() function is updated to output the movecount() values stored in the tally[] array. The output appears as shown in Figure 1.

You can view the complete code on GitHub, along with my comments that explain various details.

At this point, the code is getting complex! It’s serious brain work to keep track of all the pieces. Yet, if I want to implement the Knight’s Tour using Warnsdorff’s rule, these details are necessary.

In next week’s Lesson I complete the Knight’s Tour code with some major updates and modifications.