The task is truly complex: Navigating a knight around a chessboard, visiting each square but never the same square twice. It took me a while to code, and I don’t think my solution is particularly elegant, but it works.

As I wrote in last week’s Lesson, my solution involves using the Warnsdorff’s rule. I found this heuristic to be solid enough that I didn’t need to use recursion: A simple loop counting all the squares in the chessboard is sufficient to solve the problem.

Yes, using a loop instead of recursion frightened me, but the damn thing works, as seen by the animation in Figure 1.

Figure 1. An animation of my solution for the Knight’s Tour.

In the figure, you see the Knight start at a random position. Values starting at zero plot the knight’s path around the chessboard, never visiting the same square twice. The final square is numbered 63.

The first major change I made from the code in last week’s Lesson is to make the board[] array (formerly in the chess_board() function) external. While I’m not a fan of external variables, this move made calling the various functions a lot easier.

Further, the chess_board() function now has no arguments. It outputs the board setting numbers at the positions where the knight has already moved. An snprintf() function outputs the knight’s movement values. If a square is set to -1, the initialization value, spaces are output.

The moveto() function is updated with a new test to confirm whether a square is occupied. The if-else test looks like this:

if( (r<0 || r>=SIZE) || (c<0 || c>=SIZE) )
{
    /* square is out of bounds */
    m[x] = -1;
}
else
{
    /* plot position */
    m[x] = r * SIZE + c;
    /* confirm that square hasn't
       already been occupied */
    if( board[m[x]] > -1 )
        m[x] = -1;
}

The if test within the else block – if( board[m[x]] > -1 ) – checks a square to see whether it’s been visited. If so, -1 is set, marking the square off-limits.

The movecount() function is unchanged.

I added a new function, knightmove() to relocate the knight. It contains statements previously found in the main() function:

/* move the knight
   s = square to move to
   return the next square, the one
   with the least number of next-moves */
int knight_move(int s)
{
    int x,lowest,newpos;
    int moves[KM],next[KM],tally[KM];
    struct plot {
        int square;
        int count;
    } nextmove[KM];

    /* calculate where the piece can move */
    moveto(s,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];
        }
    }

    /* build the structure to determine
       where to move next */
    for( x=0; x<KM; x++ )
    {
        nextmove[x].square = moves[x];
        nextmove[x].count = tally[x];
    }

    /* move the knight to the lowest ranking position */
    lowest = 8;            /* eight is the highest possible value */
    for( x=0; x<KM; x++ )
    {
        /* find the square with the lowest count */
        if( nextmove[x].count<lowest && nextmove[x].count!=-1 )
        {
            lowest = nextmove[x].count;
            newpos = nextmove[x].square;
        }
    }

    return(newpos);
}

This new function accomplishes three tasks:

First, it builds the next[] and tally[] arrays to plot the knight’s next move.

Second, it builds a structure to store potential moves, which is sorted.

Third, it returns the desired square to move to, the one with the lowest count of succeeding moves (Warnsdorff’s rule). No special decision is made when two squares have the same value.

The updated main() function initializes the board[] array, randomly sets the knight’s starting location, then uses a for loop to process all 64 squares:

/* move around the chess board */
for( x=0; x<SIZE*SIZE; x++ )
{
    board = x;
    c = knight_move(c);
    chess_board();
    getchar();
}

No recursion is used, as apparently my implementation of Warnsdorff’s rule is sufficient to whisk the knight around the chessboard.

Click here to view the full code on GitHub. As I wrote earlier, I’m not proud of the code as it seems clunky to me. I tried to hone it further, making it more elegant. Alas, based on my approach a more poetic version of the program is beyond my reach.

Even so, I was able to run the code on different size chessboards and, yes, it still works. I tried a 5-sided chessboard and a 12-sided chessboard. Thanks to Warnsdorff’s rule, the code properly propels the knight around the board, never hitting the same square twice.

It’s been decades that I’ve known about this problem. I’m delighted that I’ve solved it. I’d still like to explore the Knight’s Tour concept, which I may return to someday. For now, it was fun.