Knight's Tour Program

The Knights Tour program will enable you to practice solving the Knight's Tour by hand using the Diamonds and Squares method, Warnsdorff's rule, or any of the many other strategies [1, 2]. The program (knights_tour.py) is available for download at the Linux Pro Magazine website [5]. To use the program, you'll need Python 3 and the Pygame library [6], which is available as a package on many Linux systems. You can also use the Knight's Tour program to find and display a huge number of solutions from any starting square. A mouse is used for interacting with the program. You can click on any of the options on the right-hand side of the window and click on any of the chessboard squares. On the right-hand side of the window are five options from which to choose (Figure 5):

1. leave this game is self explanatory.

2. start/restart game is selected by default when the program starts. This option allows you to choose the starting square for the puzzle and then to place the next and subsequent knights on the board. You can backtrack while this option is active and restart the game by clicking on this option at any time.

3. When the next move on/off option is on, it places a small star in the top-left corner of squares that are legitimate knight's moves to indicate where the next move can be made when you're attempting to solve the puzzle. This includes a backtracking square – very useful if you want to practice Warnsdorff's rule. You can toggle this option on and off at any time while you are trying to solve the puzzle by hand.

4. show a Knight's Tour will find a Knight's Tour using Warnsdorff's rule and then step out the tour from the first square of any game. If a game hasn't been started, you can click on any square to show a tour after selecting this option.

5. display a quick tour will instantly display a Knight's Tour from your starting square if you're trying to solve the puzzle, or from any other square clicked after selecting this option.

Options 4 and 5 allow you to click on the same square repeatedly to display alternative tours from one starting square or to click on any other square to start from a different square.

What Else?

You can use the Knight's Tour to encrypt images [7]. One weakness of using the puzzle as an encryption technique is that the encoder can also be used as a decoder, so you can't employ it for the asymmetric public encryption and private decryption methods used on the Internet.

An older use of the Knight's Tour has been to hide text messages in plain sight [8]. Suppose someone wanted to encrypt the message this message is hidden in plain sight. First of all, the spaces and punctuation are removed so that the 31 characters in the text become the string thismessageishiddeninplainsight. The message can still be read easily, but it does not have spaces that would indicate the beginning or end of a word.

You can then use a Knight's Tour, such as the one depicted in Figure 5, to hide the text. The first character of the message is placed on the square 1, the second on the square 2, and so on until the last character is placed on square 31. The remaining unused squares are then filled with random characters. Reading the hidden message one row at a time gives an indecipherable string of 64 meaningless characters, and this string can be punctuated with spaces to give the impression that a substitution cypher is being used. Random characters can also be added to the end of the message so that the hidden message doesn't always have 64 characters – which might hint at how the text has been encrypted.

Unless someone knows how the message has been hidden, and which of the millions of possible Knight's Tours was used to hide it, it is virtually impossible to read the message. The message is padded out with redundant characters, making it difficult to decrypt by looking for anagrams, and finding the right combination of characters by chance is virtually impossible because there are (64! / (64-31)!) combinations of 31 characters from 64, and this is three orders of magnitude more than the number of atoms on Earth. The downside of this encryption technique is that both the encoder and the decoder need to use the same code book or program to encrypt and decrypt the message, making it much more vulnerable than modern public key/private key encryption.

The Author

Gordon doesn't really like the sort of confrontational competition that playing chess seems to encourage, and which inevitably creates winners and losers. As he's both a bad winner and a bad loser, Gordon prefers chess puzzles to actually playing chess.