The Knight's Tour
March 7, 2014
As a child, I learned to play chess from my father. As an expert woodworker, he had built a sturdy, inlaid chessboard (see photo). I had mastered checkers, so the board was familiar, but the pieces moved in strange ways. This was especially true for the knight, so chess took a while to master. As my father before me, I taught chess to my own son.
Chess achieved great popularity at the time of the 1972 World Chess Championship match between US challenger Bobby Fischer and defending champion Boris Spassky of the Soviet Union. This rekindled my interest in chess. A decade later, my interests in chess and computers were combined when chess programs running on personal computers became available.
The first of the chess programs I played was non-graphical. It was written in Fortran and compiled to run in text mode in MS-DOS. This program was quite primitive compared with the state of the art of computer chess, even at that time, but it was good enough to beat me every time. This might speak more to my chess ability than the program's competence.
One theory of education is that it doesn't really matter what subjects you're taught in school, since education is merely "mental exercise" that prepares you for future tasks. Mental exercise, such as doing crossword puzzles, Sudoku, and, perhaps, writing blog articles, seems to delay the onset of Alzheimer's disease. As I wrote in a previous article (Centers of Excellence, April 29, 2011), some people think that chess should be a part of a child's education, since it builds brain power.
There's a lot of mathematics in chess. The fundamental question of whether computers could ever solve chess is still open, there are a few classic chess problems that incite the attention of mathematicians. One famous such problem, called the eight queens puzzle, was proposed in 1848 by chess theorist, Max Bezzel. This puzzle even evoked the interest of Carl Friedrich Gauss
The object of the eight queens puzzle is to place eight queens on a chessboard in a way that none of the queens can attack each other. The difficulty here is that the queen is the most powerful chess piece, having the ability to move in rows, columns, and diagonals. Thus, a requirement for a solution is that no two queens share the same row, column, or diagonal.
There are 92 distinct solutions, the first of which was discovered two years after the puzzle was posed. If we play the good mathematician and discount the rotational and reflection symmetries, there are just twelve unique solutions, one of which is shown in the figure.
|Heirloom wood inlaid chess board.|
As I remember, the white squares are birch, and the dark squares are walnut.
(Photo by the author.)
As you can imagine, composition of a computer program to solve the eight queens puzzle is a popular computer science homework exercise, especially since the problem can be divorced from the chessboard by just requiring (n-1) pieces to be placed on a grid with no shared rows, columns, or diagonals.
Brute force is obviously not a good approach, since there are 281,474,976,710,656 possible placements of the eight queens, so more elegant methods, such as genetic algorithms and backtracking, are used. In 1976, Niklaus Wirth published a book containing a simple solution program in the Pascal programming language.
The knight's strange manner of movement makes possible another puzzle, called the longest uncrossed knight's path. The idea, as shown in the figure, is to find the longest paths a knight can make on a chessboard without crossing its own path. The paths are either closed, when the starting and ending points are the same, or open, when they're not. This problem, of course, has been generalized to an n-by-n board, and the longest open paths are known only for n up to nine, and the longest closed paths are known only for n up to ten.
There's still more mileage in the knight, as the knight's tour shows. The object of a knight's tour is to visit every space on a chessboard using a knight's movement, but only once. There are 26,534,728,821,064 closed tours on an 8-by-8 board when we count opposite travel directions of the same physical path (a "directed" tour) as being different. The number of open tours on an 8-by-8 board is unknown. This problem has also been generalized to an n-by-n board, and the number of directed open tours rapidly escalates as a function of board size, as shown in the table. This is sequence A165134 of the On-Line Encyclopedia of Integer Sequences.
|A solution of the eight queens puzzle.|
You can see that no two queens share the same row, column, or diagonal.
The eight queens puzzle has been generalized to placing (n-1) queens on an n-by-n chessboard.
(Illustration by the author using Inkscape.)
As a demonstration of the power of modern computing, an artificial neural network was used to find the knight's tour on a 24-by-24 board shown in the following figure.
Neural networks aren't the only computing method for finding a knight's tour. There's also ant colony optimization (ACO), which I discussed in a previous article (Marco Polo Physarum, October 1, 2012). ACO mimics the way that ants find the best path between their colony and a food source. The ants' initial aimlessly wandering in search of food is slowly directed by a trail of a pheromone left by ants bringing food from a food source back to their colony. This pheromone trail is followed by other ants, and they add their own pheromone to the trail. The pheromone is replenished on the best route, and it evaporates in less traveled areas.
ACO has been successfully used in search of knight's tours by computer scientists at the University of Nottingham.[4-5] They've recently discovered about 500,000 new solutions to the knight's tour. There are several good references about the knight's tour at the end of this article.[6-9]
|Tour de force knights tour.|
A knight's tour on a 24x24 board.
A neural network was used to find this solution.
(Illustration by "Pattern86" via Wikimedia Commons.)
- Joe Verghese, M.D., Richard B. Lipton, M.D., Mindy J. Katz, M.P.H., Charles B. Hall, Ph.D., Carol A. Derby, Ph.D., Gail Kuslansky, Ph.D., Anne F. Ambrose, M.D., Martin Sliwinski, Ph.D., and Herman Buschke, M.D., "Leisure Activities and the Risk of Dementia in the Elderly," New England Journal of Medicine, vol. 348, no. 25 (June 19, 2003), pp. 2508-2516.
- Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, 1976, 366 pp. (ISBN 0-13-022418-9, via Amazon).
- The path lengths for the open paths are Sequence A003192 of the On-Line Encyclopedia of Integer Sequences. The path lengths for the closed paths are Sequence A157416 of the On-Line Encyclopedia of Integer Sequences.
- Douglas Main, "Ants Playing Chess Find New Solutions To Old Problem," Popular Science, February 3, 2014.
- P. Hingston and G. Kendall, "Ant Colonies Discover Knight's Tours," Lecture Notes in Computer Science, vol. 3339 (2005), pp. 1213-1218.
- Knight's Tour, Numberphile (http://www.numberphile.com), YouTube video, January 16, 2014.
- Brendan D. McKay, "Knight's Tours of an 8 8 Chessboard," Computer Science Department, Australian National University, Canberra, Australia (PDF file).
- George Jelliss, Knight's Tour Notes, mayhematics.com.
- Ben Hill and Kevin Tostado, "Knight's Tours," December 18, 2004 (PDF file).
Permanent Link to this article
Linked Keywords: Chess; father; woodworking; woodworker; inlay; inlaid; chessboard; English draughts; checkers; chess piece; knight; son; birch; Juglans; walnut; 1972 World Chess Championship; United States; US; Bobby Fischer; Boris Spassky; Soviet Union; decade; computers; chess engine; chess program; personal computer; graphical user interface; Fortran; compiler; compiled; text mode; MS-DOS; computer chess; theory of education; subject; school; education; mental exercise; crossword puzzle; Sudoku; blog; Alzheimer's disease; mathematics; solving chess; mathematician; eight queens puzzle; chess composer; chess theorist; Max Bezzel; Carl Friedrich Gauss; queen; rotational symmetry; reflection symmetry; Inkscape; computer science; homework; grid; brute-force search; genetic algorithm; backtracking; Niklaus Wirth; Pascal programming language; longest uncrossed knight's path; point; Wikimedia Commons; knight's tour; sequence A165134 of the On-Line Encyclopedia of Integer Sequences; artificial neural network; tour de force; ant colony optimization; ant; colony; food; pheromone; evaporation; University of Nottingham.
Latest Books by Dev Gualtieri
Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!
Blog Article Directory on a Single Page
- The Wisdom of Composite Crowds - April 27, 2017
- J. Robert Oppenheimer and Black Holes - April 24, 2017
- Modeling Leaf Mass - April 20, 2017
- Easter, Chicks and Eggs - April 13, 2017
- You, Robot - April 10, 2017
- Collisions - April 6, 2017
- Eugene Garfield (1925-2017) - April 3, 2017
- Old Fossils - March 30, 2017
- Levitation - March 27, 2017
- Soybean Graphene - March 23, 2017
- Income Inequality and Geometrical Frustration - March 20, 2017
- Wireless Power - March 16, 2017
- Trilobite Sex - March 13, 2017
- Freezing, Outside-In - March 9, 2017
- Ammonia Synthesis - March 6, 2017
- High Altitude Radiation - March 2, 2017
- C.N. Yang - February 27, 2017
- VOC Detection with Nanocrystals - February 23, 2017
- Molecular Fountains - February 20, 2017
- Jet Lag - February 16, 2017
- Highly Flexible Conductors - February 13, 2017
- Graphene Friction - February 9, 2017
- Dynamic Range - February 6, 2017
- Robert Boyle's To-Do List for Science - February 2, 2017
- Nanowire Ink - January 30, 2017
- Random Triangles - January 26, 2017
- Torricelli's law - January 23, 2017
- Magnetic Memory - January 19, 2017
- Graphene Putty - January 16, 2017
- Seahorse Genome - January 12, 2017
- Infinite c - January 9, 2017
- 150 Years of Transatlantic Telegraphy - January 5, 2017
- Cold Work on the Nanoscale - January 2, 2017
- Holidays 2016 - December 22, 2016
- Ballistics - December 19, 2016
- Salted Frogs - December 15, 2016
- Negative Thermal Expansion - December 12, 2016
- Verbal Cues and Stereotypes - December 8, 2016
- Capacitance Sensing - December 5, 2016
- Gallium Nitride Tribology - December 1, 2016
- Lunar Origin - November 27, 2016
- Pumpkin Propagation - November 24, 2016
- Math Anxiety - November 21, 2016
- Borophene - November 17, 2016
- Forced Innovation - November 14, 2016
- Combating Glare - November 10, 2016
- Solar Tilt and Planet Nine - November 7, 2016
- The Proton Size Problem - November 3, 2016
Deep Archive 2006-2008