A329520 a(n) is the number of completed steps before being trapped for a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest spiral number and with n or fewer visited neighbors. It only moves to squares with n+1 or more visited neighbors when no other squares are available, and if two or more such squares are present it chooses the square with the fewest visited neighbors, then the square with the lowest spiral number if still tied.

1151, 225, 1866, 513316, 11171, 3935788, 23014, 2015

Offset: 1

Author

Scott R. Shannon, Nov 19 2019

Keywords

• nonn
• fini
• full
• walk

Comments

This sequence gives the number of completed steps for a knight before being trapped when moving on a square-spiral numbered board and at each step choosing an unvisited square one knight-leap away which has the lowest spiral number and has n or fewer visited neighboring squares. It will only move to a square with n+1 or more neighbors when no square with n or fewer neighbors is available. If it is forced to move to such squares and two or more are available, it will choose the square with the fewest neighbors. If two or more squares with the same number of neighbors exist then it will choose the square with the smallest spiral number.

For n = 8 the path is equivalent to that given in A316667. Every square will always have eight or fewer visited neighbors, thus all unvisited squares are available to move to and the one with the smallest spiral number will always be chosen. This is A316667.

The values are surprisingly diverse, and it is not immediately obvious that the smaller values of n will even have a finite path length. It seems reasonable to assume that with the knight always choosing squares with very few visited neighbors it would be constantly moving away from the origin and thus never be trapped. But the path taken shows that, with such a restrictive choice of neighboring squares, the path leaves large areas of unvisited squares as the knight moves around the board, some of these being relatively close to the origin. At some point the knight will have an open path and move to these squares, thus move toward the origin, due to its preference to choose the squares with the smallest spiral number. It is thus drawn inward where it will then be surrounded by previous visited squares and eventually trapped. This tendency to leave large areas of unvisited squares is most easily seen in the path for n = 2, see link below, which is trapped after only 225 steps.

On the other extreme the path for n = 6, see A329519, is such that very few open areas remain near the origin, but the knight is still cautious in its choice and will not move to a square where it will likely be trapped, unless no other choices exist. This leads to the knight performing an extremely long walk before eventually finding a gap in its previous paths, moving toward the origin and finally being trapped after 3935788 steps.

Examples

			a(6) = 3935788. See A329519.
a(7) = 23014. See A329518.
a(8) = 2015. See A316667.
See A316667 for the spiral board numbering.
		

Links

• Scott R. Shannon, The knight's path for n = 1. The knight is trapped after 1151 steps. In this and other images the first square is marked in green, the final square in red, and the eight blocking squares in blue.
• Scott R. Shannon, The knight's path for n = 2. The knight is trapped after only 225 steps. The start square acts as one of the blocking squares.
• Scott R. Shannon, The knight's path for n = 4. The knight is trapped after 513316 steps. In this image the cyan points indicate where the knight would have gone to a square with eight neighbors, and thus been trapped, if these were not rejected by the n = 4 cutoff. The yellow colored points indicate similar but for combined neighbor counts of five, six and seven neighbors. The final square is in the cusp of the outer edge near the 7:30 clock position.
• N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Crossrefs

Cf. A316667, A329518, A329519.