OFFSET
1,2
COMMENTS
Board is numbered as follows:
. 17 16 5 4 1 2 9 10 . .
. . 18 15 6 3 8 11 24 . .
. . . 19 14 7 12 23 . . .
. . . . 20 13 22 . . . .
. . . . . 21 . . . . .
. . . . . . . . . . .
This sequence is finite: At step 4408 square 4077 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..4408
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (January, 2019).
MATHEMATICA
(* Version 12.0 or higher needed *)
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], Style[Disk[Last[output["Coordinates"]]+#, 0.2]&/@knightjump, Purple]}]]
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"]["DiagonalZigZagEastQ34", 20000];
grid=Association[MapIndexed[#1->#2[[1]]&, grid]];
ShowRoute[fs=FindSequence[{0, 0}, grid]]
fs
fs["Indices"]
ListPlot[fs["Indices"]]
CROSSREFS
KEYWORD
nonn,fini,full
AUTHOR
Sander G. Huisman, Feb 06 2021
STATUS
approved