Tikalon Blog by Dev Gualtieri

Tikalon Header

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 .

Wood inlaid chessboard

Heirloom wood inlaid chess board.

As I remember, the white squares are birch , and the dark squares are walnut .

(Photo by the author.)

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 .[1] 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.

A solution of the eight queens puzzle

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 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[2] 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.[3]

Uncrossed knight's path on an 8x8 chessboard

Uncrossed knight's path on an 8x8 chessboard.

(Modified version of a Wikimedia Commons image .)

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 .

N Tours

1 1

2 0

3 0

4 0

5 1,728

6 6,637,920

7 165,575,218,320

8 (unknown)

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.

A knight's tour on a 24x24 board.

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 .)

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.[4] There are several good references about the knight's tour at the end of this article.[6-9]

References: