Space Tours: Three and Higher Dimensions

© 2014 by G. P. Jelliss (First posted 9 September 2014)


Sections on this page: — Space PiecesGeneral ObservationsSmall Boards (< 64 cells)Intermediate Boards (< 128 cells)Large Boards (< 768 cells)Giant Boards Fourth and Fifth DimensionsRepresentation of HypercubesThe Hyperwazir

«Space Pieces

The following extracts from my article on 'Space Chess' in Variant Chess #23 Spring 1997, p.52-3, explain some basic notions.

By Space Chess I mean any form of chess that uses a three-dimensional board and in which the rules for the pieces, other than the pawns, are the same in all lines and planes of the board. This latter condition is added to exclude games in which the moves between the boards are by 'lift'.

Three-dimensional 'boards' are shown by means of a set of 2-dimensional boards representing successive slices through the 3-dimensional region, the labels of the boards, A, B, C, ... acting as the third coordinate.

A move in three dimensions is represented by three coordinates (r, s, t), indicating that the move is equivalent to r (wazir) steps right, s steps forward and t steps up. (Or respectively left, backward and down if the numbers are negative.) We express the 'pattern' of the move by the corresponding positive or zero values {r, s, t}. The length of an {r, s, t} move is √(r² + s² + t²).

If all three numbers are different and none is zero an {r, s, t}-leaper can move in 48 different directions! The simplest leaper of this type is the {1, 2, 3}-leaper, or √14-leaper (called a Hippogriff in Kogbetliantz's game). If one pair of the coordinates is taken to specify a move on one of the layers of the board, then the third coordinate represents a move up or down. Thus a {1, 2, 3}-leaper either moves vertically one layer and makes a {2, 3} zebra move or vertically 2 and makes a {1, 3} camel move or vertically 3 for a {1, 2} knight move, as illustrated by the marks × in the figure. Since this piece has an even number of odd coordinates it is confined to cells of one shade in the chequering.



Fortunately when there is a zero coordinate or two coordinates are equal the number of moves to be considered reduces considerably. Any 2-D move can be made in 3-D space in each of the three coordinate planes passing through the cell initially occupied by the moving piece. In this way each 2-D (or 1-D) piece defines a corresponding Space Piece.

Thus the Space Rook makes moves of type {0, 0, n} in 6 directions (up-down, left-right, and to-fro), where n can take any value except zero, the Space Bishop makes moves of type {0, n, n} in 12 directions and the Space Knight moves {0, 1, 2} in 24 directions (shown by the marks + in the figure) that is 8 in each of the three planes through its cell.

Moves with all three coordinates non-zero are 'true' 3-dimensional moves, and pieces making them are 'essentially' 3-D pieces. The simplest is the Sprite, which is the {1, 1, 1}-leaper, or √3-leaper. Its corresponding line piece, the {n, n, n}-mover, or √3-rider, is called the Unicorn in Maack's game (but 'Fool' in Kogbetliantz's).

The Rook moves through the faces of the cubic cells, the Bishop moves through the edges of the cubes, and the Unicorn moves through the corners. Thus a Unicorn has a choice of 8 directions of movement. A Rook has access to all the cells of the board, in a series of moves, but it takes two Bishops to patrol the whole space, and four Unicorns.

The King in two-dimensions can be defined either as a Wazir + Fers or as a piece that moves to every 'adjacent' cell (by which we mean any cell that has a boundary point in common with the initial cell). In three dimensions these two definitions are not equivalent. From the definition of Space Piece given above it follows that a piece that has the usual King moves in any plane is properly called a Space King. A piece that moves to every adjacent cell in space is a Wazir + Fers + Sprite which I call a Cubi(c)-King. The royal pieces in the Maack and Kogbetliantz games are of this type. The Cubi-King moves to all 26 outer cells of the 3×3×3 cube around it. The choice of the Cubi-King rather than the Space King as the 3-D monarch is supported by the fact that one Space King could stalemate another on a cubical board (e.g. on Aa1 and Bb2) which may be considered an undesirable property for the royal piece, or at least not analogous to the 2-D case.

