A328909 -id:A328909 - cp's OEIS frontend

A316667 Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square.

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

Offset: 1

Daniël Karssen, Jul 10 2018, following a suggestion from N. J. A. Sloane, Jul 09 2018

Board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12   .
   |   |       |   |   .
  19   6   1---2  11   .
   |   |           |   .
  20   7---8---9--10   .
   |                   .
  21--22--23--24--25--26
.
This sequence is finite: At step 2016, square 2084 is visited, after which there are no unvisited squares within one knight move.

Daniël Karssen, Table of n, a(n) for n = 1..2016
Daniël Karssen, Figure showing the first 60 steps of the sequence
Daniël Karssen, Figure showing the complete sequence
Daniël Karssen, MATLAB script to generate the complete sequence
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

Cf. A316328 (same starting at 0), A329022 (same with diamond-shaped spiral), A316588 (variant on board with x,y >= 0).
Cf. A326924 (choose square closest to the origin), A328908 (using taxicab distance), A328909 (using sup norm); A323808, A323809.
The (x,y) coordinates of square k are (A174344(k), A274923(k)).

A316667(n)=A316328(n-1)+1 \\ M. F. Hasler, Nov 06 2019

a(n) = A316328(n-1) + 1.

A316328 Lexicographically earliest knight's path on spiral on infinite chessboard.

Original entry on oeis.org

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 42, 69, 20, 39, 16, 33, 12, 27, 24, 45, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 50, 47, 76, 113, 72, 107, 150, 67, 102, 63, 66, 35

Offset: 0

N. J. A. Sloane, Jul 13 2018

On a doubly-infinite chessboard, number all the cells in a counterclockwise spiral starting at a central cell labeled 0. Start with a knight at cell 0, and thereafter always move the knight to the smallest unvisited cell. Sequence gives succession of squares visited.
Sequence ends if knight is unable to move.
Inspired by A316588 and, like that sequence, has only finitely many terms; see A316667 for details.
See A326924 for a variant where the knight prefers squares closest to the origin, and gets trapped only after 22325 moves. - M. F. Hasler, Oct 21 2019
See A323809 for an infinite extension of this sequence, obtained by allowing the knight to go back in case it was trapped. See A328908 for a variant of length > 10^6, using the taxicab distance, and A328909 for a variant using the sup norm. - M. F. Hasler, Nov 04 2019

			The board is spirally numbered, starting with 0 at (0,0), as follows:
.
  16--15--14--13--12   :
   |               |   :
  17   4---3---2  11  28
   |   |       |   |   |
  18   5   0---1  10  27
   |   |           |   |
  19   6---7---8---9  26
   |                   |
  20--21--22--23--24--25
.
Coordinates of a point are given in A174344, A274923 and A296030 (but these have offset 1: they list coordinates of the n-th point on the spiral, so the coordinates of first point, 0 at the origin, have index n = 1, etc).
Starting at the origin, a(0) = 0, the knight jumps to the square with the lowest number at the eight available positions, (+-2, +-1) or (+-1, +-2), which is a(1) = 9 at (2, -1).
From there, the available square with the lowest number is a(2) = 2 at (1, 1): square 0 at the origin is not available since already occupied earlier. Similarly, the knight will not be allowed to go on squares a(1) = 9 or a(2) = 2 ever after.

Daniël Karssen, Table of n, a(n) for n = 0..2015
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667 (same with offset 1 and values +1), A316338 (numbers not in this sequence).
Cf. A323809 (infinite extension of this sequence).
Cf. A316588 (variant with diagonally numbered board, coordinates x, y >= 0).
Cf. A326924 and A326922 (variant: choose square closest to the origin), A328908 and A328928 (variant using taxicab distance); A328909 and A328929 (variant using sup norm).
Cf. A326916 and A326918, A326413, A328698 (squares are filled with digits of the infinite word 0,1,...9,1,0,1,1,...).
Cf. A174344, A274923, A296030 (coordinates of a given square).

