A330189 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to the unvisited square with the fewest visited neighbors. In case of a tie it chooses the square with the lowest spiral number.

1, 10, 3, 6, 9, 4, 7, 2, 25, 50, 79, 116, 45, 74, 71, 106, 67, 36, 61, 94, 31, 54, 89, 128, 175, 84, 81, 118, 163, 76, 113, 72, 107, 68, 37, 62, 95, 136, 59, 56, 87, 126, 83, 172, 169, 82, 171, 224, 285, 354, 431, 516, 349, 426, 275, 210, 213, 112, 157, 208, 267, 334, 263, 200, 101, 66, 63, 38, 65, 144, 193, 250, 315, 246, 137, 186, 133, 238, 183, 134, 181

Offset: 1

Author

Scott R. Shannon (following a suggestion by M. F. Hasler), Dec 04 2019

Keywords

• nonn
• walk
• fini
• full

Comments

This sequences gives the numbers of the squares visited by a knight moving on a square-spiral numbered board, as described in A316667, where at each step the knight goes to the neighbor one knight-leap away which has the fewest visited neighbors. If two or more neighbors exist with the same lowest neighbor count then, from that list of squares, the square with the lowest spiral number is chosen.

The sequence is finite. After 656 steps the square with number 273 is visited, after which all neighboring squares have been visited.

The first step where the knight has only one neighbor to choose from in the list of neighboring squares with the fewest visited neighbors is at step 39 where only neighboring square 56 has one visited neighbor. The first step where the neighboring squares all have two or more visited neighbors is at step 146 where neighboring squares 443, 533, and 535 all have two visited neighbors.

Like the walks in A329520 it is not immediately obvious that this will be a finite walk as one may believe the knight would be constantly moving away from the origin and thus never be trapped. But like in those walks, the knight here leaves gaps in its path as it moves away from the origin, which will subsequently be visited due to the knight's preference of choosing the square with the smallest spiral number when two or more squares with the same neighbor count are encountered. This draws the knight toward the origin where it will eventually be trapped.

Examples

			See A316667 for the spiral board numbering.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..657
• Scott R. Shannon, Image showing the 656 steps of the knight's path. The green dot is the starting square with number 1 and the red dot the final square with number 273. The red dot is surrounded by blue dots to show the eight occupied neighboring squares. Also shown are yellow dots which indicate squares where only one square was in the list of neighboring squares with the fewest neighbors, and cyan dots which indicate squares where the minimum visited neighbor count of neighboring squares was two or more.
• N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).
• N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.

Crossrefs

Cf. A316667, A329520, A329518, A329519.