Leapers at Large
© 2001 Knight's Tour Notes by George Jelliss. Note 9e, 1 January 2001.
The {1,3}-mover has many attributes similar to the knight except that it is confined to cells of one colour. In particular the angles between its moves are the same as for the knight and it has the same facility for forming a wider variety of circuits than longer leapers (see Theory of Moves for more on this). By a camel tour on any board we mean a tour of all the squares of one colour.
THEOREM: No camel tours are possible on 2×n or 3×n boards or 4×odd boards. Proof: The 2×n and 3×n boards are too narrow to admit any 'vertical' moves. The camel moves alternately to squares on the odd and even ranks of any board, and on a 4×odd board there are 2h black squares on the even ranks and 2h + 2 on the odd ranks, a difference of 2. The difference in a closed tour must be 0 and in an open tour 1.
On the 4×4 board the six possible camel moves on squares of one colour form a closed circuit, omitting the two central squares of the same colour. On the 4×6 board there is one closed camel tour (given by T. R. Dawson L'Echiquier 1928). This has Bergholtian symmetry (i.e. rotative, crossing at the centre) and by deletion of one move produces 7 reentrant tours (2 of which are symmetric) but in addition there are 4 non-reentrant open tours (1 symmetric), all these are shown. The 4×8 board has no closed camel tours since the moves at a3, g3 and at b2, h2 combine to form two 4-move circuits; however, 3 open tours (2 symmetric) exist, having one end-point in each circuit. The 4×10 admits no tours since the moves at b2, h2 and c3, i3 form two 4-move circuits (P and S), preventing a closed tour, while the moves at a1, a3 and j2, j4 form two paths (Q and R) with no connection between them, and to form an open tour connections must be in the sequence PQRS or PRQS, the ends being in P and S. The 4×12 admits 2 closed tours as shown (1 symmetric); open tours not studied. The 4×14 admits only one closed tour (asymmetric), but 18 symmetric open tours (4 a1–n4, 5 a3–n2, 2 b2–m3, 1 c1–l4, 2 c3–l2, 1 e1–j4, 1 e3–j2, 2 g3–h2); of these, 13 have the middle move vertical and 5 have it horizontal; there are also asymmetric open tours, not counted. The 4×16 has no closed tour, but there are symmetric open tours. The 4×18 has some closed tours, symmetric and asymmetric.
On the 6×6 board there are 9 geometrically distinct camel tours of which 4 are symmetric (2 rotative, Eulerian type, and 2 reflective, with diagonal axis of symmetry).
M. Kraitchik Le Problème du Cavalier (1927) gave three examples 7×7, and a remarkable double tour on an 84-cell serrated board consisting of a 48-cell tour on the majority colour (except for the centre cell) and a 36-cell tour of the minority colour, both in 90° rotational symmetry.
On the 8×8 board there are 4 symmetric tours, all in Bergholtian symmetry. These were given by F. Hansson [Problemist Fairy Chess Supplement April and June 1933 problem 715]. Hansson also considered tours on an 8×8 cylinder board.
W. W. Rouse Ball Mathematical Recreations and Essays (1939 p.185) states that Euler applied his construction method "to find a reentrant route by which a piece that moved two cells forward like a castle and then one cell like a bishop would occupy in succession all the black cells on the board", in other words a camel tour, but I think this is an error. The earliest camel tour I know is one by T. R. Dawson in Cheltenham Examiner 1913.
A zebra move is from corner to corner cells on a 3×4 board, so on a 3-rank board it has no moves at all on the middle rank, and on a 4-rank board it has only one horizontal move from the cells a2, a3, b2, b3 etc, and so no tours are possible. On a 5-rank board the possibility of a tour looks, more promising: its moves on the 5×5 board form two square-symmetric circuits, one of 8 moves through the corner cells and one of 16 moves, leaving only the centre cell unused. The zebra is a free leaper on the 5×6 board and on any rectangle of larger dimensions (i.e. it can reach any cell from any other), however, it cannot tour this board. In fact we can prove:
THEOREM: The zebra cannot tour any board of side 6, 7 or 8. Proof: (a) No closed tours are possible since the path of the zebra through a2 and b1 is determinate and passes also through d4, but its paths through y1, y2, z1, z2 (where y denotes the penultimate and z the last file) are also determinate and at least one of these on a 6, 7 or 8 file board also uses d4, so we would have three moves impinging on d4, which is impossible in a tour. (b) In an open tour we have end cells, so we could avoid such a triple point by deleting one of the three moves and taking the cell at its other end as an end point. However, we only have two end-points, and we always have either more than two triple points or two points where at least four moves converge, or one point where at least five moves converge, so two deletions are insufficient. (In the general theory these multiple points are termed 'snags'.)
Thus, in particular, no zebra tour is possible on the normal chessboard. We now consider longer 5×n boards. The 5×6, 5×7, 5×8 are eliminated by the above theorem. Since each zebra move is from one colour to another no closed tours are possible on odd×odd boards, and an open tour, if possible, must start and end on cells the same colour as the corner cells (which we take to be white). On the 5×9 board the moves through the black cells b3, h3 form a 4-move short circuit, so no open tour is possible. On the 5×10 board the moves through b3, h3, c3, i3 form two 4-move circuits, so no closed tour is possible; and an open tour with one end in each circuit is impossible, since the moves through j2, j4, i1, i5 meet at f3, preventing moves c1-f3 or c5-f3, so that the moves through a2, a3, a4, b2, b4, c1, c5 form a 16-move circuit. On the 5×11 board consideration of the moves forced at the black squares a2, b1, a4, b5 and k2, j1, k4, j5 fixes the path through d2, d4, h2, h4 also; but now the moves through f1, f5 must go to c3, i3, forming a 4-move short circuit. On the 5×12 .... On the 5×13 board the moves through the black squares a2, b1, a4, b5 and m2, l1, m4, l5 fix the moves through d2, d4, j2, j4; but now the moves through g2, g4 must go to e1, e5, i1, i5, where they join with the moves from b3, l3 to form an 8-move short circuit. On the 5×14... On the 5×15...
The smallest rectangular board on which a zebra tour is possible is the surprisingly large 80-cell 5×16 board! The following tour was published in the Journal of Recreational Mathematics (1995).
As proved above, no zebra tour, open or closed, is possible on the 8×8 board. The longest zebra paths achieved are 54 moves (55 cells) open and 52 closed, and symmetric (Jelliss Chessics).
A closed 10×10 zebra tour was found by A. H. Frost as long ago as 1886 (in M.Frolow, Les Carrés Magiques, Paris 1886, Plate VII). This subject was rediscovered by Kraitchik (1927 pp.70-73) who gave two examples, one open, one closed, and full details of how they were constructed by Euler's method.
H. H. Cross gave an open tour in Fairy Chess Review February 1941 (problem 4709) - not shown here, which led T. H. Willcocks to compose a closed tour about the same time but which was not published until 1978 in Chessics, where it resulted in quatersymmetric examples by W. H. Cozens and myself. Finally, Tom Marlow (March 1998) applied the computer program he had used to count 10×10 knight tours with rotative quaternary symmetry to the zebra problem, with minor adaptations, and found there were only 6 geometrically distinct zebra tours of this type in all; these results were published in The Games and Puzzles Journal [vol.2 nr.16 1999 p.290]. All these tours are shown above.
A giraffe {1,4} move needs a 2×5 board, so the smallest board on which it can move on every cell is 2×8. On a 5×5 board its 16 moves form a circuit that tours all the edge cells. On the 6×6 board it cannot move on the centre cells and its moves from the corners meet to form 4-move circuits, but on the other cells it has a 28-move octonary tour. On the 7×7 board it has no move at the centre cell, but forms octonary circuits of 8, 16 and 24 moves which together cover the other 48 cells. The 5×8 board is the smallest rectangle on which the giraffe is a free leaper, and three geometrically distinct tours are possible, all given by T. R. Dawson L'Echiquier December 1930.
The 8×8 board can be covered with 16 four-move giraffe circuits, analogous to the knight's squares and diamonds, but the question of whether a giraffe tour on the 8×8 board is possible puzzled investigators for many years. T. R. Dawson wrote in Cheltenham Examiner 22 May 1913: "I see no reason why a giraffe tour of the board cannot be made, analogous to the knight's, but have not succeeded in working it out at the present." Kraitchik in L'Echiquier 1927 (p.257) says: "Mr T. R. Dawson believes that a tour of the 8×8 board by a (1,4) leaper is impossible." S. Vatriquant in L'Echiquier May 1928 (problem 267) gave a 63-cell tour (omitting h8) that claims to be a giraffe tour, but his move 55–56 is a camel move! Dawson corrected this error in L'Echiquier December 1930 (p.1085) with a correct 63-cell open tour (omitting h8; or c3 by diverting the route g4-h8-d7). Fifty years later I published a 62-cell closed tour (omitting c3 and f3). A proof of the impossibility of a closed giraffe tour was given by me in Chessics #2 1976, as follows.
THEOREM: A closed giraffe tour of the 8×8 board is impossible. Proof: Letter the cells of the board ABCD as shown. In this every A communicates by giraffe moves only with Bs,so in a closed tour every A must be preceded and followed by a B. But the number of Bs is the same as the number of As. This equality is possible only if the As and Bs form a closed circuit. But this would exclude the Cs and Ds.
THEOREM: An open giraffe tour of the 8×8 board is impossible. Proof: The previous argument to prove the impossibility of a closed tour shows that an open tour must be of the form ABABAB...AB–CD...CDCDCD. Now combine the lettering with the numbering shown in the other diagram above. This has the property that cells A1 communicate only with cells B1. These cells are equal in number (8), so the A end of the tour must start on an A1. Similarly it must end on a D1. So the whole tour becomes A1B1...A1B1 – A2B2...A2B2 – C2D2...C2D2 – C1D1...C1D1. But the flaw in this scheme is that there is no move of the type B2 – C2 needed to link the two halves of the tour!
Some giraffe tours on larger boards: T. R. Dawson in The Problemist July 1926 (problem 41) gave an open 9×9 giraffe tour. E. Huber-Stockar in Fairy Chess Review February/April 1945 (problem 6304) gave a 9×10 tour with axial symmetry. The 10×10 case was solved with a closed giraffe tour by A. H. Frost as long ago as 1886 (in M. Frolow, Les Carrés Magiques, Paris 1886, Plate VII).
Here are two 10×10 quaternary giraffe tours.
The antelope or {3,4}-mover needs at least a 4×5 board to move. On a 6-rank board it has at most only one move from the end four cells of the central ranks, so no tours are possible. On the 7×7 board its moves form three octonary circuits of 8, 16 and 24 moves (similar to the giraffe), omitting the centre cell. It is a free leaper on the 7×8 board but cannot tour it; W. Langstaff (Fairy Chess Review Problem 5798, December 1943 p.69 and February 1944 p.78) gave a 47-move path on the 7×8.
On the 8×8 board: F. Douglas (Problemist Fairy Chess Supplement, Problem 403, April 1932) gave a 44-move closed path, with quaternary reflective symmetry, with diagonal axes; W. Langstaff (FCR, Problem 5589, 1943) gave a 50-move open path; and later (Problem 5732, October 1943 p.61 and December 1943 p.70) a 52-move solution, but these were surpassed by some 54-move examples by A. H. Haddy and T. H. Willcocks (FCR, Problem 5817, February 1944 p.74 and April 1944 p.85; Problems 6095-6, August 1944 p.101) Willcocks later gave a closed solution.
As for the zebra, we can prove, by considering the formation of 'snags' that no antelope tours are possible on boards 8×n to 12×n. On the 13×13 board its moves through a3, b2, b3, c3, and cognate cells form three short circuits, so no tours are possible. T. H. Willcocks gave quatersymmetric tours by {3,4}-mover and {2,5}-mover on the 14×14 board in Chessics 1978. For reasons of clarity, the hand-drawn diagrams used there only showed one quarter of the path. Now that drawings can be made with computer precision we are able to show the full tours with reasonable clarity, but I have left out the background squares in these cases.
{1,5}-Mover and {1,7}-Mover. T. R. Dawson, L`Echiquier August 1928 Probem 285, noted a general method for a {1, 2n+1}-mover touring cells of one coour on a board (2n+2)×(4n+2). The method is similar to the corner-to-corner tour by camel on 4×6 board shown earlier. The next cases are {1,5} on 6×10 and {1,7} on 8×14.
{1,6}-Mover. T. R. Dawson, L`Echiquier, July 1928 problem 278, gave a general method for {1,2n}-mover touring a board (2n+1)×(4n). For n = 1 we get the corner-to-corner 4×4 knight's tour, and for n = 2 the similar 5×8 giraffe tour. The next case is a 7×12 tour by {1,6}-mover. Kraitchik noted that when numbered the numbers in the same rank are congruent mod 2n+1.