{local( K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], nxt(p, x=coords(p))=vecsort(apply(K->t(x+K), K))[1], pos(x,y)=if(y>=abs(x),4*y^2-y-x,-x>=abs(y),4*x^2-x-y,-y>=abs(x),(4*y-3)*y+x,(4*x-3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), U=[], t(x, p=pos(x[1],x[2]))=if(p<=U[1]||setsearch(U, p), oo, p)); my(A=List(0)); for(n=1, oo, U=setunion(U, [A[n]]); while(#U>1&&U[2]==U[1]+1, U=U[^1]); iferr(listput(A, nxt(A[n])), E, break)); print("Index of the last term: ", #A-1); A316328(n)=A[n+1];}

a(n) = A316667(n+1) - 1.

Terms from a(17) on computed by Daniël Karssen, Jul 10 2018

Examples added and crossrefs edited by M. F. Hasler, Nov 04 2019

A328929 Squares visited by a knight moving on a square-ringed numbered board where 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.

Original entry on oeis.org

0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 3, 3, 2, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 2, 3, 4, 3, 4, 5, 3, 3, 4, 5, 3, 4, 5, 4, 4, 5, 6, 4, 5, 3, 4, 5, 4, 5, 6, 4, 3, 4, 5, 4, 4, 5, 4, 4, 5, 4, 3, 4, 5, 4, 4, 5, 4, 4, 5, 4, 5, 4, 4, 5, 4, 4, 5, 6, 5, 5, 6

Offset: 0

Scott R. Shannon, Oct 31 2019

This sequence uses the number of the square ring of squares surrounding the 0-numbered origin to enumerate each square on the board. At each step the knight goes to an unvisited square with the smallest square 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 25108 steps a square with the number 73 (standard spiral number = 21041) is visited, after which all neighboring squares have been visited.

			The squares are labeled using the number of the square ring of squares surrounding the origin:
.
    +---+---+---+---+---+---+---+
    | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
    +---+---+---+---+---+---+---+
    | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
    +---+---+---+---+---+---+---+
.
If the knight has a choice of two or more squares with the same number which also have the same distance from the origin, then the square with the minimum square spiral number, as shown in A316667, is chosen.

M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Scott R. Shannon, Image showing the 25108 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 at about the 4:30 clock position.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667, A326922.
Cf. A328909 (number of the visited square, following spiral numbering).
Cf. A326922 (variant using Euclidean or L2-norm), A328928 (variant with 1-norm = taxicab distance); A326924, A328908 (corresponding trajectories, i.e., spiral number of squares).

A328929(n)=normlp(coords(A328909(n))) \\ with coords() defined in A328909 or in A296030. - M. F. Hasler, Nov 04 2019

a(n) = max(|A174344(p)|, |A274923(p)|), p = A328908(n)+1. - M. F. Hasler, Nov 04 2019

A326924 Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

Original entry on oeis.org

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81

Offset: 0

M. F. Hasler, Oct 21 2019

"Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral.
Differs from the original A316328 from a(34) = 76 on. See there for more information and other related sequences.
The knight gets trapped at the 22325th move at position (x,y) = (81, -18), from which it can't reach any unvisited square.
Sequence A326922 gives the distance^2 of the square number a(n) visited at move n. - M. F. Hasler, Oct 22 2019
From M. F. Hasler, Nov 04 2019: (Start)
When a(22325) = 25983 at (81, -18) is reached, at distance sqrt(6885) from the origin, the last unvisited square has number 13924, at (-59, 59), distance sqrt(6962) from the origin. This suggests that in an infinite extension (knight moves one step back if no unvisited square is available, cf. A323809) the knight might eventually visit every square. Can this be disproved by a counterexample of a square which will never be visited in the infinite extension? (In A328908 such a counterexample exists even before the knight gets stuck.)
The ratio a(n)/n oscillates between 0.5 and less than 1.7 for all n > 3000, even < 1.5 for all n > 14000, cf. graph of the sequence. What is the superior and inferior limit of this ratio, assuming the infinite extension beyond n = 22325?
(End)

M. F. Hasler, Table of n, a(n) for n = 0..22325
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
M. F. Hasler, Plot of knight tour A326924(0..22325), ending at (x,y) = (81,-18), Oct 20 2022.

Cf. A316328, A326918, A326922.
Cf. A326413, A326916, A316667; A328908, A328928; A328909, A328929; A326413, A328698.
Cf.  A174344, A274923, A296030 (coordinate of square number n).

{local(coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), U=[]/* used squares */, K=vector(8, i, [(-1)^(i\2)<<(i>4), (-1)^i<<(i<5)])/* knight moves */, pos(x,y)=if(y>=abs(x),4*y^2-y-x, -x>=abs(y),4*x^2-x-y, -y>=abs(x),(4*y-3)*y+x, (4*x-3)*x+y), t(x, p=pos(x[1],x[2]))=if(p<=U[1]||setsearch(U, p), oo, [norml2(x),p]), nxt(p, x=coords(p))=vecsort(apply(K->t(x+K), K))[1][2]); my(A=List(0)/*list of positions*/); for(n=1, oo, U=setunion(U, [A[n]]); while(#U>1&&U[2]==U[1]+1, U=U[^1]); iferr(listput(A, nxt(A[n])), E, break)); print("Index of last term: ", #A-1); A326924(n)=A[n+1];} \\ To compute the infinite extension, set upper bound in for() loop and replace "break" by listput(A, A[n-1])

A326918 Squares visited by a knight moving on a single-digit square-spiral numbered board where 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.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 2, 3, 2, 2, 1, 3, 1, 1, 1, 2, 2, 3, 2, 3, 1, 4, 3, 5, 6, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 1, 0, 1

Offset: 0

Scott R. Shannon, Oct 21 2019

This sequence uses the same board numbering as A326413, and like that sequence, if the next step encounters two or more squares with the same square number, it then chooses the square which is the closest to the original 0-squared origin. But if two or more squares are found which also have the same distance to the origin, then the square which was first drawn in the spiral numbering is chosen, i.e., the smallest standard spiral numbered square as in A316667.
The sequence is finite. After 1069 steps a square with the number 9 (standard spiral number = 473) is visited, after which all neighboring squares have been visited.
Sequence A326916(n) gives the number of the square visited at step n, i.e., its rank in the spiral, starting with 0, as illustrated, e.g., in A326413. The digit on that square, i.e., a(n) can be obtained through A007376, cf. formula. - M. F. Hasler, Oct 21 2019

			The squares are numbered using single digits of the spiral number ordering as:
                                .
    2---2---2---1---2---0---2   :
    |                       |   :
    3   1---2---1---1---1   9   3
    |   |               |   |   |
    2   3   4---3---2   0   1   1
    |   |   |       |   |   |   |
    4   1   5   0---1   1   8   3
    |   |   |           |   |   |
    2   4   6---7---8---9   1   0
    |   |                   |   |
    5   1---5---1---6---1---7   3
    |                           |
    2---6---2---7---2---8---2---9
If the knight has a choice of two or more squares in this spiral with the same number which also have the same distance from the origin, then the square with the minimum standard spiral number, as shown in A316667, is chosen.

Scott R. Shannon, Table of n, a(n) for n = 0..1069
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019.
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019. [Cached copy, pdf file, with permission]
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Scott R. Shannon, Image showing the 1069 steps of the knight's path. The green dot is the first square with number 0 and the red dot the last 1070th square with number 9. The later is surrounded by blue dots to show the eight occupied squares.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A326916, A326413; A316328, A316667; A326924, A326922; A328908, A328928; A328909, A328929; A328698.

Cf. A174344, A274923, A296030 (coordinates of the square number n).

a(n) = A007376(A326916(n)). - M. F. Hasler, Oct 21 2019

A328908 Knight's tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1-norm, then 2-norm, then number of the square: a(n) = number of the square visited at the n-th move.

Original entry on oeis.org

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 175

Offset: 0

M. F. Hasler, Oct 31 2019

Differs from A326924 (where only the 2-norm is considered) from a(73) = 175 on.
The sequence is also finite, when the knight lands on square number a(1092366) there is no unvisited square within reach.
The 1-norm or taxicab distance from the origin of the square a(n) is given in A328928(n).
It appears that this knight's tour would also completely fills the board, if we consider the infinite extension where the knight is allowed to move back on its last step(s) when there's no unvisited square available: no isolated sets of unvisited squares as defined in A323809, seem to occur. Is there a proof or disproof for this? - M. F. Hasler, Nov 04 2019

			The squares are numbered as in the spiral given in A174344 (upside down to get a counterclockwise spiral, but this is irrelevant here).
The knight starts at a(0) = 0 with coordinates (0, 0).
It jumps to a(1) = 9 with co-ordinates (2, -1): all 8 available squares (+-2, +-1) and (+-1, +-2) are at the same taxicab (2 + 1 = 3) and Euclidean distance (sqrt(2^2 + 1^2) = sqrt(5)) from the origin, but square number 9 has the smallest number.
a(73) = 175 with coordinates (7, 0) is the first destination which is preferred due to the 1-norm (= 7) over A326924(73) = 81 with coordinates (5, -4), having 1-norm 5 + 4 = 9 but Euclidean or 2-norm sqrt(41) smaller than 7.
a(1000) = 816 with coordinates (-10, -14).
a(2000) = 2568 with coordinates (-7, -25).
a(5000) = 4476 with coordinates (21, -33).
a(10000) = 15560 with coordinates (-2, -62).
a(20000) = 19566 with coordinates (-36, 70).
a(50000) = 62092 with coordinates (125, -33).
a(10^5) = 135634 with coordinates (-184, -26), taxicab distance 210 from the origin.
a(200'000) = 259798 with coordinates (47, 255).
a(500'000) = 713534 with coordinates (-68, -422).
a(1'000'000) = 995288 with coordinates (217, 499).
a(1'092'366) = 1165672 with coordinates (188, 540), taxicab norm 728 from the origin, is the last square visited by the knight before there is no unvisited square within reach.
By then the earliest square on the spiral not yet visited is number 629641 at (397, 396), taxicab norm 793, and the unvisited square closest to the origin is number 1794929 at (1, 670), taxicab norm 671.

M. F. Hasler, Table of n, a(n) for n = 0..100000
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.

Cf. A328928 for the "value" (= 1-norm) on the visited square.
Cf. A316328 ~ A316667, A326924, A328909 (variants).
Cf. A174344, A274923, A296030 (coordinates of square number n).

{Nmax=1e5;/* Full seq. with > 10^6 terms takes long to compute. */ local( K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], pos(x,y)=if(y>=abs(x),4*y^2-y-x,-x>=abs(y),4*x^2-x-y,-y>=abs(x),(4*y-3)*y+x,(4*x-3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), t(x, p=pos(x[1],x[2]))=if(pt(x+K), K))[1][3], U=0,Umin=0); my(A=List(0)); for(n=1, Nmax, U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1;Umin++); iferr(listput(A, nxt(A[n])), E, break)); print("Index of the last term: ", #A-1); A328908(n)=A[n+1];}

A328928(n) = |A174344(a(n))| + |A274923(a(n))|, the 1-norm (or taxicab distance) of the square visited at the n-th step.

A326413 Successive squares visited by a knight on the single-digit square spiral, with ties resolved towards the left.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 2, 3, 2, 2, 1, 3, 1, 1, 1, 1, 1, 2, 2, 3, 2, 3, 1, 4, 3, 5, 6, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0

Offset: 1

N. J. A. Sloane, Oct 17 2019

Take the standard counterclockwise square spiral starting at 0, as in A304586, but only write one digit at a time in the cells of the spiral: 0,1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,...
Place a chess knight at cell 0. Move it to the lowest-numbered cell it can attack, and if there is a tie, move it to the cell closest (in Euclidean distance) to the start, and if there is still a tie, move to the left(*).
No cell can be visited more than once.
Inspired by the Trapped Knight video and A316667.
Just as for A316667, the sequence is finite. After a while, the knight has no unvisited squares it can reach, and the sequence ends with a(1217) = 4.
(*)Moving to the left means choose the point with the lowest x-coordinate. This leads to an unambiguous choice of tied squares only for the 'move left' case.

			The digit-square spiral is
                                .
                                .
    2---2---2---1---2---0---2   2
    |                       |   |
    3   1---2---1---1---1   9   3
    |   |               |   |   |
    2   3   4---3---2   0   1   1
    |   |   |       |   |   |   |
    4   1   5   0---1   1   8   3
    |   |   |           |   |   |
    2   4   6---7---8---9   1   0
    |   |                   |   |
    5   1---5---1---6---1---7   3
    |                           |
    2---6---2---7---2---8---2---9

Luca Petrone, Table of n, a(n) for n = 1..1217
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019.
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019. [Cached copy, pdf file, with permission]
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A304586, A316667, A328698.

Cf. A326916, A326918; A316328; A326924, A326922; A328908, A328928; A328909, A328929.

More terms from Luca Petrone

Corrected and extended by Eric Angelini, Oct 24 2019

A323808 Squares visited by a knight on a spirally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Original entry on oeis.org

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, 39, 66, 63

Offset: 1

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316667 with which it agrees for the first 2016 terms. - N. J. A. Sloane, Jan 28 2019

			The board is numbered with the square spiral:
  17--16--15--14--13   :
   |               |   :
  18   5---4---3  12  29
   |   |       |   |   |
  19   6   1---2  11  28
   |   |           |   |
  20   7---8---9--10  27
   |                   |
  21--22--23--24--25--26
See A323809 for examples where "backtracking" happens. - _M. F. Hasler_, Nov 06 2019

Daniël Karssen, Table of n, a(n) for n = 1..100000
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810, and A323811.

Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).

A323808(n)=A323809(n-1)+1 \\ M. F. Hasler, Nov 06 2019

a(n) = A323809(n-1) + 1. - M. F. Hasler, Nov 06 2019

A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.

Original entry on oeis.org

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 42, 69, 20, 39, 16, 33, 12, 27, 24, 45, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 50, 47, 76, 113, 72, 107, 150, 67, 102, 63, 66, 35, 38, 65, 62

Offset: 0

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316328, with which it coincides for the first 2016 terms. - N. J. A. Sloane, Jan 29 2019
From M. F. Hasler, Nov 04 2019: (Start)
At move 99999, the least yet unvisited square has number 66048, which is near the border of the visited region. This suggests that the knight will eventually visit every square. Can this be proved or disproved through a counterexample?
More formally, let us call "isolated" a set of unvisited squares which is connected through knight moves, but which cannot be extended to a larger such set by adding a further square. Can there exist at some moment a finite isolated set which the knight cannot reach? (Without the last condition, the square a(2016) would clearly satisfy the condition just before the knight reaches it.)
Such subsets have a good chance of preserving this property forever. It should be possible to prove that an isolated subset sufficiently far (2 knight moves?) from any other unvisited square (or from the infinite connected subset of unvisited squares) remains so forever. (This condition of distance could replace the time-dependent condition "reachable by the knight".)
If such (forever) isolated sets do exist, with what frequency will they occur? Could they have a nonzero asymptotic density? Will this (if so, how) depend on the way the knight measures "lowest available" (cf. variants where the taxicab or Euclidean or sup norm distance from the origin is used)? (End)

			The board is numbered following a square spiral:
  16--15--14--13--12   :
   |               |   :
  17   4---3---2  11  28
   |   |       |   |   |
  18   5   0---1  10  27
   |   |           |   |
  19   6---7---8---9  26
   |                   |
  20--21--22--23--24--25
.
From _M. F. Hasler_, Nov 06 2019: (Start)
At move 2015, the knight lands on a(2015) = 2083, from where no unvisited squares can be reached. So the knight moves back to a(2016) = a(2014) = 2466, from where it goes on to the unvisited square a(2017) = 2667.
Similarly, at moves 2985, 3120, 3378, 7493, 8785, 9738, 10985, 11861, 11936, 12160, 18499, 18730, 19947 and 22251, the knight get "trapped" and has to move to the previous square on the next move.
On move 23044, the same happens on square 25808, and the knight must move back to square a(23045) = a(23043) = 27111. However, there is still no unvisited square in reach, so the knight has to make another step back to a(23046) = a(23042) = 28446, before it can move on to a(23047) = 29123. (End)

Daniël Karssen, Table of n, a(n) for n = 0..99999
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810 and A323811.

Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).

Nmax=1e5 /* number of terms to compute */; {local( K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], pos(x,y)=if(y>=abs(x),4*y^2-y-x,-x>=abs(y),4*x^2-x-y,-y>=abs(x),(4*y-3)*y+x,(4*x-3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), U=0, Umin=0, t(x, p=pos(x[1],x[2]))=if(pt(x+K), K))[1], back=0); my(A=List(0)); for(n=1, Nmax, back||U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1; Umin++); listput(A, nxt(A[n])); if(A[n+1] != oo, back=0, A[n+1]=A[n+1-back+=2])); print("Index of the last term: ", #A-1); A323809(n)=A[n+1];}

a(n) = A323808(n+1) - 1. - M. F. Hasler, Nov 06 2019

Edited by M. F. Hasler, Nov 02 2019

A326916 Trajectory of the knight's tour for choice of the square with the lowest digit, then closest to the origin, then first in the spiral.

Original entry on oeis.org

0, 11, 14, 31, 28, 51, 10, 13, 34, 95, 190, 247, 312, 385, 244, 133, 242, 239, 376, 301, 372, 233, 370, 295, 232, 173, 228, 367, 230, 171, 226, 223, 358, 285, 220, 355, 282, 217, 352, 283, 218, 115, 44, 73, 20, 71, 40, 17, 36, 15, 18, 3, 12, 1, 22, 75, 46, 117, 48, 77, 24, 79, 50, 81, 118, 221, 286, 225, 292, 229, 296, 451, 298, 235

Offset: 0

M. F. Hasler, Oct 21 2019

A variant of Angelini's "Kneil's Knumberphile Knight", inspired by Sloane's "The Trapped Knight", cf. A316328 and links:
Consider an infinite chess board with squares numbered along the infinite square spiral starting with 0 at the origin (as in A174344, A274923 and A296030). The squares are filled with successive digits of the integers: 0, 1, 2, ..., 9, 1, 0, 1, 1, ... (= A007376 starting with 0). The knight moves at each step to the yet unvisited square with the lowest digit on it, and in case of a tie, the one closest to the origin, first by Euclidean distance, then by appearance on the spiral (i.e., number of the square). This sequence lists the number of the square visited in the n-th move, if the knight starts at the origin, viz a(0) = 0.
It turns out that following these rules, the knight gets trapped at the 1070th move, when he can't reach any unvisited square.
See A326918 for the sequence of visited digits, given as A007376(a(n)).
Many squares, e.g., 2: (1,1), 4: (-1,1), 5: (-1,0), 6: (-1,-1), 7: (0,-1), 8: (1,-1), 9: (2,-1), ..., will never be visited, even in the infinite extension of the sequence where the knight can move back if it gets trapped, in order to resume with a new unvisited square, as in A323809. - M. F. Hasler, Nov 08 2019

M. F. Hasler, Table of n, a(n) for n = 0..1069
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019.
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019. [Cached copy, pdf file, with permission]
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

Cf. A326918; A316328, A316667; A326924, A326922; A328908, A328928; A328909, A328929; A326413, A328698.

Cf. A174344, A274923, A296030; A007376.

{L326916=List(0) /* list of terms */; U326916=1 /* bitmap of used squares */; local( K=vector(8, i, [(-1)^(i\2)<<(i>4), (-1)^i<<(i<5)])/* knight moves */, coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), pos(x, y)=if(y>=abs(x), 4*y^2-y-x, -x>=abs(y), 4*x^2-x-y, -y>=abs(x), (4*y-3)*y+x, (4*x-3)*x+y), val(x, p=pos(x[1],x[2]))=if(bittest(U326916, p), oo, [A007376(p), norml2(x), p])); iferr( for(n=1,oo, my(x=coords(L326916[n])); U326916+=1<A326916(n)=L326916[n+1]} \\ Requires function A007376; defines function A326916.

cp's OEIS Frontend

A316667 Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A316328 Lexicographically earliest knight's path on spiral on infinite chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A328929 Squares visited by a knight moving on a square-ringed numbered board where 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A326924 Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A328908 Knight's tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1-norm, then 2-norm, then number of the square: a(n) = number of the square visited at the n-th move.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A326413 Successive squares visited by a knight on the single-digit square spiral, with ties resolved towards the left.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A323808 Squares visited by a knight on a spirally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs