Studies in Tours of the Knight in Three Dimensions

by Awani Kumar

Divisional Director, Social Forestry Division, Kanpur, INDIA.

Note: the Diagrams of the 3D Tours are on a separate page.
Right click and choose 'Open in new window' so it can be read together with the text.

The ever fascinating problem of the knight's tour on a square board (in two dimensions) is almost as old as the game of chess itself and the incessant work of professional and amateur mathematicians has produced voluminous literature over centuries. However, little attention has been paid to its extension in three-dimensional space. Here, the knight is allowed to jump above the board and land up in a cell in the vertical plane. This increases the mobility of the knight considerably. Readers can easily visualize that on a conventional board (in two dimensions), the knight can cover only up to 8 cells but can cover up to 24 cells in three-dimensional space. The author has investigated the tours in three dimensions and the results are no less fascinating than the ones discovered in two dimensions.

Readers can easily verify that the knight's tour is not possible in a 3×3×3 cube because the knight can neither enter nor come out of the central cell. In the smaller cube (2×2×2), it can't even move.

Although the knight's tour is not possible on the 4×4 square it is nevertheless plentiful in the 4×4×2 cuboid.

Perusal of the literature reveals that Gibbins [1] mentioned a closed tour in a 3×3×4 cuboid. Figures 1 to 4 are a few examples of open and closed tours in this three-dimensional array. Readers can visualize them in three dimensions by stacking the layers, one above the other, in alphabetical order. There are tens of thousands of knight's tours in a 3×3×4 cuboid.

Gibbins asserted that "The smallest lattice in which this (closed tour) can be done is the 3×3×4 cuboid"; citing an example by E. Huber-Stockar, Geneva. The author disagrees with Gibbins because it is possible to construct closed, as well as open, tours in a much smaller lattice. Schwenk [2] has proved that 3×10 or 5×6 is the smallest board size in which a closed knight tour is possible. Watkins [3] writes, "The smallest board for which an open tour is possible is the 3×4 board". In three dimensions, the author has observed that 3×4×2 is the smallest lattice in which both closed and open tours are possible. Figures 5 to 8 are a few examples.

Since there are thousands of such tours, they are of little interest as such. However, tours having magic properties are a different story. Figures 9 to 12 are such tours. They have all the rows summing up to the magic constant = 50. The author has enumerated over 40 such semi-magic tours.

If we consider a lattice with square base then 4×4×2 is the smallest lattice in which both closed and open tours are possible. The author has constructed sixteen interesting tours as shown in Figures 13 to 28. All the tours are magic in rows and columns with magic constant = 66. Figures 14 and 23 have 8 pillars summing up to half the magic constant. This is shown in green colour. Each of the 2×2 mini-squares also sum up to the magic constant. Here, open and closed tours are equal in numbers. The author proposes to call the tours from Figures 24 to 28 quintuple tours as they all have an identical layer; having an aesthetical appeal.

Gibbins gives an example of a closed knight tour in a 4×4×4 cube, which was published by F. Maack in Mitt. Uber Raumschack, 1909, No.2, p.31. More recently, Gardner [4] and Petkovic [5] have also given closed tours using only the rhombic pattern. Examples with Beverley pattern and irregular pattern are shown in Figures 29 and 30 respectively.

Many can also be constructed by stacking 4×4×2 tours. Figures 31 and 32 are two examples. Since there are millions of tours in the 4×4×4 cube; they are of little interest as such.

However, magic cubes, like magic squares, have a long history and great fascination for centuries. Guenter Stertenbrink [6] has constructed a magic tour of knight in a 4×4×4 cube in the year 2003. It is shown in Figure 40. All its rows, columns, pillars and space diagonals sum up to magic constant = 130. A closer examination of it reveals that it is a 4-fold cyclic tour. That is, it remains magic in rows, columns, pillars and space diagonals when renumbered from 17, 33 and 49. All the four 2×2 mini-squares on each layer are also magic. The difference between numbers in diametrically opposite cells of each layer is 2. It consists of only squares and diamonds pattern. Seven other tours can be derived from Guenter's tour as shown in Figure 33 to 39.

It is easy to construct knight's tours incorporating the Beverley pattern, however in spite of putting intense effort into this approach, the author couldn't get any magic tours with it. In two dimensions, magic tours involving the Beverley pattern are common but it is almost certain that they do not exist in the 4×4×4 cube. However, magic tour cubes having irregular knight moves are very much there. The author has constructed such a tour as shown in Figure 41. It is also a cyclic tour and Figures 42 to 48 can be derived from it. How many magic cubes are there? Readers are requested to enumerate them.

