In February 2003 a nine-year-old boy cause a minor sensation on German TV. It was on the show "Wetten dass..?", which translates approximately to "Want to bet..?" The format is that a series of candidates propose to be able to do impossible feats, live and in front of the camera. For instance uncork a bottle of wine using a corkscrew attached to the landing gear of a helicopter.

The boy on the show was Xaver Neuhäusler from the state of Bavaria, and the bet was that this young lad could complete a "knight's tour" of the chessboard, completely in his head, starting from any square on the board.

A "knight's tour" is a sequence of 64 knight moves executed in such a way that each square of the board is visited exactly once. Xaver was blindfolded and a starting square was called out to him. Without much ad the lad dictated a sequence of 64 squares that comprised a perfect knight tour.

The reaction to this feat in Germany was overwhelming. Newspapers were full of it, people discussed it on trains and busses, in offices and schools, and we received dozens of calls asking us to tell the story on our web site.

Well this is what we are doing. And it leads to a small dilemma. Should we not simply report the story, one that has produced such universal interest for a chess-related subject? Should we join the speculation that we might have encountered a future chess world champion, or at least been witness to an prodigious feat of pure genius? Or should one look deeper? Even if it detracts from a moment of glory for a nine-year-old child? Will anyone cheer if we shoot down a legend that has moved a nation? Our decision can be seen at the end of the article. But first let us take a look at the mechanics of the knight's tour.

Earliest examples

A "Knight's Tour" of the chessboard, as originally proposed, is a sequence of moves by a knight such that each square of the board is visited exactly once. The questions raised were: can the knight indeed make such a tour; and if it can, how many different knight tours are there? A comprehensive history of the knight's tour is to be found on George Jelliss' 'Knight's Tour Notes', from which the following historical examples are taken.

The first question was answered in a ninth century Arabic manuscript by Abu Zakariya Yahya ben Ibrahim al-Hakim. The author give two tours, one by Ali C. Mani, an otherwise unknown chess player, and the other by al-Adli ar-Rumi, who flourished around 840 and is known to have written a book on Shatranj (the form of chess then popular).

A "closed tour" is one in which the square at the end of a knight's tour is a knight move away from the first square, as in the second example above. The master of Shatranj as-Suli, who based his works on those of al-Adli (which he criticised), published the following two closed tours:

The first example shows perfect axial symmetry on the left halfboard, the second is composed of two quasi-symmetrical half-board tours.

The first comprehensive mathematical analysis of the knight's tour was presented by the eighteenth century mathematician Leonhard Euler (1707–1783) to the Academy of Sciences at Berlin in 1759. The Academy had proposed a prize of 4000 francs for the best memoir on the problem, but that the prize was never awarded, probably since Euler was at that time Director of Mathematics at the Berlin Academy and presumably ineligible.

If you want to learn a closed knight's tour by heart pick one of the above by Leonhard Euler. Learning a closed tour had the important advantage of allowing you to start from any square on the board and complete the tour from there.

How many knight's tours are there?

The number of knight's tours that are possible on a normal chessboard is surprisingly big. Actually it is so big that simple counting of tours is out of reach even for the fast computers of today. The problem has to be tackled in other ways. In 1995 Martin Löbbing and Ingo Wegener proclaimed that "the number of knight's tours equals 33,439,123,484,294". They obtained this result by running 20 Sun workstations for four months.

In 1997 Brendan McKay used another method (splitting the board into two halves) and got the result 13,267,364,410,532. To give you an idea of the magnitude of these numbers, a computer searching and finding tours at a speed of one million tours per minute would need more than 25 years to calculate the number of tours given by McKay.

The Magic Knight's Tour

If you really want to show off you should not just learn one of the closed tours given above, you should go for a "magic knight's tour".

In a magic knight's tour the steps, if numbered, make a magic square. This is an arrangement of the numbers from 1 to n in a matrix, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is the same.

Full magic knight's tours are not possible on n x n boards for odd numbers, and are believed to be impossible for the 8x8 chessboard. The "most magic'' knight tour known on the board is the Semimagic Square illustrated in the above left figure having main diagonal sums of 348 and 168. Combining two half-knights' tours one above the other as in the above right figure does, however, give a full Magic Square, in which the diagonals add up to 260 – but the steps 32 and 33 are not linked by a knight's jump.

All known magic knight's tours of the normal chessboard are listed here. There are 131 different geometrical forms.

Practising the knight's tour

In the 19th century H. C. Warnsdorff presented a practical method of constructing knight's tours ("Des Rösselsprungs einfachste und allgemeinste Lösung", Schmalkalden, 1823). The aim is simply to avoid creating dead ends – squares from which the knight cannot get further without getting to an already visited square. For that reason the possible squares to be chosen next are examined before every move. One counts the number of free new choices – entrances – every one of them has, and then moves to the square with the lowest number of new choices.

If you want to try out this method you can do so on this excellent page by Gunno Törnberg. It contains a Java applet which demonstrates the efficiency of Warnsdorff's rule. When you click a square all legal jumps are displayed and the number of free entrances to each of the squares is displayed. You simply choose the lowest value, or one of them if there are a number of equal choices.

Here's a simple applet that will allow you to practice the knight's tour in general. On the same site there is also an applet that will solve the tour from any start square.

The above is a delightful little program (28 KB exe) that you can use to practise the knight's tour.

Another larger Delphi program (executable 434 KB) allows you to practise and solve the problem, including closed tours. In case you become seriously interested the author has supplied the full source on his knight's tour page.

How difficult is the knight's tour?