The Space Queen is of course Rook + Bishop. Its more powerful cousin the Cubi-Queen runs in the directions that the Cubi-King walks, i.e. Rook + Bishop + Unicorn.

The 3D moves with coordinates non-zero and less than 3 are {1,1,1}, {1,1,2}, {1,2,2}, {2,2,2}. The first and last are Unicorn moves. The {1,1,2} move is of length √6, and I call the corresponding rider a Sexton, it is confned to cells of one colour and can reach all the cells of that colour. The {1,2,2} move is of length √9 = 3. Thus the Threeleaper becomes of special interest in space: besides its 1D move {0,0,3} it has this 3D move. Unlike the Threeleaper in two dimensions, which is confined to 1 cell in every 9, in three dimensions it can get to every cell of the board.

In space we also encounter two other double-pattern fixed-distance leapers before we reach the familiar Fiveleaper. These are the √17 leaper or Space Giraffe which moves {0,1,4} and {2,2,3} and can reach any cell, and the √18 = 3√2 leaper or Space Tripper which moves {0,3,3} and {1,1,4} and is confined to one colour.

«General observations on tours on p×q×r boards

It is easily possible to construct an open knight tour on any board p×q×r where the p×q board has a closed tour. Start the closed tour on the first board at any cell, then jump from the end cell up to the next level and take the cell reached as the start point of the same closed tour, and so on, and on.

In the case of a p×q board that will not admit a closed tour, if the same tour is to be used on every level then either the end cells must be two steps apart {0,2} or can be made two steps apart by a rotation or reflection (see the 2×3×4 tour and my Methuselah tours below).

To join two closed tours on successive layers together to make a closed tour we need to delete one move in each and cross-connect. There are three formations that allow this. All these knight-move pairs are of quite common occurrence in tours, especially the crossing pair, so almost any tour can be used in this way; and any two different tours can usually be lined up to produce these formations.



Once a two layer closed tour has been formed in this way other layers can be added similarly, making a pile of boards to any size r. It may be noted that the centres of all three tetragons are at the mid-point of a cell edge. So this method of linking will only preserve symmetry in tours on odd by even boards. For examples see the sections below on 2×3×10 and 2×5×6 boards.

«Small Boards

2×2×2 = 8 cells

T. R. Dawson (Chess Amateur June 1926) considered moves of rook and bishop (i.e. wazir and fers) in a 2×2×2 board, noting that the net of rook moves form the edges of a cube and that there are 18 oriented tours, 3 geometrically distinct, while the net of bishop moves on one colour form the edges of a tetrahedron and that there are 6 oriented tours, but only 1 geometrically distinct. He also noted that the bishop can describe a triangle in three dimensions.



2×2×4 = 16 cells

The knight's moves on this board form a pseudotour consisting of four circuits of four moves, so no tour is possible. In fact on any board 2×2×n with n > 2 the moves from Aa1 and Ba2 go to Ac2 and Bc1, forming a circuit, so no tour is possible on any of these boards.



2×3×3 = 18 cells

No knight move is possible from the two cells of the centre column, so no tour is possible. However, tours of the remaining 16 cells can easily be formed.

2×3×4 = 24 cells

The corner-to corner 3×4 tour found by Euler (1759) can be combined with a reflected copy of itself on a second board to give a closed 2×3×4 tour, as illustrated below. This seems obvious. However an article in the Mathematical Gazette, 1944 by N. M. Gibbins stated that the minimal board for a tour was 3×3×4, a surprising oversight.

It seems that this error was first pointed out by Awani Kumar in a Note on "Magic Knight's Tours for chess in three dimensions" in the same journal in March 2008. However the four tours given there do not include this simple case! In that paper Fig 1 is an irregular open tour while Figs 3-4 are partially magic, adding to 50 in the four-cell lines. I show Fig. 3 for comparison.