Kraitchik [7] constructed a 6×6 semi-magic knight tour in 1927. It can be extended to a 6×6×6 cube as shown in Figure 49. This is an open tour since it started from the bottom layer and gradually moved up. In fact, it can be raised to any 6×6×n size.

Figure 50 is another method of constructing a 6×6×6 cube tour by sandwiching four 3×3×4 tours between the 6×6 semi-magic tours of Engelhaupt and Jelliss [8]. The author has enumerated 88 semi-magic tours on the 6×6 board and by carefully selecting and stacking them thousands of 6×6×6 cubes can easily be constructed. Figures 51 and 52 are two examples. Since the number of knight tours increase very rapidly with the size of the cube, construction of simple tours is not that challenging. However, tours having magic properties are always fascinating. Jelliss [9] has proved that magic knight tours are not possible on singly-even boards (6×6, 10×10, 14×14, etc.). But what about magic knight tours in singly-even cube? Readers are requested to look into it.

Figure 53 has layers B and E adding to magic constant = 651 in rows. It has, altogether, 12 magic lines. Figure 54 has 14 magic lines (6 rows and 8 columns) in layers C and D. Figure 55 has 10 magic pillars. All these are shown in blue colour. These are the best magic properties the author could get. Readers are requested to find tours having better magic properties.

Stewart [10] has constructed a closed knight tour by stacking 8×8 tours. Ligondès constructed more than 56 magic tours on the 8×8 board and as a tribute the author has constructed Figure 56 by stacking his 8×8 magic tours. Figures 57 to 60 are tours having two layers adding up to the magic constant = 2052. Another method is by arranging and stacking 4×4×4 magic cube tours as shown in Figure 61. This is a distinct improvement over Stewart's tour because all its 64 pillars are magic (magic constant = 2052). Figures 62 to 64 are other examples.

Figure 65 has magic rows in all its eight layers. Figures 66 to 68 are other examples. Magic lines have been shown in blue colour. In his e-mail dt. November 11, 2003 (with a 4×4×4 magic cube ray diagram), Guenter Stertenbrink asked: "Can we extend the pattern to 8×8×8?" The question has remained unanswered. However, out of 192 rows, columns and pillars in the 8×8×8 cube, the author has found up to 64 to be magic. So the magic ratio up to 33% has been achieved. Can readers improve on this? Please do so. Remember, Rome was not built in a day!

For all practical purposes, the knight's tour problem is inexhaustible. Tours of the knight in three-dimensional space form an unfathomable ocean and we have been able to bring only a few pearls out of it. How many tours are there in 3×4×2, 4×4×2, 3×3×4 and 4×4×4 lattices? Which cuboids have a knight's tour? Can there be magic cubes with Beverley pattern? What about tours having pan-diagonal and bi-magic properties? How many knight's tours are there in m×n×k cuboids and how many magic knight tours are there in the n×n×n cube? A host of such questions remain unanswered.

References

[1] N. M. Gibbins; Chess in 3 and 4 dimension, Mathematical Gazette, May 1944, pp 46-50.
[2] A. J. Schwenk; "Which rectangular chessboards have a Knight's tour?" Mathematics Magazine 64:5(December 1991), pp 325-332.
[3] J. J. Watkins; Across the Board, The Mathematics of Chessboard Problems, Universities Press (India) Private Limited, 2005, p.6.
[4] M. Gardner; New Mathematical Diversions, The Mathematical Association of America, Washington, DC, 1995.
[5] M. Petkovic; Mathematics and Chess, Dover Publications, New York, 1997, p.65.
[6] Guenter Stertenbrink; personal comunication by e-mail dated November 11, 2003.
[7] M. Kraitchik; Le Probl´me du Cavalier, 1927, p.36.
[8] H. Engelhaupt and G. P. Jelliss; Journal of Recreational Mathematics, Vol. 29 (1), 1998, p.70.
[9] G. P. Jelliss; The Games and Puzzles Journal, Issue #25, 2003.
[10] I. Stewart; "Solid Knight's Tours", Journal of Recreational Mathematics, Vol. 4 (1), January 1971, p.1

Acknowledgements: The author has felt that in India, getting the references is more difficult than discovering a magic tour cube. The author is grateful to Takaya Iwamoto for providing Ref.1 and Ref.10 and to Guenter for Ref.6.]