A Python solution for a classic chess puzzle
Knight's Tour
If you're looking for a head start on solving the classic Knight's Tour chess challenge, try this homegrown Python script.
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.
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 righthand (RH) diamond (Figure 2a). The second is a lefthand (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.
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).
If you place the first knight on, for example, b3, then you can complete a fourknight partial tour in the lower lefthand 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 fourknight 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 fourknight, RH diamondshaped partial tour on them, and there are 16 knights on the board (Figure 3a). After completing the RH diamondshaped partial tour, you move on to a squareshaped partial tour, in this example, a RH squareshaped partial tour starting at c4 and ending at d6 (Figure 3b). Then you can complete a LH diamondshaped partial tour starting at e8 and ending at b6 (Figure 3c) and finally a LH squareshaped 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, 16knight, diamondshaped, LH and RH partial tours and two, 16knight, squareshaped, LH and RH partial tours in the order diamondsquarediamondsquare or squarediamondsquarediamond. 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 ruleofthumb 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.
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 secondpriority move. If that doesn't work, you can backtrack again and choose the thirdpriority move, and so on until all the tiebreakers have been tried. If that doesn't overcome the impasse, backtrack to the lastbutone 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.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Direct Download
Read full article as PDF:
Price $2.95
News

OpenStack Foundation Changes Name of the OpenStack Summit
New event will be known as the Open Infrastructure Summit

System76 Announces a Line of USMade PCs
Thelio series is available for preorder and will ship in early December.

IBM Acquires Red Hat
IBM is acquiring Red Hat, the most successful open source company.

Fedora 29 and Ubuntu 18.10 Released
New releases focus on boot time, new hardware, and modular design.

Redis Labs Modules Forked
New Commons Clause license rider causes Debian and Fedora developers to fork Redis Labs modules.

Microsoft Offers its Patent Portfolio
The company ends its long war; vows to protect Linux.

Red Hat Reports $823 Million in Revenue for Second Quarter 2019
Strong performance for cloud and container products leads to a 14% increase over last year.

Debian, Ubuntu, and Other Distros are Leaving Users Vulnerable
A security researcher says Linux vendors wait too long to patch the kernel.

NextCloud 14 Arrives
The new version adds two new security features for users.

Linus Torvalds Takes a Break, Apologizes
The creator of Linux is admitting his abusive behavior on LKML and plans to change.