15
$\begingroup$

I wonder if Knight's Tours have been explored in higher dimensions, using the following definition of a knight move.

  • In dimension $d=2$, the knight moves left/right and forward/back one step and two steps in either order. This leads to $8$ moves.

  • In dimension $d=3$, the knight moves $\{ \pm 1, \pm 2, \pm 3 \}$ steps in any order along $x,y,z$ axes. This leads to $48$ moves; see below.

  • In dimension $d$, the knight moves $\{ \pm 1, \pm 2, \ldots \pm d \}$ steps in any order along the axes. This leads to $d!\, 2^d$ moves.

I have found literature on knight's tours in 3D but under a different (planar) definition of move.1

It would be interesting to learn which (if any!) $n \times n \times n$ cube chess boards allow a knight's tour.


      KnightMoves3D


1 Awani Kumar. "Magic Knight's Tours in Higher Dimensions." (arXiv link)
Addendum. BenBarber found much more relevant references for planar knight moves in higher dimensions: "with $n$ even, there is always a knight's tour provided that $n$ is sufficiently large." TMA made an incisive observation that answered my explicit question: There is no knight's tour for $d=3,4$, due to parity considerations. So, what remains is: (a) $d \ge 5$ and other odd triangular numbers, or (b) knight's tours of the even-coordinate-sum ("black") cells in $d=3,4$.

$\endgroup$
  • 1
    $\begingroup$ Some more references on the usual problem: the $n$-dimensional chessboards admitting a (conventional) Knight's tour were classified by Josh Erde and independently by Bruno and Sylvain Golenia. $\endgroup$ – Ben Barber May 11 '14 at 14:03
  • 8
    $\begingroup$ Note for when the dth triangular number is even (d is 3 or 4 mod 4), the given move does not change parity, so only half the board can be covered in those dimensions. $\endgroup$ – The Masked Avenger May 11 '14 at 14:14
  • 1
    $\begingroup$ Even coordinates is one subset...however, the idea of every other cell comes from taking the sum of the coordinates to be even. These are the lattices $D_n.$ $\endgroup$ – Will Jagy May 11 '14 at 23:24
  • 1
    $\begingroup$ @WillJagy: That's what I meant by "even coordinates," although I now realize how misleading was that phrasing. Thanks for your correction. $\endgroup$ – Joseph O'Rourke May 11 '14 at 23:45
  • 1
    $\begingroup$ Note that you can transpose ( as well as alter sign on) two adjacent coordinates to get a move of (1, -1) on some two dimensional subspace. This suggests that there is a path which may revisit squares but will eventually visit all squares if there is room to make a move. I think n greater than 3d/2 in two dimensions (and similar constraints) will be .enough to guarantee a tour where possible $\endgroup$ – The Masked Avenger May 12 '14 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.