login
A337170
Squares visited by knight moves on a diagonally back and forth numbered board and moving to the lowest available unvisited square at every step.
2
1, 8, 4, 2, 13, 3, 6, 9, 11, 19, 5, 7, 26, 16, 14, 31, 15, 18, 12, 21, 24, 10, 23, 33, 39, 20, 22, 34, 25, 17, 28, 47, 43, 29, 27, 32, 40, 35, 37, 53, 57, 36, 58, 52, 38, 55, 80, 76, 56, 54, 59, 51, 42, 30, 45, 48, 62, 70, 44, 46, 64, 49, 41, 72, 60, 50, 63
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
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
nonn,fini,full,look
AUTHOR
Sander G. Huisman, Jan 28 2021
STATUS
approved