after Euler                   Kumar Figure 3
A             B               A              B
01 04 07 10   22 19 16 13     01 18 21 10   22 09 06 13 
08 11 02 05   17 14 23 20     20 11 16 03   15 04 23 08
03 06 09 12   24 21 18 15     17 02 19 12   24 07 14 05 

3×3×3 = 27 cells

There is no knight move from the centre cell so no knight tour is possible. However tours of the remaining 26 cells are easily found. Wazir tours of the whole board might be of interest.

Two-layer board 2×4×4 = 32 cells

In his 2008 Maths Gazette article Awani Kumar gave 16 figures showing tours on this board that have partially magic properties. The ranks and files of the 4×4 boards all add to 66, and in some cases half of the two-cell columns add to 33, as in this example (his Fig 6):

A             B          
 1 14 23 28   10 19 32  5
24 27  2 13   31  6  9 20
15 22 25  4    8 11 18 29
26  3 16 21   17 30  7 12

Two-layer board 2×3×10 = 60 cells

To make a closed tour in the two-layer case (by joining closed tours on the two layers) it is necessary that the end cell on the upper board be two steps from the start cell on the bottom board. Here is a simple example (Jelliss September 2014) using the 3×10 board which (along with the 5×6) is the smallest rectangle with a closed tour. This tour is symmetric. (It uses a tour by Bergholt 1918.)



Two-layer board 2×5×6 = 60 cells

The same principle as illustrated for the 3×10 board above can be used on the 5×6 board, but since no tours on that board have a symmetrically arranged pair, the symmetry in this case is achieved by rotating the tour used (which is due to Euler 1759).



«Intermediate Size Boards

4×4×4 = 64 cells

A. T. Vandermonde (1771) was the first to construct a three-dimensional knight's tour, using a board 4×4×4. As for his 8×8 tour in the same article, he constructed this closed tour by joining up four circuits. (Some sources mistakenly state that Vandermonde constructed an 8×8×8 tour.) He presented his tour in the form of a series of spatial coordinates (x,y,z) expressed in a fraction style of notation, but translated into numbered cells it becomes:

63 12 25 34    26 41 54 13    05 62 33 18    42 17 04 55 
28 35 64 15    59 16 29 46    38 21 08 51    07 56 43 20 
39 24 11 52    06 53 40 19    27 48 61 14    60 03 32 47 
10 49 36 23    37 30 01 50    58 09 22 45    31 44 57 02 

Two 4×4×4 closed tours are given in Prof Hermann Schubert's Mathematische Mussestunden 1st ed 1898 p.220 (also in 3rd ed 1909 p.34-35; but only one is retained in the 4th ed 1924, edited by Prof F. Fitting p.244. The first is also quoted in Ahrens 1901 p.198). The first is given as the solution of a cryptotour puzzle.

10 07 22 17    27 62 15 02    42 37 56 51    57 30 47 36
21 18 09 06    14 01 26 63    55 52 43 40    48 33 58 31
08 11 20 23    61 28 03 16    38 41 50 53    29 60 35 46
19 24 05 12    04 13 64 25    49 54 39 44    34 45 32 59 

24 39 58 09    35 44 03 14    22 29 54 59    49 34 15 02
19 28 51 62    50 31 18 01    25 40 57 10    36 43 06 13
38 45 04 11    23 42 55 08    48 33 16 63    21 30 53 60
47 32 17 64    20 27 52 61    37 46 05 12    26 41 56 07

Here is another closed tour by T. W. Marlow (Chessics 1987 p.162).

01 08 03 10    24 43 26 19    63 32 55 52    44 61 38 31 
16 11 06 13    27 20 15 30    56 53 48 33    37 50 45 60 
07 02 09 04    64 25 18 41    23 42 57 54    62 39 36 51 
27 05 12 29    17 28 21 14    58 49 34 47    35 46 59 40 

