OFFSET
1,2
COMMENTS
Board is numbered as follows:
1 3 4 10 11 .
2 5 9 12 . .
6 8 13 19 . .
7 14 18 . . .
15 17 . . . .
16 . . . . .
This sequence is finite: At step 343 square 276 is visited, after which there are no unvisited squares within one knight move.
LINKS
Sander G. Huisman, Table of n, a(n) for n = 1..343
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).
MATHEMATICA
ClearAll[ShowRoute, MakeMove, FindSequence]
knightjump=Select[Tuples[Range[-2, 2], 2], Norm[#]==Sqrt[5]&];
ShowRoute[output_Association]:=Module[{colors}, colors=(ColorData["Rainbow"]/@Subdivide[Length[output["Coordinates"]]-1.0]);
Graphics[{Line[output["Coordinates"], VertexColors->colors], Disk[Last@output["Coordinates"], 0.2]}]]
MakeMove[spiral_Association, visited_List]:=Module[{poss, hj}, poss=Table[Last[Last[visited]]+hj, {hj, knightjump}];
poss=DeleteMissing[{spiral[#], #}&/@poss, 1, \[Infinity]];
poss=Select[poss, FreeQ[visited[[All, 2]], Last[#]]&];
If[Length[poss]>0, First[TakeSmallestBy[poss, First, 1]], Missing[]]]
FindSequence[start_:{0, 0}, grid_]:=Module[{positions, j, next}, positions={{grid[start], start}};
PrintTemporary[Dynamic[j]];
Do[next=MakeMove[grid, positions];
If[next=!=Missing[], AppendTo[positions, next], Break[]; ], {j, \[Infinity]}];
<|"Coordinates"->positions[[All, 2]], "Indices"->positions[[All, 1]]|>]
grid=ResourceFunction["LatticePointsArrangement"]["DiagonalZigZagEastQ4", 10000];
grid=Association[MapIndexed[#1->#2[[1]]&, grid]];
ShowRoute[fs=FindSequence[{0, 0}, grid]]
fs
fs["Indices"]
ListPlot[fs["Indices"]]
CROSSREFS
KEYWORD
AUTHOR
Sander G. Huisman, Jan 28 2021
STATUS
approved