

A329519


Squares visited by a knight moving on a squarespiral numbered board where the knight moves to an unvisited square with the lowest spiral number and with six or fewer visited neighbors. It only moves to squares with seven or more visited neighbors when no other square is available; if two or more such squares are present it chooses the square with the fewest neighbors, then the square with the lowest spiral number if still tied.


4



1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This is a variation of A316667. The same knight move rules apply, but the knight will not move to a square which has seven or eight visited neighbors unless no other square is available. If the only unvisited squares available to move to have seven or eight neighbors it will choose the one with the lowest number of neighbors first, and if a tie still exists it will choose the one with the smallest spiral number.
The sequence is finite. After 3935788 steps the square with spiral number 3352743 is reached after which all surrounding squares have been visited. This is the longest possible path using the given knightleap rules for the eight possible values of visited neighbor count. A329520 gives the other path lengths.
The sequences matches the values of A316667 for the first 332 terms, but on the 332nd step the knight sees that square 193 has seven visited neighbors and thus chooses square 393 instead. Along its path the knight encounters 38812 squares where it would have chosen a square with seven or eight neighbors if only the lowest spiral number was considered; 21897 squares had seven neighbors, 16915 squares had eight neighbors. Of those squares thirteen times a square with seven neighbors was actually chosen due to no other square with a lower neighbor count being available. The first such encounter is after 380990 steps while on the square with number 295910. On this first encounter a square with eight neighbors is also available, and has a lower board number than the square with seven neighbors. Thus if the rules were changed to always select the lowest board number regardless of the number of neighbors in such cases then the knight would choose the eightneighbor square and thus be trapped after 380990 steps.
Due to the knight's avoidance of trapping or potentially trapping squares numerous squares which are inside the knight's overall path are never visited; the first such example is square 193 mentioned above. This is in contrast to standard knight's tours which typically cover all internal squares.


LINKS

Scott R. Shannon, Table of n, a(n) for n = 1..20000
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).


EXAMPLE

See A316667 for the spiral board numbering.


CROSSREFS

Cf. A316667, A323714, A329518, A329520.
Sequence in context: A323763 A316667 A329518 * A323808 A330189 A330008
Adjacent sequences: A329516 A329517 A329518 * A329520 A329521 A329522


KEYWORD

nonn,fini,walk


AUTHOR

Scott R. Shannon, Nov 18 2019


STATUS

approved



