login
A068608
Path of a knight's tour on an infinite chessboard.
11
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
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
KEYWORD
nonn,look
AUTHOR
Hans Secelle and Albrecht Heeffer (albrecht.heeffer(AT)pandora.be), Mar 09 2002
STATUS
approved