A chess knight can travel around a chessboard using the knight's move and visit every square once, and only once. This is known as the Knight's Tour. The Knight's Tour is usually played with numbered counters on a conventional chessboard (Figure 1), but you can play it on any rectangular board with five or more rows and columns.

Figure 1: The Knight's Tour is usually played on a chessboard with counters to mark the progress. This tour starts on the square with the black knight and ends on the square with the white knight.

The Knight's Tour is an example of a classic mathematical problem that lends itself to easy and creative expression through computer programming. I created a Python program to help users practice solving the Knight's Tour. The Knight's Tour program is a good example of the simple yet powerful applications you can build with the Pygame Python library for computer gamers.

Solving the Knight's Tour

At first, solving the Knight's Tour seems to be a daunting challenge, but quite a few strategies exist that will help you solve the puzzle [1]. I'll consider just two of them. The first strategy is usually known as the Diamonds and Squares method, and it's a simple party trick that anyone can learn in minutes.

Solving the Knight's Tour using the Diamonds and Squares technique doesn't require any mathematical talent or much logical skill; it merely requires the player to recognize two simple geometric shapes in the patterns of knight's moves. This approach can produce a relatively small number of apparently unique tours from every starting square, but the symmetry of the chessboard means that many of these solutions are transformations of other tours by rotation, reflection, or inversion, and this simple technique can only produce 46 truly unique Knight's Tours on a chessboard. Most of the Knight's Tour solution videos you watch on YouTube and elsewhere demonstrate the Diamonds and Squares method.

The second approach is known as Warnsdorff's rule. This strategy takes a bit more effort to master. On an 8x8 chessboard, it can produce thousands of different Knight's Tours from any starting square, but, again, the symmetry of the chessboard means that not all of these solutions are truly unique and many of them are transformations of other Warnsdorff's rule tours. As you'll see in a moment, Warnsdorff's rule can sometimes lead to an impasse, but it still produces far more solutions than the Diamonds and Squares method.

If you want to impress your friends by showing them how to solve the Knight's Tour, then using Warnsdorff's rule will not expose you as a chess puzzle pretender, but using the simple Diamonds and Squares technique might put your reputation as a chess puzzle genius in jeopardy.

Diamonds and Squares

The Diamonds and Squares technique was first described by C. R. R. von Schinnern in 1826 [1]. It only works on boards that have at least 8x8 squares. Larger boards must have a number of rows and columns that are a multiple of four (i.e., 12x12, 8x16, and so on). Unlike Warnsdorff's rule, the Diamonds and Squares technique cannot be used to solve the Knight's Tour on a 6x6 or a 10x10 board.

To employ the Diamonds and Squares strategy on a conventional 8x8 chessboard, you need to divide the chessboard into four quadrants and understand how four knights can be placed on a quadrant in four distinct patterns. The first of these patterns is described as a right-hand (RH) diamond (Figure 2a). The second is a left-hand (LH) diamond (Figure 2b), the third is a RH square (Figure 2c), and the last one is a LH square (Figure 2d). When these four shapes are joined together on one quadrant of the chessboard, all 16 squares in that quadrant will have a knight on them.

Figure 2: Any chessboard quadrant can be filled with 16 knights arranged in four shapes: 2a is the right-hand diamond, 2b the left-hand diamond, 2c the right-hand square, and 2d the left-hand square.

In order to use the diamond and square shapes to solve the Knight's Tour, you need to know whether the first knight placed on the board is on a diamond (either RH or LH) or on a square (either RH or LH). For example, a knight at b3 is on a RH diamond (Figure 3a), one at c4 is on a RH square (Figure 3b), a knight at d1 is on a LH diamond (Figure 3c), and one at d3 is on a LH square (Figure 3d).

Figure 3: The Knight's Tour can be completed by combining four, 16-knight, partial tours using all four shapes; in this example, RH diamonds are followed by RH squares, and then LH diamonds are followed by LH squares.

If you place the first knight on, for example, b3, then you can complete a four-knight partial tour in the lower left-hand quadrant with four knights on a RH diamond shape (Figure 3a). You then move onto an adjacent quadrant and use a RH diamond shape to complete another four-knight partial tour on that quadrant. Then you can move on to a third quadrant and then the fourth so that all four quadrants have a four-knight, RH diamond-shaped partial tour on them, and there are 16 knights on the board (Figure 3a). After completing the RH diamond-shaped partial tour, you move on to a square-shaped partial tour, in this example, a RH square-shaped partial tour starting at c4 and ending at d6 (Figure 3b). Then you can complete a LH diamond-shaped partial tour starting at e8 and ending at b6 (Figure 3c) and finally a LH square-shaped partial tour starting at d7 and ending at g5 to complete the Knight's Tour (Figure 3d).

The Knight's Tour can always be solved by combining two, 16-knight, diamond-shaped, LH and RH partial tours and two, 16-knight, square-shaped, LH and RH partial tours in the order diamond-square-diamond-square or square-diamond-square-diamond. You will need to make sure that the fourth knight placed in each quadrant leads to an empty square on an adjacent quadrant. With a bit of practice, it's quite easy to solve the Knight's Tour from any starting square using this method.