4×4×4 Magic Tours!

Günter Stertenbrink (2003) appears to have been the first to realise that a 4×4×4 knight's tour could be magic! That this is possible on a board with such a short side is surprising to anyone who has studied 8×8 magic tours. The space diagonals (but not the plane diagonals) also add to the magic constant, 130. I'm not sure where it was first published. Here is the tour as shown by John Beasley in Variant Chess #55 (2007):

53 16 43 18    02 59 32 37    47 22 49 12    28 33 06 63 
42 19 56 13    29 40 03 58    52 09 46 23    07 62 25 36 
15 54 17 44    60 01 38 31    21 48 11 50    34 27 64 05 
20 41 14 55    39 30 57 04    10 51 24 45    61 08 35 26 

I understand over 70 such tours were constructed between 2006 and 2009 by Awani Kumar, Günter Stertenbrink and Francis Gaspalou. Here is an open tour by Awani Kumar published in 'Magic Knight's tours in higher dimensions' on the Arxiv website:

19 46 63 02    58 07 22 43    47 18 03 62    06 59 42 23 
48 17 04 61    05 60 41 24    20 45 64 01    57 08 21 44 
29 52 33 16    40 09 28 53    49 32 13 36    12 37 56 25 
34 15 30 51    27 54 39 10    14 35 50 31    55 26 11 38 

3×4×6 = 72 cells

A tour on this board is given in Schubert's Mathematische Mussestunden (1st ed 1898 p.222, 3rd ed 1909 p.36, 4th ed 1924 p.245). It is shown there as four boards 3×6, but for reasons of space and consistency I show it here as three boards 4×6.

61 14 59 10 51 06    02 25 72 15 66 19    27 44 31 48 35 50 
58 11 62 07 54 09    71 22 69 18 63 16    30 41 28 45 38 47 
03 60 13 56 05 52    26 01 24 65 20 67    43 32 39 36 49 34 
12 57 04 53 08 55    23 70 21 68 17 64    40 29 42 33 46 37 

5×5×5 = 125 cells

The 5×5×5 cube is the board used for the Maack version of space chess.

P. C. Taylor (Fairy Chess Review, 1939, vol.4, no.3 and 1940, vol.4, no.4, problem 3928) constructed a figured knight's tour in a 5×5×5 cube under the conditions that (a) the cube numbers (1, 8, 27, 64, 125) are from Cc1 to Cc5, (b) the square numbers are all on the C-plane in a knight's chain and (c) the maximum number of cells are filled before the E-plane is entered. The chain of squares evidently represents a D for Dawson. Add 100 to underlined numbers:

A               B               C               D               E 
17 52 57 46 11  34 47 40 15 32  81 16 25 90 63  84 89 80 71 92  07 18 03 24 13 
58 45 10 51 56  39 20 33 48 05  18 61 64 09 50  79 72 83 88 69  02 23 06 17 04 
53 26 41 12 03  28 35 94 31 14  25 00 27 62 93  82 85 70 91 12  19 08 99 14 97 
22 59 44 55 06  19 38 21 76 95  60 65 08 49 04  73 78 87 68 75  22 01 10 05 16 
43 54 23 30 13  24 29 42 37 02  21 36 01 66 07  86 67 74 77 96  09 20 15 98 11

«Large Boards

Two-layer chessboard 2×8×8 = 128 cells

There are numerous chess variants that use two boards, but where transfer between the boards is permitted this is usually to the corresponding cell on the other board. (The most popular is probably Alice Chess by V. R. Parton where the second board is the land "Through the Looking Glass" rather than on another level. One that is specifically described as a 3D game is Flying Chess by David Eltis 1984 but the vertical moves are straight up and down. See the Encyclopedia of Chess Variants by David Pritchard and John Beasley for more details.)

