Knuth: Knight's Tours Writ Large

Knight's Tours Writ Large

I was overjoyed when Case Western Reserve University asked me last year to design a series of artworks based on knight's tours, which would be permanently displayed on the walls of Olin Hall, because it gave me a chance to fulfill a lifelong dream. And now I'm even happier, because the dream has come true, with the help of many other people!

My designs strove to satisfy several goals simultaneously: (1) Visual appeal, to enhance the experience of being in the building. (2) Technical appeal, to be consistent with world-class science in a world-class university. (3) Variety, yet conforming to a unified theme. (4) Educational appeal, so that a professor could, in principle, hold one or more class sessions next to the artwork, using it to teach important concepts of mathematics and computer science. (5) Fun.

A knight's tour is a path that can be taken by the chess piece called a “knight,” on a grid like a chessboard. The cells of that board are like individual tiles, and the knight leaves a trail as it jumps from tile to tile in knightlike fashion — two steps in one dimension, and one step in the other dimension. The general idea is usually to make the path as long as possible without returning to the same cell twice, unless that cell was the starting point. All but one of the tours in this exhibit are, in fact, “closed”, in the sense that they do return to the starting point and make a complete cycle.

Knight's tours are one of humankind's earliest known combinatorial patterns. They originated in Kashmir and Persia, about 1200 years ago, and they've had a substantial, continuous history ever since then — first in Asia, then eventually in Europe, and finally in the Americas, Africa, and Australia.

I've often seen appealing examples of knight's tours in books. But never before had I seen one at “real life size”, with tiles that are 2.5 inches square, as they are in this exhibit. Large enough to trace the path easily with your fingers. (But please be careful not to damage it, of course.)

Level 3: Long and skinny tours

On the entrance level to Olin Hall, which happens to be Level 3, the emphasis is on closed tours that visit every cell and are exactly three cells wide. Such “3×n cycles” are especially interesting because, for more than 100 years, they were thought to be impossible!

It's a curious story. Leonhard Euler, who was one of the greatest mathematicians of all time, contributed a widely read essay about knight's tours to the Berlin Academy of Sciences in 1758. In §43, near the end, he made one of comparatively few mistakes in all of his published works: He stated, without proof, that m×n cycles do not exist unless both m and n are 5 or more, and mn is even. And since Euler was Euler, everybody believed him … until Ernest Bergholt shocked the world by constructing a 3×10 cycle in 1917.

By now it is known that 3×n cycles are by no means rare, when n is a large even number. Indeed, the number of 3×100 cycles turns out to be exactly 4,861,943,174,181,138,724,903,568,742,746,024,250,554,974,208, according to an instructive theory that's presented in Chapter 42 of my book Selected Papers on Fun and Games.

An elegant “frieze” pattern appears just above the elevator on Level 3, and I imagine that most people will think of it as a fairly ordinary design, sort of like fancy grillwork. Then one day, however, while waiting for the elevator, they might notice that there's more to it; indeed, it happens to be a 3×74 cycle! A knight that begins in the upper left corner and does a little dance until it gets moving right, will continue rightward until it almost reaches the far right end, having covered about 1/4 of the cells. Then it will come back almost all the way to the left, after which it will zigzag to the right again, before finally returning to its starting point after 3×74=222 steps.

(If you don't believe me, take a look at the middle panel, just to the left or right of the elevator doors. That cycle uses the same idea; but it's 3×26 instead of 3×74. A 3×2 motif, called ‘012-213’ in the theory, can be inserted any even number of times between the two special 3×7 configurations at either end, in order to construct 3×(4n+14) cycles for all nonnegative n.)

The leftmost vertical panel is a 3×28 cycle. This one has a completely different texture, in which the knight travels at a more leisurely pace. Starting at the top, it will fill in about half of the cells before it gets to the bottom; then it will wander back again to the top. We obtain 3×(4n+12) cycles, for all nonnegative n, by inserting n copies of its ‘333-110-201-022’ motif.

And the vertical panel nearest the elevator is dramatically different again. According to this one, with 2n copies of the motif ‘011-121-131-202’, a knight will fill all cells of a 3×(8n+12) cycle. It marches at high speed from top to bottom, filling about 1/6 of the cells; then it comes back to the top, filling in another 1/3. Another 1/3 are covered as it moves downward again; and the final 1/6 are just in the right places for a quick trip back to the top. The fact that it works is almost a miracle.

Even more miraculous are the friezes that appear above the elevator doors on levels 4 and 8. One can verify that, on level 4, 2n copies of the motif ‘011-223-110-212-131-222’ will give a 3×(12n+14) cycle. Finally, the amazing motif on level 8, ‘133-122-011-023-131-110-231-223-001-101’ leads to 3×(10n+20) cycles that are totally bizarre — yet it's only one of a vast number of possibilities. Imagine walking through a labyrinth that follows this pattern!

Level 4: Noncrossing cycles

The scene changes as we move up one floor: Now we try to find the longest possible knight cycles whose paths never cross over or under themselves. It's impossible to visit all of the cells, under this restriction; yet a clever knight can reach all but a few.

The task of finding an absolutely longest noncrossing knight cycle in a given board is extremely challenging. Indeed, that problem became a well known combinatorial benchmark in the 1960s. The great British puzzlist Thomas Rayner Dawson and his Romanian friend Wolfgang Pauli had found noncrossing cycles of length 32 on an ordinary 8×8 chessboard, already in 1931; but nobody knew whether or not a longer cycle was possible. Finally in 1968, after more than 100 hours of computation on what was at the time the world's fastest computer, the optimality of Dawson's and Pauli's tours was rigorously verified.