You can find variations of the Diamonds and Squares technique that will allow you to choose the starting and ending square, but be warned, nearly everyone who knows about the Knight's Tour knows about the Diamonds and Squares method, and you can only impress naive chess puzzlers by demonstrating this technique.

Warnsdorff's Rule

The second strategy is known as Warnsdorff's rule [1, 2] and it is named after H. C. von Warnsdorff, who first described it in 1823. Warnsdorff's rule is a heuristic or rule-of-thumb method for finding a Knight's Tour from any starting square on any sized board with at least 5x5 squares. I'll look at it on a conventional chessboard.

Warnsdorff's rule is summarized as follows:

1. With each move, you have to look ahead to see which of the possible next moves has the least number of exits that can be taken using the knight's move (Figure 4). An exit is a legal move to a square that the knight hasn't inhabited yet.

Figure 4: Warnsdorff's rule requires that you look ahead to find the next move that has the least number of exits. In this example, looking ahead from the first position at a3 shows that a move to the second position at b1 has the least number of exits (the exits are marked with stars).

2. The square with the least number of valid exits is chosen for the next move.

3. If there is a tie between two or more squares, the next square is chosen at random from all the squares with the least number of exits.

Unfortunately, if a Monte Carlo test [3] is done when Warnsdorff's rule is applied to a conventional chessboard, about three percent of the attempts to find a complete tour will lead to an impasse. If you want to find a Knight's Tour every time using Warnsdorff's rule, you need to modify the original rule to overcome any impasse that might occur. Do this by replacing the random choice of a tiebreaker with a systematic choice.

The easiest variant of Warnsdorff's rule to implement in a computer program requires very little coding. It modifies the third element of Warnsdorff's rule so that, if there is a tie for the next move between two or more squares, the next square is chosen systematically – any systematic way of choosing the tiebreaker will do as long as it prioritizes the way in which the tied moves are selected to break the tie. If breaking a tie systematically leads to an impasse, the calculation can just start again using a different way of making a systematic choice. This is quite a good option for a computer program, because a computer can find a complete tour using an alternative way of choosing a tiebreaker in milliseconds. The program overcomes any impasse that might occur using this simple plan – if the way you're choosing a tiebreaker doesn't work, then stop using it, start again, and choose your tiebreaker in a different way.

Another variant of Warnsdorff's rule is better if you're trying to find a way out of an impasse by hand, because it usually involves less work than starting again. If systematic tie breaking leads to an impasse, you can backtrack to the last tiebreaker and take the second-priority move. If that doesn't work, you can backtrack again and choose the third-priority move, and so on until all the tiebreakers have been tried. If that doesn't overcome the impasse, backtrack to the last-but-one tiebreaker, select the second priority tiebreaker, and keep doing this until the impasse is overcome. The computer program will enable you to backtrack in this way if you're using Warnsdorff's rule (or any other strategy) to solve the puzzle by hand and you get stuck in an impasse. The program doesn't use backtracking when it's finding a solution for you, but if you'd like to see how a program can use backtracking to find a way out of an impasse, there's a backtracking algorithm used in a Knight's Tour program I wrote when I first became interested in chess puzzles many years ago. This program was published in The Century/Acorn User Book of Computer Puzzles [4].

Any systematic way of choosing can be used as a tiebreaker for either of the alternative versions of Warnsdorff's rule described above, but remember, it must be a systematic choice rather than a random one. There are eight factorial (8! = 40320) ways in which you can make a systematic choice, but two of the easiest ones to remember when finding a Knight's Tour by hand are to select the tiebreaker in either a clockwise or counterclockwise direction starting at the 12 o'clock position (i.e., start looking from the top of the board and work your way around the tied moves to the right or to the left).

A very handy shortcut version of Warnsdorff's rule can be used to place the first 30 or so knights on the board. This technique works because, in the first half of solving the puzzle, selecting the square with the least number of exits is usually the same as moving the knight as far away from the center of the board as possible – but beware, this shortcut will occasionally disappoint you.

The shortcut requires you to stay as close to the edge of the board as possible and to prioritize the corner squares and their adjacent perimeter squares. This will usually result in two circuits of the board's perimeter during the first half of the tour, after which it's better to stop using the shortcut and start calculating the best way around the empty squares on the board using systematic tie breaking. An insight into what's needed to solve the puzzle is also very useful during the second half of the tour, and you will develop the necessary insight with practice. The fewer knights that are placed on the board using this shortcut, the better it works. The shortcut becomes less reliable as more knights are placed on the board, and the chance that it will let you down increases noticeably when there are more than half of the knights on the board. The Knight's Tour shown in Figure 5 was found using this shortcut combined with backtracking and insight. With practice, it takes only a couple of minutes to find a complete Warnsdorff's tour by hand.

Figure 5: The Knight's Tour program will help you to solve the puzzle using any strategy, including backtracking if you choose. The tour in this illustration is described as a closed tour, because the first and last positions are just one knight's move apart. The program will solve the puzzle for you if you click on one of the blue options on the right and then select a starting square.