Everything you wanted to know about knights

When people find out that I am both a mathematician (at least in a former life) and a chess player, they sometimes ask me if mathematics gives me an advantage in playing chess.

The answer, alas, is emphatically no. There is a relation between math ability and chess ability, but it is not causal. There are some really important confounding variables: abstract reasoning ability and the ability to concentrate for long periods of time. If you are able to formulate long chains of “if… then” statements, you will be more successful than average at both math and chess. Likewise, if you are able to concentrate on one thing for hours at a time, you will do well in both fields.

The actual intersection between mathematics and chess, though, is quite small. I think that one of the few things that has attracted both mathematicians and chess players is the ancient problem of the knight’s tour: Can you move a knight so that it visits all 64 squares on a chessboard without visiting any square more than once?

The chess player who is most identified with the knight’s tour is George Koltanowski. He had a phenomenal memory (for a long time he held the world record for playing the most simultaneous blindfold games). He would demonstrate his memory by asking spectators to write random pieces of information — a name, a phrase, a phone number — on each of the 64 squares. Then he would study the board briefly, put on a blindfold, and ask an audience member to call out a square to begin the knight’s tour with. He would then recite the rest of the knight’s tour, correctly identifying the name/phrase/number written on each square.

Of course Koltanowski was not just a showman, he was a serious player. Several times he won the championship of Belgium. In this country he was more of a chess promoter, though. He had the first national TV show on chess in the U.S., “Koltanowski on Chess.” My father and I used to watch this show when I was just getting interested in chess, back in 1970 or 1971 or so, and I think it had a bigger influence on me than Bobby Fischer’s triumphs, which were happening at the same time.

I didn’t know much about the history of the knight’s tour until I started reading about it on the Web this morning. George Jelliss keeps a really terrific page devoted to knight’s tours, and you can also find lots of other pages with similar information by doing a Google search. One of the things that surprised me most was the antiquity of the problem — the first reference to it dates back more than 1000 years, to about 840! Knight’s tours were around long before the rules of chess even reached their current form.

The most famous mathematician to work on the knight’s tour problem was Leonhard Euler, who is often considered one of the two or three greatest mathematicians ever. He first distinguished between open tours (where the knight begins and ends at different squares) and re-entrant tours (where it returns to its original square). He also looked at boards of different sizes, and tours with different kinds of symmetry. Here is one of my favorites:

Symmetric knights tour by Euler (1759)

I like this one because of the symmetry, the bold straight lines that go across the middle, and the two “duck heads” in the upper left and lower right!

In recent years knight’s tours have started to be of interest to computer scientists, in part because they are an example — the oldest example — of something called a Hamiltonian cycle. If you imagine joining a bunch of electrodes with wires, or thumbtacks with string, you are creating something that mathematicians call a “graph.” A Hamiltonian cycle in a graph is a path that passes through each vertex (electrode, thumbtack) once. To see the connection with the knight’s tour, imagine wiring up a chessboard so that every square is linked to every other square that is a knight’s move away. Then a Hamiltonian cycle for that graph is a re-entrant knight’s tour.

For general graphs, determining whether a Hamiltonian cycle exists at all is known to be a computationally hard problem. But of course, for the chessboard and the knight’s tour, we do know they exist. But another interesting question, which we can only hope to answer with the help of computers, is how many re-entrant knight’s tours there are. Surprisingly, nobody knew until just a few years ago. In 1996 two computer scientists published an answer (33 trillion and change) that was incorrect! I think that’s pretty embarrassing, especially because you could just look at the last two digits (94) and know that it’s incorrect because the number has to be a multiple of 4.

Another computer scientist named Brendan McKay computed the correct answer (13,267,364,410,532) in 1997. Interestingly, his work was never actually published in an academic journal, and Jolliss mentioned on his web page that to his knowledge it has never been independently confirmed.

Until now! A Finnish electrical engineer named Patric Östergård (can anybody tell me the correct pronunciation of his name?) has written a paper called “Counting Hamiltonian Cycles in Bipartite Graphs” which is actually going to be published in a real journal (Mathematics of Computation).

The funny thing is that the knight’s tour problem is mentioned only briefly at the end, and you wouldn’t know from the title that it’s there at all. His main focus is actually a different problem: counting Hamiltonian cycles on a 6-dimensional cube. This is understandable because that was an unsolved problem, and you get more attention from solving an unsolved problem than you do from one that has been solved once before. Also, high-dimensional cubes are an extremely familiar kind of graph to computer scientists (more familiar than the aforementioned graph of knight moves on a chessboard). Östergård derives a clever backtracking technique that lets him solve the cube problem (there are 35,838,213,722,570,883,870,720 Hamiltonian circuits on the 6-cube) and then says, by the way, we can count the number of knight’s tours the same way, and he confirms McKay’s count.

Hooray! I don’t know about you, but I’m going to sleep more soundly tonight.

One thing that surprises me a bit is that the number of Hamiltonian cycles is so vastly greater on the 6-cube than on the chessboard. Both of these graphs have the same number of vertices (64 squares on a chessboard, 64 corners of a 6-dimensional cube). You can say, well, the hypercube graph is better connected than the knight’s graph, because every vertex is connected to 6 others. But the average square on the knight’s graph is connected to 5.25 others, so there isn’t a huge difference. However, knights in the corners and sides have a lot fewer moves — 2, 3, or 4 — and I think that this must act as a bottleneck that dramatically reduces the number of Hamiltonian cycles. Just one more proof that “knights on the rim are dim”!

To conclude, let me mention one other kind of “knight’s tour” that I had never thought of before. (I learned this also from Jelliss’s page.) Suppose you start moving your knight and you keep going in a straight line for several moves. Then you turn and go in a different straight line for several moves. Then you turn and go in a third direction for several moves. You finish on the same square you started. What is the shape of the triangle you have made? What is the smallest board on which this triangular knight’s tour is possible?

The answer is illustrated below:

The triangle always has the shape of a 3-4-5 right triangle! This means that you have to make 3 knight moves in one direction, 4 in a direction at a right angle to it, and 5 in the third direction. Or you can make any multiple of these number (6, 8, 10, for instance). The smallest chessboard you can do it on is 9 by 11 (as shown above). That explains why you’ve never seen this pattern in an actual game:

Na1-c2-e3-g4-i5-k6-i7-g8-e9-d7-c5-b3-a1.

It reminds me, though, of a funny comment I saw recently. Recently, at the Wijk aan Zee tournament, Magnus Carlsen (White) defeated Hikaru Nakamura (Black) in a rather overwhelming fashion. Nakamura for some reason spent a huge amount of time advancing his pawn to h3 and his knight to g2, while Carlsen was dominating the rest of the board. Here is the final position:

Some of the kibitzers on chessgames.com were asking what purpose was served by Nakamura’s knight on g2 (aside from blocking the long diagonal so that White doesn’t have to worry about … Qxc6). One wit said, “Well, it does keep the king from moving to the h0 and i1 squares…”