In 1759, Leonhard Euler, one of the greatest minds of the Enlightenment, published “Solution of a curious question which does not seem to be subject to any known method”. It concerned a problem familiar to every chess player: how can a knight visit all 64 squares of the board without visiting any square twice?
Over time, the problem has been generalized repeatedly. The board need not have 64 squares, for example; it can be any rectangular board divided into m × n equal squares.
Leonhard Euler, Alexandre Vandermonde and others found particular solutions. Naturally, celebrated chess players also tackled it, including Carl Friedrich von Jaenisch and Vasily Nikolayevich Panov.
In graph-theoretic terms, each route visiting every square corresponds to a Hamiltonian path, or to a Hamiltonian cycle if the route is closed, in a graph whose vertices are the board’s squares. Two vertices are joined by an edge when a knight can move between their squares in one move. On an 8 × 8 board, the number of closed knight’s tours, or Hamiltonian cycles, disregarding direction, is 13 267 364 410 532. The number of open tours, counting direction, is 19 591 828 170 979 904.
The problem admits different mathematical models, algorithms and computer programs, and has also been solved by chess automata.
In 1823, a certain Warnsdorff published a pamphlet, The Simplest and Most General Solution to the Knight’s Tour Problem, proposing an algorithm for traversing an 8 × 8 board.
“At each move, place the knight on a square from which it has the fewest possible moves to squares not yet visited. If several such squares exist, any of them may be chosen.”
In practice, this rule makes it easy to construct tours. For a long time, however, it was not known whether it always held. Several papers have provided counterexamples to Warnsdorff’s rule. Computer-generated counterexamples exist for every starting square. In other words, wherever the knight begins, choices consistent with Warnsdorff’s rule can lead it into a dead end before it has visited the entire board.
Nevertheless, try applying the rule. Assume the squares are numbered in some way, for example as in the figure. Cross out squares that the knight has already visited. To make the algorithm deterministic, choose the square with the lowest number.
This problem appears in several collections of historical and recreational problems, for example:
- Balk, M. B.; Balk, G. D. Mathematics After Lessons: A Guide for Teachers. Moscow: Prosveshcheniye, 1971. 462 pp. [In Russian]
- Gik, E. Ya. Chess and Mathematics. Moscow: Nauka, 1983. 176 pp. [In Russian]
- Ignatyev, E. I. In the Kingdom of Ingenuity. Moscow: Nauka, 1978. 192 pp. [In Russian]
