Knight’s tour is still going strong
An ancient but little-known chessboard puzzle is a common problem given to computer programming students and continues to fascinate mathematicians, writes Jason England.
During his illustrious 40-year career master illusionist Harry Kellar’s touring show visited six continents including shows in Sydney, Brisbane, Melbourne and Adelaide in 1876. At the time there was no conjuror more famous – in his later years, Kellar became friend and idol to a young illusionist Harry Houdini. One of the features of Kellar’s celebrated act was a demonstration of an ancient but little-known puzzle called the knight’s tour.
The goal of the knight’s tour is to place a knight on any square of a standard chessboard and, using only the peculiar L-shaped move of the knight, move it step by step around the board so that it lands on each of the remaining 63 squares, once and only once. If the reader is wondering if this is even possible, rest assured that it is – it’s just very difficult if you don’t know what you’re doing!
The knight’s tour is an intellectual puzzle that has been challenging inquisitive minds for at least 1,100 years.
The first published tour was discovered in an Arabic document from approximately 840 CE called The Delight of the Intelligent, A Description of Chess. This leather-bound volume, now held in a collection of medieval works at the University of Manchester Library, describes two different types of knight’s tours, both still used today.
A “closed” or “re-entrant” tour is one in which the knight ends on a square one L-shaped move away from where it began forming a sort of loop that could repeat itself. An open tour is one in which the knight ends up on a square that is more than one move away from the beginning square.
Although other tours were published over the centuries, the knight’s tour appears to have been largely ignored by serious mathematicians until the mid-18th century when several solutions appeared in the sixth edition of Jacques Ozanam’s Récréations Mathématiques et Physiques in 1725.
This publication appears to have sparked a revival of interest in the tour and its emerging mathematical principles, helping spawn the field of mathematics called graph theory.
If you allow for all directions, rotations and mirror-image tours to be counted
as separate tours, then there are 26,534,728,821,064 of them.
Perhaps the earliest mathematical paper to rigorously analyse the knight’s tour was presented by Leonhard Euler in 1759. Euler is responsible for a good deal of our knowledge of knight’s tours on boards of varying sizes and shapes, not just the standard 8x8 chessboard. For instance, he showed the smallest board on which it’s possible to complete a knight’s tour is a 5x5 board. In fact, it has been proven that tours are possible on any rectangular board where the shortest side is at least five squares, though they can be difficult to find. Certain irregular shaped boards also contain solutions depending on the shape and the number of squares.
With the aid of modern computers, mathematicians have calculated the number of closed tours on a standard 8x8 board. If you allow for all directions, rotations and mirror-image tours to be counted as separate tours, then there are 26,534,728,821,064 of them. Remember, this is just the number of closed tours!
The precise number of open tours is so large it hasn’t even been calculated although research is ongoing. Today, developing a program to find a solution to the knight’s tour is a common problem given to computer programming students. And remarkably, this ancient puzzle continues to spark creativity in the fields of mathematics, heuristics and artificial intelligence, 250 years after Euler’s thorough investigations.
But the beauty of the puzzle is that anyone with an afternoon to spare can enjoy the satisfaction of learning to solve it.
One of the simplest ways to start is to follow “Warnsdorf’s Rule.” First published in 1823, the rule states that one should always “play the knight to a square where it commands the fewest cells not yet used.” Counterintuitive as it sounds, this strategy is actually a good rule of thumb but it can occasionally fail to produce a complete tour.
A similarly concise strategy devised by Dan Tomasson of the US begins with placing the knight in any corner and then “continuously rotate in the same direction around the board moving on the outermost squares,” waltzing the knight around the board. As with the Warnsdorf Rule, Tomasson’s strategy has a few moments when the solution can get a little tricky and require some interpretation and thought to determine the next move.
It may be tricky, but take inspiration from Kellar’s feats. When Kellar revived the puzzle for his full evening shows, he would allow a spectator to choose any starting square on the board, and then proceed to call off the correct series of moves - without ever looking at the board.