Let us return to our nine-year-old boy on the TV show. As mentioned in the introduction to this article Xaver Neuhäusler was able to complete a knight's tour blindfolded and from a starting square given to him by the host of the show. Exactly how prodigious was this feat? How deeply must we be impressed?

In order to test the effort involved in learning a knight's tour we asked a guest who was visiting over the weekend of the TV show whether she could do it. Elizabeth Pähtz is the current women's under 18 world champion, and she was in Hamburg to play in the first German Internet championship. "I used to be able to do the knight's tour when I was a child," Elli told us, "but now I have forgotten how it went." So we asked her to try to learn it again.

Using a knight's tour of her choice Elli started learning it by heart.

It's not as easy as it looks!

With some effort Elli was able to master a tour in 40 minutes. It must be mentioned that the poor thing was in some pain, having had two wisdom teeth extracted a few day previously. So there was some problem with motivation.

How about someone who is not a very strong chess player. Thomas Friedel, 20, gave up competitive chess when he was 14 and is now a full-blood programmer. How would an algorithmic mind fare with the task?

After 12 minutes studying the diagram Tommy announced that he could do it. And indeed, with Elli checking the moves he completed a knight's tour flawlessly on an empty chessboard.

With some effort Tommy was able to dictate the squares without looking at the chessboard. He could only do the tour starting from one starting square, but wagered that with half an hour of practice he could pick it up at any point in the closed circuit. Maybe an hour to do it reliably, dictating the squares with a blindfold covering his eyes.

Sorry, Xaver, for demystifying your great performance. And sorry everybody for being such spoilsports. We can only close by giving you the following advice: pick a knight's tour above, invest an hour or two learning it, use one of the gorgeous little programs to practise it and be prepared for your moment of glory. If you don't make it to a big TV show it at least makes for a great party trick.

Frederic Friedel

Addendum

There are two points I would like to add, both of which came up after the above article was published. The first is that a Hamburg programmer, Tim Spitzer, actually taped the "Wetten dass..?" show and replayed it in stop motion. He retraced the closed knight tour that Xaver Neuhäusler had used. Here it is for the record:

The knight's tours of George Koltanowski

The second point was brought to my attention by an old friend whom I hadn't seen in years. After reading my article he wrote to me reminding me of the most remarkable knight's tour we – both of us together – had ever witnessed. I shamefully admit that it had completely slipped my mind while I was dealing with the young German TV star.

It happened many years ago, at a US chess club, where a blindfold master was giving a demonstration of his extraordinary abilities. At one stage he asked for a helper from the audience, and I was pushed and poked by my friends to take the stage. There the master gave me block of sticky notes and asked me to write down names, words and numbers dictated at random by the audience. Each was stuck on a big demo chessboard, starting from the square a8 and working sequentially to h1.

The audience call out a variety of words: names of cities, family members, phone numbers, abstract expressions. It went something like: Dayton, Margaret-Lee Farrow, pride before a fall, 212-783-4529, my dad's dog Skippy. While this was going on the master sat on his chair, listening to the audience, chatting with them. He was completely relaxed and not making any visible effort to memorise the notes.

After all the squares had been covered the master was blindfolded. He then asked someone in the audience to name a square on the chessboard. Starting from that square he started repeating words and numbers, while I removed the corresponding sticky notes from the demo board. The order of the words resulted in a perfect knight's tour. I believe he got one or two words slightly wrong, on the lines of Margaret-Mae Farrow instead of Margaret-Lee. All the numbers were perfect.

Now that is a truly remarkable feat. We were all deeply impressed, not the least because the master was approaching ninety years in age! He was George Koltanowski, one of the greatest mental acrobats the world has ever seen.

George Koltanowski, 1903-2000, copyright (C) San Francisco Chronicle 2000

George Koltanowski was born in Antwerp on Sept. 17, 1903. He developed his prodigious memory skills by studying memory games while he was very ill as a child and confined to bed for a couple of years. When he was 14 he started playing chess, and at the age of 21 when he played and drew Siegbert Tarrasch at the 1924 Meran tournament. In the early thirties he was the top Belgian player, beating Akiba Rubinstein in Antwerp 1931 and drawing Alekhine at Hastings 1936/37. He was awarded the title of IM in 1950 and in 1988 he was given an honorary GM title by FIDE.

Koltanowsky held a number of records in another area of chess. For centuries, the greatest masters in the world tested their mettle by playing blindfolded. It was long believed that three blindfolded games at once marked the limit of human capacity. Then, in 1933, Alexander Alekhine successfully played 32 simultaneous blindfolded games. Later, other grandmasters left Alekhine's record in the dust. Koltanowski set the current record, playing 56 blindfolded games San Francisco in 1960. He played the games sequentially at 10 seconds a move in 9 hours, scoring +50 =6. He also gave huge simultaneous displays with sight of the board, playing 271 games in 1949 and 110 in 1955. (Some of this is described in an article entitled "The Einstein Factor", a very readable article which explains in general terms why everyone should play chess).

When the Nazis overran Belgium during World War II, several of his family members perished in the Holocaust. Koltanowski was on a chess tour of Central America and was allowed to immigrate to the United States, mainly because a chess-playing consul in Cuba had been amazed by one of his demonstrations. He started writing a column for the San Francisco Chronicle. He had completed over 19,000 instalments when he died of complications resulting from congestive heart failure in February 2000, at the age of 96.

A full obituary is still available in the archives of the San Francisco Chronicle: Grandmaster Of Chess, George Koltanowski.

Frederic Friedel