2
$\begingroup$

Let $n,k \in \mathbb{N}-\{0,1\}$. The generalization of the closed knight's tour problem to higher dimensions asks to move a knight along the $n^k$ cells of a $n \times n \times \cdots \times n$ checkboard belonging to the Euclidean space $\mathbb{R}^k$, touching the centres of all of them only once, and then returning to the starting square at move $n^k$.

Now, as suggested by the definition provided by the FIDE LAWS of CHESS (see Article 3.6), assume that the knight is a piece whose move rule states that it can move to any square/cell of the chessboard that is $\sqrt{5}$ (chessboard) units away from the square where it stands.

Then, assume $n=2$. I have proven here that such a closed knight's tour is always possible as long as $k>6$, while it cannot clearly exists any (possibly open) knight's tour for any $k<6$ (i.e., a knight can perform its special move only once on the $2 \times 2 \times 2 \times 2 \times 2$ board, from a random vertex of the hypercube to the opposite vertex and then there are no other — unvisited — vertices at a distance greater than or equal to $\sqrt{5}$ from the current one).

My question is to find an easy proof that no closed knight's tour exist on the $2 \times 2 \times 2 \times 2 \times 2 \times 2$ board.

$\endgroup$
8
  • $\begingroup$ There is nothing labeled "article 3.6", what exactly are you pointing to on the site? $\endgroup$
    – Ben Grossmann
    Commented Jan 18 at 18:18
  • $\begingroup$ Missed link, fixing it in order to point to a PDF instead to the whole site that can change in the future. $\endgroup$
    – Marco Ripà
    Commented Jan 18 at 18:21
  • $\begingroup$ Anyway, in the previous link to the website, I should have pointed to "FIDE Handbook E/01 " and then we would have get Article 3.6 there (see handbook.fide.com/chapter/E012023). $\endgroup$
    – Marco Ripà
    Commented Jan 18 at 18:24
  • 2
    $\begingroup$ Got it, thanks. Using the $\sqrt{5}$ distance as the criterion is an interesting choice of how to generalize the rule $\endgroup$
    – Ben Grossmann
    Commented Jan 18 at 18:25
  • $\begingroup$ A counterintuitive fact here that might bear making explicit: in a $2 \times 2 \times \cdots \times 2$ board, every square is a corner. It follows that the graph of legal knight moves is regular, contrary to the situation on the traditional chess board. $\endgroup$
    – Ben Grossmann
    Commented Jan 18 at 18:27

1 Answer 1

Reset to default
5
$\begingroup$

Unless I'm mistaken, there is indeed such a path (many such paths!) on the six-dimensional board: each move must change five different coordinates, so it can be thought of as a change of a single coordinate followed by an inversion of all the coordinates.

Now, consider a six-bit Gray code, in particular starting at 000000: such a code will have only one bit changing at a time. This means that the even-index positions will have an even number of bits set and the odd-index positions will have an odd number of bits set. Now, since the inverse of a word with an odd number of set bits is also a word with an odd number of set bits, inverting all of those words must introduce a permutation on them (since inversion is 'reversible') and so will also cover all the odd words. This should mean that if we take any Gray code and reverse all of the odd words, we get a valid Knight's Tour on the $2\times2\times2\times2\times2\times2$ board. And there are a lot of Gray codes, even taking the permutation symmetry into account: https://oeis.org/A066037

$\endgroup$
10
  • $\begingroup$ A simple description of one such Gray code: number the coordinates 1 through 6, and let move $i$ be the move that toggles all the coordinates except the $i^{\text{th}}$. Then perform moves 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6. $\endgroup$
    – Misha Lavrov
    Commented Jan 18 at 18:49
  • $\begingroup$ That was the idea, but this is an unexpected outcome... I need to check the result. It would helpful to have the whole set of $64$ moves stated in order to easily check them one by one. $\endgroup$
    – Marco Ripà
    Commented Jan 18 at 18:50
  • $\begingroup$ P.S. I am not sure about the initial statement: "each move must change five different coordinates" (and this is true, but exactly five... nothing more, nothing less) "so it can be thought of as a change of a single coordinate followed by an inversion of all the coordinates." (this seems to be ok at the end). $\endgroup$
    – Marco Ripà
    Commented Jan 18 at 18:55
  • $\begingroup$ Another representation of the tour: identify node $(a_1,\dots,a_6)$ with $a_i \in \{0,1\}$ with the number with binary representation $a_1a_2\cdots a_6$. One knight's tour is then 0, 62, 3, 61, 6, 56, 5, 59, 12, 50, 15, 49, 10, 52, 9, 55, 24, 38, 27, 37, 30, 32, 29, 35, 20, 42, 23, 41, 18, 44, 17, 47, 48, 14, 51, 13, 54, 8, 53, 11, 60, 2, 63, 1, 58, 4, 57, 7, 40, 22, 43, 21, 46, 16, 45, 19, 36, 26, 39, 25, 34, 28, 33, 31, 0. $\endgroup$
    – Ben Grossmann
    Commented Jan 18 at 18:56
  • $\begingroup$ As a useful info, assuming the $k=7$ case, it turned out that about $\frac{1}{10}$ of the possible paths are knight's tour... a huge number of solutions, indeed. $\endgroup$
    – Marco Ripà
    Commented Jan 18 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .