In a featured video from Numberphile:Trapped Knight, Sloane illustrated a discovery by Daniel Karssen that if a knight moves on the chessboard marked by spiral integral sequence and hops to the smallest unvisited square, the length of such path is finite. We use the conclusion in the video and add wavy color pattern to the map for beautiful visualization effect with different distance functions.

Setup and how to play

My configuration for the path visualization is based the set of magic number, {2016, 2084}, from the Numberphile video to assign a proper boundary in the simulation. It means the move set stops at 2016 steps and the last integer it visit is 2084. The actual code uses slightly larger number for larger grid to prevent overflow at the grid boundary. See comment section for how to choose this number.
The spiral integer sequence is provided in the function repository:
In[]:=
grid=Most[Round@ResourceFunction["SquareSpiralPoints"][120]];
And I build two lookup tables to easily find the conversion integer to its position on the grid in two ways:
In[]:=
gridIdx=AssociationThread[grid->Range[Length[grid]]];​​invLookup=AssociationThread[Range[Length[grid]]->grid];
Visualize the spiral integers on chessboard:
In[]:=
pts=grid[[;;81]];
In[]:=
Graphics[{bw/@pts,Text[gridIdx[#],#]&/@pts,Opacity[0.3],Blue,Arrow[pts]}]
Out[]=
Assume the knight starting from 1. The valid move sets are illustrated with arrows. Because 10 is the smallest unvisited, we move knight to 10:
In[]:=
Graphics[{bw/@pts,Text[gridIdx[#],#]&/@pts,​​Text[Style["♞",18],invLookup[1]],​​Arrow[{invLookup[1],invLookup[1]+#}]&/@knightMove​​}]
Out[]=
At square 10, the smallest unvisited square is 3 (notice we have already visited 1 at beginning):
In[]:=
Graphics[{bw/@pts,Text[gridIdx[#],#]&/@pts,​​Text[Style["♞",18],invLookup[10]],​​Arrow[{invLookup[10],invLookup[10]+#}]&/@knightMove​​}]
Out[]=
At square 3, the next valid move is to 6. Then 4, then 7 and so on:
In[]:=
Table[Graphics[{bw/@pts,Text[gridIdx[#],#]&/@pts,​​Text[Style["♞",18],invLookup[square]],​​Arrow[{invLookup[square],invLookup[square]+#}]&/@knightMove​​}],{square,{6,9,4}}]//GraphicsRow
Out[]=

Algorithm

I use two simple data structures. Use stack to save the visited node; use a hash table to store every coordinate to integer pair and remove any pair if it is visited.
In[]:=
stk=CreateDataStructure["Stack"];​​latticeHt=CreateDataStructure["HashTable"];
A reset function is defined before each run:
In[]:=
reset[]:=(stk["DropAll"];latticeHt["KeyDropAll"];Scan[latticeHt["Insert",#]&,Normal[gridIdx]])
Define a function that checks the valid move given the current position. the function removes the current position as a key from the hash table and check the smallest unvisited node. If this location is in the hash table, then it is not visited and we push the coordinate to a stack and remove the coordinate as a key from the same hash table.
In[]:=
knightMove={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
In[]:=
knightNext[curr_]:=Module[{mvSet,pick},​​If[!latticeHt["EmptyQ"],​​latticeHt["KeyDrop",curr];​​mvSet=Select[Threaded[curr]+knightMove,latticeHt["KeyExistsQ",#]&];​​If[mvSet=!={},​​pick=ResourceFunction["PositionLargestBy"][mvSet,-latticeHt["Lookup",#]&];​​latticeHt["KeyDrop",pick];​​mvSet[[pick]],mvSet​​],0]​​]
Repeating this process until we find a node with no valid move left . I cheated a little bit here because I know the step length is 2016 from the video. Otherwise use NestWhile and it terminates until the outcome is zero. zero is a good choice for testing of termination because it is not in the original spiral integer sequence.
In[]:=
reset[];
In[]:=
Nest[(stk["Push",#];knightNext[#])&,{0,0},2016];

Visualization

Define a function for lines based on the midpoint of the segment:
In[]:=
Clear@lineStyleFun
In[]:=
lineStyleFun[{p1_,p2_},shift_,distf_:ManhattanDistance]:={Hue[.35+.3Sin[shift+3π*distf[p1,{0,0}]/55.]],Line[{p1,p2}]}
Use Manipulate to add a wavy color to the map:
Generate animation:

Comment

There is a well known equation determines the number of sides needed to reach a particular number on the integer spiral. I notice the actual largest number visited in the Numberphile video is slightly less than 3200. Then we need at least a 113-sided spiral.
So I choose 120 as a safe measure to generate the grids.
The sequence of visited integers forms OEIS A316667:
Play with different distance function:

CITE THIS NOTEBOOK

Trapped knight path with wavy color​
by Shenghui Yang​
Wolfram Community, STAFF PICKS, October 13, 2024
​https://community.wolfram.com/groups/-/m/t/3296900