A329129 Squares visited by a knight moving on a board with squares numbered with the minimum number of steps for a knight to reach the square when starting from the origin. The knight moves to the smallest numbered unvisited square; the minimum distance from the origin is used if the square numbers are equal; the smallest spiral number ordering is used if the distances are equal.

0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4

Offset: 0

Author

Scott R. Shannon, Nov 05 2019

Keywords

• nonn
• fini
• walk

Comments

This sequence numbers the squares on the board by using the minimum number of steps a knight takes to reach the square when starting from the 0-squared origin. Once the board is numbered the knight starts at the origin and at each step the knight goes to an unvisited square with the smallest number. If the knight has a choice of two or more squares with the same number it then chooses the square which is the closest to the 0-squared origin. If two or more squares are found which also have the same distance to the origin, then the square which was first drawn in a square spiral numbering is chosen, i.e., the smallest spiral-numbered square as in A316667.

The sequence is finite. After 45576 steps a square with number 60 (spiral number = 56543) is visited, after which all neighboring squares have been visited.

Examples

			The squares are numbered using the minimum number of steps a knight takes to reach the square starting from the origin:
.
  +---+---+---+---+---+---+---+---+---+
  | 4 | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 4 |
  +---+---+---+---+---+---+---+---+---+
  | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 2 | 3 |
  +-- +---+---+---+---+---+---+---+---+
  | 2 | 3 | 4 | 1 | 2 | 1 | 4 | 3 | 2 |
  +---+---+---+---+---+---+---+---+---+
  | 3 | 2 | 1 | 2 | 3 | 2 | 1 | 2 | 3 |
  +---+---+---+---+---+---+---+---+---+
  | 2 | 3 | 2 | 3 | 0 | 3 | 2 | 3 | 2 |
  +---+---+---+---+---+---+---+---+---+
  | 3 | 2 | 1 | 2 | 3 | 2 | 1 | 2 | 3 |
  +---+---+---+---+---+---+---+---+---+
  | 2 | 3 | 4 | 1 | 2 | 1 | 4 | 3 | 2 |
  +---+---+---+---+---+---+---+---+---+
  | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 2 | 3 |
  +---+---+---+---+---+---+---+---+---+
  | 4 | 3 | 2 | 3 | 2 | 3 | 2 | 3 | 4 |
  +---+---+---+---+---+---+---+---+---+
.
If the knight has a choice of two or more squares with the same number which are also the same distance from the 0-squared origin, then the square with the minimum spiral number, as shown in A316667, is chosen.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 0..45576
• Scott R. Shannon, Image showing the 45576 steps of the knight's path. The green dot is the first square and the red dot the last. Blue dots show the eight occupied squares surrounding the final square; the final square is on the boundary just left of the 12 o'clock position.
• N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Crossrefs

Cf. A316667, A326922, A328928.