A Python solution for a classic chess puzzle
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.
Infos
- The history of the Knight's Tour: https://www.cma.fct.unl.pt/sites/www.cma.fct.unl.pt/files/knights_tours_final.pdf
- The Knight's Tour in Wikipedia: https://en.wikipedia.org/wiki/Knight's_tour
- Monte Carlo testing in Wikipedia: https://en.wikipedia.org/wiki/Monte_Carlo_method
- Dally, S. (editor). The Century/Acorn User Book of Computer Puzzles; Century Publications, 1984: https://openlibrary.org/books/OL15157004M/Book_of_computer_puzzles?v=17
- Code for this article (
knights_tour.py
): ftp://ftp.linux-magazine.com/pub/listings/magazine/211 - Pygame: https://www.pygame.org/
- Singha, M., A. Kakkarb, and M. Singh. "Image Encryption Scheme Based on Knight's Tour Problem." Procedia Computer Science 70 (2015), pg. 245 – 250: https://ac.els-cdn.com/S1877050915032457/1-s2.0-S1877050915032457-main.pdf?_tid=2f9f40be-12f8-43a3-b007-a0b80b271201&acdnat=1520931505_5f2fdc94f5e805770654f2e794c2eaf6
- Tomatis, M. and M. Williamson. "Detailed analysis of the Great Parchment of Rennes-le-Château." Indagini Su Rennes-Le-Chateau (2008): http://www.renneslechateau.it/index.php?sezione=studi&id=greatparchment
« Previous 1 2
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Direct Download
Read full article as PDF:
Price $2.95
News
-
Mozilla VPN Now Available for Linux
The promised subscription-based VPN service from Mozilla is now available for the Linux platform.
-
Wayland and New App Menu Coming to KDE
The 2021 roadmap for the KDE desktop environment includes some exciting features and improvements.
-
Deepin 20.1 has Arrived
Debian-based Deepin 20.1 has been released with some interesting new features.
-
CloudLinux Commits Over 1 Million Dollars to CentOS Replacement
An open source, drop-in replacement for CentOS is on its way.
-
Linux Mint 20.1 Beta has Been Released
The first beta of Linux Mint, Ulyssa, is now available for downloading.
-
Manjaro Linux 20.2 has Been Unleashed
The latest iteration of Manjaro Linux has been released with a few interesting new features.
-
Patreon Project Looks to Bring Linux to Apple Silicon
Developer Hector Martin has created a patreon page to fund his work on developing a port of Linux for Apple Silicon Macs.
-
A New Chrome OS-Like Ubuntu Remix is Now Available
Ubuntu Web looks to be your Chrome OS alternative.
-
System76 Refreshes the Galago Pro Laptop
Linux hardware maker has revamped one of their most popular laptops.
-
Dell Will Soon Enable Privacy Controls for Linux Hardware
Dell makes it possible for Linux users to disable webcams and microphones.