A068608 Path of a knight's tour on an infinite chessboard.

1, 10, 3, 16, 19, 22, 9, 12, 15, 18, 7, 24, 11, 14, 5, 20, 23, 2, 13, 4, 17, 6, 21, 8, 25, 50, 27, 54, 31, 60, 35, 64, 67, 40, 71, 74, 45, 78, 49, 52, 29, 56, 59, 34, 63, 66, 39, 70, 43, 76, 47, 80, 51, 28, 55, 58, 33, 62, 37, 68

Offset

0,2

Comments

One of eight possible knight's tours. Squares are numbered in a clockwise spiral. Enumerates all positive integers.

A description of the method to construct the tour is provided in A306659. - Hugo Pfoertner, May 11 2019

Links

Hugo Pfoertner, Table of n, a(n) for n = 0..1088

Frank Ellermann, Sequences based on a spiral of the natural numbers

Hugo Pfoertner, Illustration of tours corresponding to A068608-A068615, (2019).

Dan Thomasson, Knight's Tour Art, (2001-2014).

Prog

(PARI) \\Ellermann's clockwise square spiral, first step (0, 0) -> (0, 1)
y=vector(10000); L=0; d=1; n=0;
for(r=1, 100, d=-d; k=floor(r/2)*d; for(j=1, L++, y[n++]=k); forstep(j=k-d, -floor((r+1)/2)*d+d, -d, y[n++]=j));
x=vector(10100); L=1; d=-1; n=0;
for(r=1, 100, d=-d; k=floor(r/2)*d; for(j=1, L++, x[n++]=-k); forstep(j=k-d, -floor((r+1)/2)*d+d, -d, x[n++]=-j));
\\ Position in spiral
findpos(i, j)={my(size=(2*max(abs(i), abs(j))+1)^2); forstep(k=size, 1, -1, if(i==x[k]&&j==y[k], return(k)))};
atan2(y, x)=if(x>0, atan(y/x), if(x==0, if(y>0, Pi/2, -Pi/2), if(y>=0, atan(y/x)+Pi, atan(y/x)-Pi)));
angle(v, w)=atan2(v[1]*w[2]-v[2]*w[1], v[1]*w[1]+v[2]*w[2]);
move=[2, 1; 1, 2; -1, 2; -2, 1; -2, -1; -1, -2; 1, -2; 2, -1]; \\ 8 Knight moves
m=6; b=matrix(2*m+1, 2*m+1, i, j, 0); setb(pos)={b[pos[1]+m+1, pos[2]+m+1]=1};
getb(pos)=b[pos[1]+m+1, pos[2]+m+1];
inring(n, p)=!(abs(p[1])<n&&abs(p[2])<n)&&abs(p[1])<=n+1&&abs(p[2])<=n+1;
p=[0, 0]; setb(p); print1(findpos(p[1], p[2]), ", "); p+=move[3, ]; setb(p); forstep(n=1, m-3, 2, my(angmin, jmin, jlast); until(jmin==0, print1(findpos(p[1], p[2]), ", "); angmin=-2*Pi; jmin=0; for(j=1, #move[, 1], my(ptry=p+move[j, ], adiff); if(inring(n, ptry), if(!getb(ptry), adiff=angle(p, ptry); if(adiff<=0, if(adiff>angmin, jmin=j; angmin=adiff; jlast=j))))); if(jmin>0, p+=move[jmin, ]; setb(p); ); ); p+=move[jlast, ]; setb(p)); \\ Hugo Pfoertner, May 11 2019

Crossrefs

Cf. A068609, A068610, A068611, A068612, A068613, A068614, A068615, A306659, A306660.

Sequence in context: A309382 A064211 A050133 * A358278 A195817 A347126

Adjacent sequences: A068605 A068606 A068607 * A068609 A068610 A068611

Keyword

nonn,look

Author

Hans Secelle and Albrecht Heeffer (albrecht.heeffer(AT)pandora.be), Mar 09 2002

Status

approved