Knight’s Yarn
A brief intro to knight tours
The knight tour on an infinite chess board is a sequence of knight moves during which the knight may only visit each square once.
Each subsequent move is determined by prioritizing one of the up to 8 possible squares the knight can jump to. This could be by enumerating the squares or by some metric prioritizing the shortest the distance to the origin (any set of rules that you come up with is allowed, especially if it does create interesting and beautiful patterns).
The Numberphile Video “The Trapped Knight” provides an accessible introduction to the problem, discussing the tour on the square spiral.
OEIS lists a selection of variants of the tour and their length.
Given a starting point (x,y) and our chosen rule set we are interested in the length of the sequence before the knight gets trapped. This happens when there is no longer a free square for the knight to jump to.
While in the case of the square spiral the sequence is only 2015 moves long, a variant that uses the L1-norm to rank the possible moves (and a predefined order of all 8 knight moves as tiebreaker) already takes us 18 411 moves.
A further variant using the L1-norm and the square spiral as tiebreaker is listed with a length of 1 092 366 on OEIS.
Entering the third dimension
Now what if we considered a three dimensional chess board? Do the sequences still terminate? If so how long does it take?
First, we usually generalize knight moves to higher dimension as moving one square on one axis and two squares on a second axis. In three dimensions this means we have the following 24 legal knight moves (as vectors):
(-2, -1, 0), (-2, 0, -1), (-2, 0, 1), (-2, 1, 0),
(-1, -2, 0), (-1, 0, -2), (-1, 0, 2), (-1, 2, 0),
(0, -2, -1), (0, -2, 1), (0, -1, -2), (0, -1, 2),
(0, 1, -2), (0, 1, 2), (0, 2, -1), (0, 2, 1),
(1, -2, 0), (1, 0, -2), (1, 0, 2), (1, 2, 0),
(2, -1, 0), (2, 0, -1), (2, 0, 1), (2, 1, 0)
As a metric we consider the L2-norm to (0,0,0) where we let the tour start.
A tiebreaker is decided through the order of the moves as listed above.
The figure below shows the tour after the first 500 moves.
The knight hops and wraps around the origin, forming a rough sphere.
Does it terminate?
So far we don't know. We’ve computed the tour up to a length of 448 467 279 but the knight doesn’t seem to get trapped anytime soon.
We were neither able to prove that it does not get trapped or to craft a scenario where it would get trapped.
Any remarks and ideas are appreciated!