Tours formed on the same principle as the 2×3×10 and 2×5×6 tours above can only produce asymmetric tours on the 2×8×8 board. It is a matter of finding a tour with a pair of knight moves separated by a two step shift, or that can be placed in this relation by rotation or reflection (assuming the same tour is used on both levels). Here are a couple of tours (Jelliss September 2014) that I have constructed for the purpose.



By repeated linking of tours closed tours of boards of any size 8×8×n can be constructed. These can moreover be spatially symmetric in the cases when n is odd; for example a symmetric middle tour with asymmetric tours above and below, oppositely oriented, and linked to the middle tour in corresponding positions.

Cuboid Chess Board = 312 cells

Cuboid Chess is a 3D game that I described in the Variant Chess article mentioned above. It uses a board 6×6×6 with 4×4 extensions added to the middle of each of the six faces. However I have not attempted any tour of it so far.

8×8×8 = 512 cells

I understand there is a tour 8×8×8 by J. Stewart in the Journal of Recreational Mathematics (vol.4, no.1, 1971) consisting of 8 planar tours stacked so the ends can be connected by knight moves in vertical planes, but I have not seen this article. In the note above on the 2×8×8 case I show tours that can be used on each level to make a closed tour of any size 8×8×n.

Here is another scheme for a closed tour on an 8×8×n board of any size. The tour on the right is Beverley's magic tour and any other magic tour of the 27 type can be substituted. This tour is for the upper and lower levels. The other diagram serves for all the intermediate floors. It shows the 8×8 board covered by two separate tours of 27 and 37 cells. After traversing the ground level tour the knight moves up to the next floor and traverses the 27-cell tour, then up again to tour another 27-cell tour, and so on until it reaches the roof. Here it traces out the Beverley tour in reverse. It can then descend the back staircase, touring the 37-cell part-tours on each floor on the way down, reaching the start again for a 3D closed tour. Any of the intermediate floors can also be reflected front to back.



Here is an alternative scheme of this type with the staircases on right and left and using any corner-to-corner tour at top and bottom. The corner-to-corner tour shown is from Käfer (1842). The two odd-numbered part-tours on the intermediate floors are of 25 and 39 cells this time, and can be reflected left to right.



The sub-tours have to be odd of course snce their ends have to be on the same colour cells when chequered. These schemes were devised by me while writing this article.

«Giant Boards

3×17×19 = 969 cells: Methuselah Tours

The diagrams below (Jelliss 1986) show 19×17 = 323-cell tours based on nightrider patterns 2 and 5 with translational symmetry. Three copies of the first tour, or three of the second tour with the middle copy reflected, will join by knight-move ramps between the floors, to form two 969-cell open "Methuselah Tours", representing the alleged age to which the patriarch lived.

Methuselah Board 1



Methuselah Board 2



7×11×13 = 1001 cells: Sheherazade Tour