The solution to even larger problems was, however, unthinkable until recently. New algorithms and data structures were needed. But now, thanks to ZDD technology, optimum solutions are known for all problems up to size 10×10; and they look rather like exotic lizards! You can see them next to the elevator on the fourth floor. for all cases 3×10, 4×10, … 10×10. (The full story is told in Chapter 40 of my book Selected Papers on Fun and Games.)

At the right of the 4th-floor elevator is another noncrossing pattern, this time based on 4×6 modules in which the knight is allowed to go “outside the box,” as long as it doesn't interfere with any of the neighboring lizard-like paths. In this way it's possible to achieve a “toroidal” density of 14/24.

The density of noncrossing tours on n×n boards approaches 100% as n approaches infinity, thanks to constructions by an enthusiast named Robin Merson. (Merson sketched his results in somewhat cryptic letters written to George Jelliss, who published the ideas in 1999. Jelliss is the author of Knight's Tour Notes, a comprehensive collection of almost everything that is currently known about the knight's tours in general.)

Merson's stunning constructions achieve cycles of length n²-7n+22 on n×n boards for all n greater than 31, and the tours are sometimes even longer. For example, his remarkable cycle for the case n=58 can be seen on the wall just around the corner from the 4th-level elevator; it covers 2982 of the 58²=3364 cells! (The underlying recursive scheme is rather complicated; therefore such large examples of Merson's tours have never been seen before, and they are appearing in this exhibit for the first time.)

Nobody knows exactly how many cells can be covered by the longest possible noncrossing cycle on this board. A few tweaks to the pattern may perhaps yield a modest improvement, but a tour of length 3000 would be very surprising indeed.

(Incidentally, the tiles in these noncrossing cycles are 1.25 inches wide — only half as big as the tiles on level 3. Otherwise the patterns would not fit.)

Level 8: Celtic Tours and Frames

Look closely at the strands of a knight's tour and you'll see that they interlace nicely: Whenever paths cross, each of them strictly alternates between the “high road” and the “low road,” always going over/under/over/under/…, as in a Celtic knot. However, there's a problem: Almost all knight's tours have tight spots where three paths nearly coincide. Such tours can be drawn with proper interlacing only if the paths are rather narrow.

A closed tour is called Celtic if it doesn't have any such tight spots. Connoisseurs prefer Celtic tours, because they can be drawn with wider paths, whose crossings are more beautiful.

But Celtic tours are rare. In fact, the total number of closed knight's tours on an ordinary chessboard is 1,658,420,855,433, and only 18,941,491 of them are Celtic. That's roughly one in every 90,000.

Prominent examples of the Celtic property appear on a panel to the right of the elevator in level 8. (These tours have been drawn with thicker lines than those used in non-Celtic examples.) The 3×16 pattern at the upper left is actually an open knight's tour, because 3×n knight's cycles cannot be Celtic.

Below the 3×16 are three Celtic knight's cycles of size 10×5. They illustrate the three distinct kinds of symmetry that are possible on such boards: (a) Bergholt symmetry; (b) rotation symmetry; (a) reflection symmetry. In both cases (a) and (b) the tour looks the same when we rotate it 180° about the center. But in case (a), this rotation actually reverses the direction of the tour! And in case (c), the tour looks the same when we reflect it top-to-bottom.

The 6×6 cycle at the upper right has the honor of being the first Celtic tour ever published, because Leonhard Euler presented it on the next-to-last page of his famous essay cited above. Of course Euler didn't realize at the time that it was “Celtic;” but he did remark that the path is symmetric under 180° rotation. This tour also has another claim to fame, namely that it's the only 6×6 knight's cycle which 8 of the 36 moves are intersected by at least four other moves, while the remaining 28 are crossed by at most three others.

Just below Euler's example is an 8×8 Celtic tour that George Jelliss constructed while trying to find a knight's cycle with fewest self-intersections. This one has only 76; but it turns out not to be minimum: The current champion is a knight's tour with rotation symmetry that intersects itself only 70 times (and it is not Celtic!).

Below that is my candidate for the “most Celtic” 8×8 knight's tour, because it has fewest of the next-to-tightest triangles. Then comes a Celtic tour with the astonishing property that 60 of its 64 moves are part of a so-called ‘×’ intersection. And another, which uniquely has the maximum number of self-intersections, namely 108. (These examples are taken from Chapter 41 of my book Selected Papers on Fun and Games, where many other stories about Celticity can also be found.)

Finally, the 10×10 Celtic tour at the lower right exhibits fourfold symmtery under rotation by 90°.

The wall to the left of the elevator on level 8 completes the exhibit by illustrating a brand-new kind of knight's tour, not previously studied: A set of nested frames, each only three cells wide. Here we see a 7×7 frame inside a 31×31 frame inside a 55×55 frame. Each larger frame is obtained from the next-smaller one by inserting four of the modules that were used in the frieze on level 4! For several days I feared that such tours would be impossible; but suddenly everything clicked into place. Therefore I look forward to the day when occupants of Olin Hall carry out further research on knight's frames.

Final notes: This exhibit of knight's tours, together with the light box displays, is part of the Putnam Collection at Case Western Reserve University. The task of rendering the “over/under/over/under” behavior of a knight's tour with conventional software for computer graphics is extremely difficult, because those tools are based on layers that are stacked atop each other. (In a knight's tour, every layer wants to be on top, as well as on the bottom!) Therefore graphics wizardry galore was needed — and it was brilliantly supplied by Nick Sillies and Chandler Philpott.

Long live Geek Art!

Don Knuth's home page