Closed tours have been completely enumerated only on boards up to 12 cells, and even less work has been done on open tours which allow more possibilities. Results are gathered here for tours on these boards as far as they are known. The tours are classified according to the types of symmetry they show, beginning with symmetries of higher degree and ending with asymmetric examples.
All the tours have been redrawn in an improved style, the board being in 25% grey shade to contrast with the tour in black. The board edges (including hole outlines) use a wider line for emphasis. Since different boards often look similar at first glance diagrams of tours on the same shape of board are shown joined by a common base line, for greater clarity.
The diagrams are arranged according to the size of the containing rectangle, oriented with the longer side (if any) horizontal. Shaped boards precede holey boards, and multiply toured boards come before those with single tours. Within this scheme the boards are generally arranged according to the binary number method, by which the cut away cells count as 0s and the board cells count as 1s, and the board is oriented so as to give the smallest number. This helps to ensure that the same board shape is not counted twice in different orientations.
In a previous version of this study many of the boards were shown in reduced size, leaving the reader to draw the tours, but now all the tours are illustrated. In the process of drawing these a few errors in the previous counts were noticed. So an independent check may be advisable, if anyone is willing to take on the task.
The smallest knight-tourable boards are the two 7-cell boards shown below, each of which is tourable by both wazir and knight uniquely. The tours have the same symmetry as the boards, namely direct binary symmetry, lateral or diagonal. The U-shaped case appeared in the earliest Arabian chess manuscripts (al-'Adli, c.840) in the form of a puzzle where you are to place seven pawns round three edges of the 3×3 board, leaving only the top square vacant, each new pawn being placed at a knight's move from the preceding one (Murray 1913 p.337). The trick is to start at a knight's move from the vacant cell.
The mediaeval manuscripts also contain the puzzle of the four knights, often attributed to the later writer Guarini (1512), where white and black knights placed in the corners of the 3×3 board are to be interchanged. The knights go in procession round the star-shaped closed tour of the eight edge squares. The 3×3 closed tour is the first example of a tour with octonary symmetry.
There are 10 boards of 8 cells (octominoes) that are knight-tourable, with open tours.
Only the centreless 3×3 board admits a reentrant or closed tour. Within the 3×4 frame there are three shaped boards each with a single open tour, and two holey boards, each with two open tours. In the 3×5 frame there is one shaped board that can be toured in two ways. In the 4×4 frame there are two shaped boards each with one tour. In the 4×5 frame there is one tourable board with one tour, this is centrosymmetric.
The collages below show the open tours of 8-cell boards joined to form a single open tour. The first, excluding the 3×3 case, fits them within an 11×11 area, the second, including the 3×3 case, takes a 10×13 board.
The latest check (17 July 2013) on my enumeration of the 9-cell tours finds 56 tourable boards with 93 tours. Here are diagrams of the 10 symmetric tours (2 oblique, 8 direct). One in the 3×4 frame, axial. Four within the 3×5 frame, two oblique, two direct. Two holey boards within the 4×4 frame, each with two tours, with diagonal axis (they also have asymmetric tours). Finally one within the 5×5 frame also with diagonal axis.
The two boards within the 4×4 frame above also each have two asymmetric tours, shown below. There are also two other symmetric boards, 3×4 and 3×5, that each have three asymmetric tours, but none symmetric:
Here are drawings of the tourable asymmetric boards within the 3×4 and 3×5 frames.
Here are diagrams of the tourable asymmetric boards within the 4×4 frame. There is one board that can be toured in 6 ways. Besides the two symmetric boards shown above, another asymmetric board can also be toured in 4 ways. There is also one that tours in 3 ways. These are all of holey type.
There are seven in the 4×4 that tour in 2 ways, and the remaining 13 uniquely.
Within the 4×5 frame there is one board with three tours, and three with two tours and seven with single tours.
Four of the Vinje tours are symmetric, one each of the Bergholtian, Murraian, Sulian and Eulerian types. They are the first four in the top row. The Bergholtian tour, on an H-shaped board, has biaxial symmetry (also known as direct quaternary symmetry with lateral axes) and can be regarded as having Murraian symmetry about the axis with two cells and Sulian symmetry about the other axis.
T. W. Marlow (1995) has noted that there are six further 10-ominoes with holes that have closed knight tours, to be addded to Vinje's enumeration.
In the remarkable collage that follows, the shaped boards are fitted together within a 13×13 area to form a larger board, also without holes, in which the tours join together, with deletion of one move in each, to form a closed tour of the composite board. This is due to A. W. Baillie (Fairy Chess Review, problem 8531 November 1949 p.84 and June 1950 p.110).
On 10 cells there are 9 centro-symmetric open tours (using 6 shapes of board). Note that one of these tours is reentrant (derived from the 10-cell Bergholtian closed tour).
The asymmetric open tours have not been enumerated.
On boards of 11 cells there are 12 symmetric tours on 6 different boards. Within the 3×5 frame, two of the boards have biaxial symmetry, one having a single oblique tour, the other an oblique and a direct tour, the third board being oblique with two oblique tours. In the 4×4 frame there is one board, with diagonal axis and two holes, which has three tours. In the 5×5 frame there are two oblique boards each with two tours
Asymmetric tours have not been enumerated.
Enumeration of the 12-cell boards with closed knight tours has proved to be a considerably stiffer problem than for the 10-cell case.
I sent a summary of my results to Tom Marlow (27 October 1995) writing: "I think I have found all those up to 4×5 minimum containing rectangle, by a process of systematically removing squares from the rectangle, while ensuring the tourability of the remainder. However, for the larger sizes this method becomes inefficient. The 4×6 cases have mostly been found by 'folding out' a pair of moves from the 4×5 cases, and permuting the different shapes removed from the corners. The 5×5 cases, which I'm sure are very incomplete, resulted mostly from an examination of 12-cell tours that include a 2×3 rectangle. The 5×6 was 'folded out' from a 4×6 case. The particularly nice 6×6, where there seems to be the only one solution, was found by pure intuition before I started the systematic count. I haven't proved to my satisfaction that no cases with a dimension greater than 6 can occur, but this seems probable."
Mr Marlow responded (24 November 1995): "I am finding the polyomino tour problem quite addictive." He gave the 10-cell tours with holes as diagrammed above and diagrams of nineteen 12-cell boards (with 24 tours) not included in my list. He wrote: "My method has been to start from the opposite direction to you and look for 12 step knight loops within a rectangle. Then I see if the squares form a connected shape and reach to all edges. I found that I could easily adapt a magic tour computer programme to search for 12 step loops and then worked by hand. It seems clear that neither dimension can be greater than six."
We now give diagrams of all the symmetric closed tours of 12 cells. There are 17 on shaped boards. There are two 12-cell tours with quaternary symmetry, both of the type with two diagonal axes. The one within the 4×4 frame was found by Euler (1759), the one within the 6×6 is my own discovery.
There are nine other closed tours of 12 cells with centrosymmetry (i.e. 180 degree rotational symmetry). Of these, 3 are Eulerian (i.e. not passing through the centre) all within the 4×6 frame (two being on the same board shape). The other 6 are Bergholtian (i.e. passing through the centre), one within the 3×6 frame and five within the 4×5 frame. The remaining six have a single axis of symmetry with diagonal axis within a 5×5 frame.
There are 8 holey boards with symmetric tours (two with two symmetric tours). One tour in the 5×5 frame has centrosymmetry (Eulerian). One tour 4×5 has a lateral axis (with Murraian symmetry). The other 8 tours have a diagonal axis (Murraian), four 4×4 and four 5×5. The first 4×4 tour here was shown by Murray.
The first and last of these boards have a symmetric tour (see above) as well as the asymmetric one. The others have no symmetric tours, only the one asymmetric tour. We are counting 'geometrically distinct' tours here. Each of these tours can be seen in an alternative orientation by rotating the first two boards or reflecting the others. The two examples with lateral axis differ only in having a pair of moves, and the associated cell, folded up or down.
3×5, 3×6 and 4×4 cases.
4×5 case shaped. (a) asymmetric boards with multiple tours: 4 with 3 tours, 5 with 2 tours.
4×5 case shaped. (b) asymmetric boards with 1 tour and incomplete middle file. The sixth is the only example where one of the centre two cells is cut away.
4×5 case shaped. (c) asymmetric boards with 1 tour and complete middle file.
4×5 case holey. (a) asymmetric with multiple tours. We show one shape with four tours, then three shapes with two tours each.
4×5 case holey. (b) Asymmetric boards with a single tour.
4×6 case shaped. We begin with two shapes that have two tours each. The other ten have a single tour.
4×6 case with holes. 8 boards with 10 tours. Two boards with two tours. Six with single tours.
5×5 case shaped. (a) asymmetric boards with multiple tours: there is one with six tours, one with three,
and five with two.
5×5 case shaped. (b) asymmetric boards with single tour: 11 with no complete rank or file. The third one includes three two-move knight lines and also cycles round in one consistent direction.
5×5 case shaped. (c) asymmetric with single tour: 18 with complete rank but no complete file
5×5 case shaped. (d) asymmetric with single tour: 8 with complete rank and file.
5×5 case holey.. One example with four tours. Ten with single tour.
5×6 case. Three shaped boards. Two holey boards, one with two tours.
|Frame size||Boards||Tours||Symmetric||With hole|
Thus for example within the 4×5 frame there are 83 different 12-cell boards, of which 30 have a hole. Since some of these can be toured in two or more ways they give 103 tours, (36 on holey boards and thus 67 on shaped boards). There are 8 symmetric boards of this size but only 6 symmetric tours since two of the symmetric boards only have asymmetric tours (another has two tours, but only one of them is symmetric).
In the 5×5 frame there are 12 symmetric boards but one of these, the one with lateral axis of symmetry, has only an asymmetric tour, so there are only 11 symmetric tours. Again, one of the symmetric boards has two tours but only one of these is symmetric.
As noted at the start of this study, in course of doing the diagrams I found three errors. A 4×4 board claimed to have a tour only had a pseudotour. A 4×5 board marked as having 2 tours only had one. A 5×5 board marked as having one tour in fact had two. I hope the totals are now correct!
Proof (sketch): Each edge must contain at least one cell that is part of the tour, with two cells reachable from it (say a3, b5, c4 or a3, c2, c4), and at least two other cells (say b3, b4 or b3, c3) to connect these. These in turn generate two other cells each, but it will be found that none can coincide with the previous five. Two such batches of nine against opposite edges separated by seven units must have an overlap of at least six to give a 12-cell tour (3 + 6 + 3), since an overlap of 5 uses 13 (4 + 5 + 4) and of 4 uses 14 (5 + 4 + 5). The only possible arrangements to do this result in lozenge-shaped short circuits of four moves. (For example a3, b3, c2, c3, c4, d2, d4, e2, e3, e4, f3, g3.)
Here we encounter the first examples of tours of rectangular boards, namely the three tours of the 3×4 board which were found by Euler, two of which are symmetric (we also diagram the asymmetric tour). There are two other three-rank symmetric open tours, within the 3×6 frame. It may be noted that these two tours can be joined, jigsaw-style, to copies of themselves to form open tours within frames 3×10, 3×14, 3×18, and so on endlessly.
In all there are 49 geometrically distinct 12-cell symmetric open tours. These consist of: 2 rectangular (3×4 board), 12 reentrant (derived from the 6 bergholtian tours above by deleting one of the central moves), 27 other shaped-board tours, and 8 with holes. The 27 shaped-board tours use 18 shapes of board. The next diagram shows the 10 shaped boards within the 4×5 frame (1 with 3 tours, 5 with 2 tours, 4 with 1 tour).
Next we show the tours within the 4×7 frame (1 tour), and 5×6 frame (2 with 2 tours, 3 with 1 tour):
There are also eight 12-cell centrosymmetric open tours with holes. Of these 7 are on the same board with two single-cell holes, and 1 is on a board with a two-cell hole.
These have not been counted. There is the one on the 3×4 board diagrammed above. There is only one closed tour within the 3×5 frame, and it is asymmetric, so produces 12 reentrant tours. In a partial enumeration not yet checked, I found 39 non-reentrant tours within this frame. These tours use 10 different board shapes. Removing the minority color square from a2 the other two cells removed can be a1, b2; a1, c3; a1, d2; a1, e1; a1, e3; b2, e1; d2, e1; e1, e3; and with b1 as the minority cell, the others are a3, d2 or a3, e1.