This tour (Jelliss, New Year's Greeting card 1986-7, Chessics 1987 p.162) shows a 1000-move knight's tour of a 7×11×13 = 1001-cell board, with the title "The Sheherazade Tour" which was dedicated to Anthony Dickins, who kindly commented: "It was a brilliant idea to make it a 1001 tour and thus simultaneously give it the right to a most apt and fitting title. For Sheherezade used to play chess with her Shah as well as tell him stories - and the Shah (Caliph) was the one in Baghdad at the time of the first great explosion of Fairy Chess under the Moslems."



1001-cell tour continued:



Each "floor" 11×13 is symmetrically toured from f6 to h6 before the knight moves up the central "staircase" to the next level. These 7 tours are based on 7 of the 8 possible area-coverings by nightrider lines and can be taken in any order. The 8th pattern (type 34) cannot be placed symmetrically on an odd-sided board.

«The Fourth and Fifth Dimensions

3×3×3×2 = 54 cells

J. A. Lewis (Fairy Chess Review, February 1944, vol.5, p.74, problem 5818, solution April 1944, pp.85-86). In a 4-dimensonal hypermodel 3×3×3×2 put black knights at IBb2 and IIBb2. A white knight then plays a closed tour of the remaining 52 hypercells.

IA         IB         IC            IIA        IIB        IIC 
17 12 15   42 37 40   49 46 51      06 09 04   35 32 29   28 23 26 
14 01 18   39 -- 43   52 19 48      03 20 07   30 -- 34   25 02 21 
11 16 13   44 41 38   47 50 45      08 05 10   33 36 31   22 27 24

4×4×4×4 = 256 cells

Awani Kumar in the Arxiv article referred to above constructed a magic knight's tour in a four-dimensional 4×4×4×4 board, and also on a 5-dimensional board 4×4×4×4×4. See Figures 9 and 10 in that article for diagrams.

«Representation of Hypercubes

If we represent each of the 2^k binary numbers of k digits by a point and join two points by a line if their numbers differ only by one digit in one position, then the resulting diagram is a net called a k-cube. Equilateral diagrams of the 1, 2, 3 and 4-dimensional cubes are shown below, in which the links are shown as wazir or knight moves.



To draw similar equilateral diagrams for the 5D and 6D cases requires use of a root-65 leaper, that is a {1,8}+{4,7} leaper, but the diagrams take up a lot of room (31×24 board and 39×25 board respectively) and do not show the structure very clearly. A 5-leaper or root-50 leaper does not suffice since there is overlap of the orthogonal {0,5} leaps or of the diagonal {5,5} leaps in places.

Clearer diagrams can be achieved by allowing the edges to be of different lengths and minimising the size of the board on which the diagram is to be drawn. The illustrations show the 4D cube fitted onto a 5×5 board, 5D cube fitted onto a 6×9 board. It is clear from these how each successive dimension is reached by duplicating the diagram from the previous case and joining all pairs of corresponding points of the two diagrams by parallel lines. The 4D net is evidently equivalent to the net of wazir moves on a 4×4 torus board.



A 6D cube can be fitted onto a 10×10 board, using the moves of a {0,1}+{1,2}+{1,4} leaper. A diagram of this type was used as the cover illustration on Chessics #14, 1982, with the caption: "The chessboard as a six-dimensional hypercube".



«The Hyperwazir

By a slight distortion of the 6D pattern above the moves become the {0,1}+{0,2}+{0,4} leaps of a hyperwazir on the 8×8 board. The moves of the hyperwazir on the chessboard constitute a representation of the 6D hypercube. The rule for movement of a hyperwazir is that it can make {0,4} moves freely, {0,2} moves within any quarter of the board, and {0,1} moves within any sixteenth of the board (i.e. any quarter of a quarter). A hyperwazir has 6 moves available at any position on the board, and in fact is capable of making tours of the board. A tour is shown (Chessics #13, p.13, 1982) that uses the maximum number of 48 {0,1} moves. Similar tours can be constructed showing 48 {0,2} moves or 48 {0,4} moves, though these are difficult to show clearly in diagrams because of the need to curve the move lines.



The other tour shown relates to the puzzle toy known as the Chinese Rings or Tiring Irons, in the form of six rings attached to a bar in such a way that a ring can be removed from or put on the bar only when the next lower ring is on and all other lower rings are off. Any configuration of the rings can be represented by a sequence of six binary digits (0 for off, 1 for on), and the most difficult task is to get from 100000 = 32 to 000000 = 0. Surprisingly, to get the ring nearest the handle off the bar we have to put all the others back on! Numbering the squares of the board in natural order (0 on a1, 1 or b1, ..., 63 on h8) and converting the numbers to binary notation, the sequence of positions of the rings can be represented visually by the hyperwazir tour shown (Chessics #19, 1984, pp.30-31). Remarkably, all 64 possible arrangements of the six rings, on or off the bar, are used in the solution.