| The Games and Puzzles Journal — Issue 21, September-December 2001 |
I have started to number the sections from the start of the January issue so that they can easily be referred back to in future.
For this month's issue I've been looking back over some correspondence that I had about knight's tours with Professor Donald E. Knuth in the early 1990s.
In a letter dated 29th November 1992 he wrote: "I amused myself yesterday making a font for typesetting knight's tours." ... "One can prove without difficulty that the path of a knight's tour has only simple intersections (no three lines concurrent). Hence the tour can always be drawn with alternating over-and-under relations ... It would be nice if I could make the paths wider, so that the Celtic-knot nature of the designs would be immediately obvious. But sometimes the intersection points get very close together, so I'd get in trouble with wider paths."
An enclosed sheet included this diagram of the tour due to Al-Adli of circa 850AD, the earliest surviving closed knight's tour. (Click on the gif image to see a clearer jpg. Actually the print by Prof. Knuth is clearer than my scanned version.)
I had considered the problem of intersections of knight moves back in Chessics 1984 (issue 19 p.26) and sent Prof. Knuth my results (since published in GPJ 17 p.315) proving that a knight-move triangle of size k has area (k^2)/120. In particular the smallest triangle formed by three knight moves encloses an area 1/120 of the area of a cell of the board; in diagrams of this type such triangles are reduced almost to a point, as for example the three moves b8-c6, b6-d7, b5-c7.
Prof. Knuth's letter of 29th November 1992 continued: "The construction raises an interesting question: Is it possible to construct a knight's tour having no three lines nearly concurrent? By this I mean there should be no instances of three moves like [first diagram below, showing moves a1-c2, b1-c3, b2-d1] or rotations/reflections thereof. Another related question is to seek the minimum number of crossings."
In my reply of 4th December 1992 I wrote: "Looking at the diagrams in my files, in date order, I noticed that Euler's 6×6 tour meets your requirements. This happens to be the only one of the 22 symmetric 6×6 tours that has this property, so perhaps old Euler knew more than he let on! I will check the rest of the 6×6 tours for this feature in due course." In my next letter of 26 December I could say: "... on the 6×6 board there is, surprisingly, besides the symmetric solution by Euler, only one other closed tour with this property, as shown below. Fortunately I did not have to search through all the 1223 [asymmetric closed] tours, but simply set out directly to construct tours of this type, a process that required the examination of only 17 diagrams. The process also turned up the three reentrant tours shown." I believe others of this type are possible. "Note that if the end points of these are joined a type 1 triangle is formed." It was in his next letter of 5 January 1993 that Prof. Knuth used the term Celtic Tours for tours without type 1 triangles.
Back to my 4th Dec letter: "In view of this, one would expect it to be easy to find an 8×8 example, but a rapid search did not reveal any, and I had to construct one myself" [first 8×8 diagram below]. "It seems that the type 1 triangle tends to appear in a tour unless you take particular care to exclude it. For example it occurs in all 8×8 closed tours with a2-c3-b1 in the corner." This statement is not quite correct: for "closed" substitute "symmetric". The second diagram below (from my 26th Dec letter) shows an asymmetric tour with a2-c3-b1 in the corner.
"I have begun a search for all symmetric 8×8 tours without type 1 triangle, and give three examples" [as below] "from more than 50 I have so far found. Another appears as diagram 8 on the New Year's Greeting card enclosed." [the last diagram below] "I found this example among my notes ... on "simple linking" ... Incidentally this example may be a candidate for the solution of your related problem of a tour with the minimum number of self-intersections; it has 76 if my count is correct. I have no intention of counting all the intersections, in all the tours I construct, to test which has the fewest; this is definitely a task for your computers!"
In his letter of 5th January Prof. Knuth wrote; "On Christmas Eve I finished my program that enumerates celtic knight's tours. When tours are counted without removing isomorphisms, there are ... 12 on the 6×6" thus confirming the result above - 4 from the Euler symmetric and 8 from the asymmetric. He also counted tours on various oblong boards and concluded: "I doubt if I will be able to tackle the 8×8 until computers get faster, although I do know how to make my program almost 8 times faster on square boards. It is, however, possible to enumerate symmetrical 8×8s. The total number of knight's tours with 180° symmetry on the standard chess board is 4×608233, and 4×2321 of these are Celtic." In view of this information I did not choose to carry my hand-count of 8×8 celtic tours further!
My letter of 26th December continued: "I have also begun a search for all doubly symmetric 10×10 tours without type 1 triangles, and give three examples of these:" Two are reproduced here, the third is in GPJ #16 1999 p.287.
In his letter of 5th January 1993 Prof. Knuth commented: "I suppose it's possible to prove that celtic tours are impossible on a 3×n board. At least, I know there are none on the 3×20 and 3×22."
On 14 January I was able to answer: "Closed celtic tours on a 3×n board are impossible - but open celtic tours are possible on the 3×8 and probably on larger boards." I gave the following proof: "Graphically this is reasonably obvious, but written out in full the argument is somewhat tedious: (1) The board must be at least 3×4 since no tours are possible on smaller boards. If no ends occur in the first two files then diagram (a) is forced, since there is no choice of moves through a1, a2, a3, b2. In this diagram we cannot connect b1 and b3 to d2 since a short circuit is formed. And we cannot have b1-c3 or b3-c1 since a type 1 triangle is formed. This also proves the impossibility of a celtic closed tour. (2) If both ends are in the first and second files then there are no ends in the two files at the other end of the board. So rotating the board 180°, the above argument applies. We are left with the case of one end in the first two files and one in the last two. (3) An end cannot be in the middle of the first (or last) column, by the same argument as above applied to diagram (b). The end cannot be in the middle of the second (or next to last) file because moves are forced as in diagram (c) and here to avoid a type 1 triangle we must take b2-d3 and b3-d2 (or b2-d1 and b1-d2). But now b1-d2 (or b3-d2) forms a short circuit and b1-c3 (or b3-c1) forms a type 1 triangle. (4) An end cannot be in a corner since in diagram (d), taking a3 as the corner, the moves through b1 and b3 must be a3-b1-d2 and b3-d2 to avoid forming type 1 triangles. Now in diagram (e) the tour must continue either c2-e3 or c2-e1, but both of these prevent c3-d1 abd c1-d3 (since both form a type 1 triangle), but we cannot join c3-e2 and c1-e2 (forming a short circuit). (5) This leaves us with the ends at the top or bottom of the second and next to last files. The forced moves in the first two files give diagram (f). To continue the tour from d2 we must add two more files. To provide a path through f2 we must add two further files. This leads to the 3×8 board and we find the three solutions illustrated, two of which are symmetric.
In a letter of 16th January I added further: "Celtic tours on 3×n boards. There are no such on boards of lengths 9 to 15. The proofs follow the same lines as for the smaller boards, the impossibility being proved by the formation of either short circuits, type 1 triangles, or dead ends. The 3×16 board admits 10 (geometrically distinct) tours, 4 of which are symmetric. The tours have ... three central formations [shown above], the end pieces can be inserted to end at the top or bottom of the second and penultimate files. This gives four geometrically distinct solutions in the ab case, but in the aa and bb cases, the solutions with both ends in the top rank and with both ends in the bottom rank are not distinct but are 180° rotations of each other.
In my letter of 4th Dec 92 I concluded: "The argument given in Chessics 19 p.26 (which can be extended to any size of even rectangular board) to prove that every closed knight's tour has at least one move that is intersected four times, also shows that triangles of type 2 must occur." At the end of his letter of 5th January 93 Prof. Knuth, after constructing some random celtic tours on various boards, queried: "Is it true that no move is intersected by more than four other moves in a celtic tour?" The answer to this is No, since five intersections are possible, as proved by the following argument in my letter of 14 January 93: "Take a knight's move, not near the board edges, and number the nine moves that cross it 1 to 9 as shown in diagram (a). Then, in a celtic tour, the pairs of moves {1,6}, {1,7}, {2,7}, {3,8}, {3,9}, {4,9} cannot be used. Also in any tour the triples {1,2,3}, {7,8,9} cannot be used, since no more than two moves can meet on any square. It follows that the only allowable quintuplets of these moves are the seven: {1,2,4,5,8}, {1,2,5,8,9}, {2,3,4,5,6}, {2,4,5,6,8}, {2,5,6,8,9}, {3,4,5,6,7}, {4,5,6,7,8}. Geometrically there are five cases ... three symmetrical and two asymmetrical (corresponding to pairs of quintuplets). There are no allowable sextuplets. I have constructed a tour 8×9 showing a five-fold intersection (with central diametral symmetry) ..." as in diagram below. In my next letter I gave asymmetric 8×8 tours showing the five ways in which one move can be intersected five times.
The last idea in my letter of 26 Dec 92 was: "With regard to the presentation of knight's tour diagrams, it has occurred to me, while filling in the triangular areas in some diagrams, that another way of presenting a tour is by colouring the areas between the knight's moves alternately black and white. Here are two examples:"
"This method of presentation suggests another problem: to minimize the black area. I leave this also for computer analysis."