The knight's tour
This article is part of Five of Euler's best. Click here to read the other four problems featured in this series, which is based on a talk given by the mathematician Günter M. Ziegler at the European Congress of Mathematics 2016.
The second question in this series is also about finding a path, but this time on a chess board. To phrase it in Euler's own words,
"I found myself one day in a company where, on the occasion of a game of chess, someone proposed this question: To move with a knight through all the squares of a chess board, without ever moving two times to the same square, and beginning with a given square."
A knight's tour as it appears in Euler's paper. Euler just numbered the squares in the order in which they're traversed, but we have traced the tour in blue. From paper E309 on the Euler archive.
Euler called this a "curious problem that does not submit to any kind of analysis". But analyse it he did, and he was the first person to do so methodically. He came up with a method for constructing knight's tours which, as he claimed, allows you to discover as many tours as you like. Because "although their number isn't infinite, it is so great that we will never exhaust it."
These statements are contradictory by modern mathematical standards. If you can discover as many tours as you like, then surely their number is infinite. But we know what Euler means: the number of tours is so huge, it might as well be infinite. To really try and count them you need to use a computer. In 1996 the mathematicians Martin Löbbing and Ingo Wegener did just this. They counted only those tours for which the end square is just one knight's hop away from the starting square, that is, tours that can be turned into a loop. They claimed that there were 33,439,123,484,294 of them (in fact, their aim wasn't so much to count the number of tours, but to demonstrate the usefulness of a particular enumeration method).
It was soon pointed out to them, however, that the result can't be right: the number of knight's tours must be divisible by 4 which 33,439,123,484,294 isn't. The apparently correct result is 13,267,364,410,532. That's more than the diameter of the solar system measured in kilometres. As for knight's tours that can't be turned into a loop, a number computed by Alexander Chernov in 2014 is 19,591,828,170,979,904. People don't seem to be entirely certain as to whether it's correct though.
If you read French then you can read Euler's original article on the Euler archive (article E309). For an easier ride, read about Euler's methods for constructing knight's tours in this MAA online article. There's more about variations of the classical knight's tour problem on the MacTutor History of Mathematics archive.
About this article
This article is part of Five of Euler's best. Click here to read the other four problems featured in this series, which is based on a talk given by the mathematician Günter M. Ziegler at the European Congress of Mathematics 2016.
Günter M. Ziegler is professor of Mathematics at Freie Universität Berlin, where he also directs the Mathematics Media Office of the German Mathematical Society DMV. His books include Proofs from THE BOOK (with Martin Aigner) and Do I count? Stories from Mathematics..
Marianne Freiberger is Editor of Plus. She really enjoyed Ziegler's talk about Euler at the European Congress of Mathematics in Berlin in July 2016, on which this article is based.