cp's OEIS Frontend

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

%I A068608 #24 May 12 2019 18:31:11
%S A068608 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,
%T A068608 27,54,31,60,35,64,67,40,71,74,45,78,49,52,29,56,59,34,63,66,39,70,43,
%U A068608 76,47,80,51,28,55,58,33,62,37,68
%N A068608 Path of a knight's tour on an infinite chessboard.
%C A068608 One of eight possible knight's tours. Squares are numbered in a clockwise spiral. Enumerates all positive integers.
%C A068608 A description of the method to construct the tour is provided in A306659. - _Hugo Pfoertner_, May 11 2019
%H A068608 Hugo Pfoertner, <a href="/A068608/b068608.txt">Table of n, a(n) for n = 0..1088</a>
%H A068608 Frank Ellermann, <a href="http://oeis.org/A068225/a068225.html">Sequences based on a spiral of the natural numbers</a>
%H A068608 Hugo Pfoertner, <a href="/A068608/a068608.pdf">Illustration of tours corresponding to A068608-A068615</a>, (2019).
%H A068608 Dan Thomasson, <a href="http://web.archive.org/web/20161028114643id_/http://www.borderschess.org/KTart.htm">Knight's Tour Art</a>, (2001-2014).
%o A068608 (PARI) \\Ellermann's clockwise square spiral, first step (0,0) -> (0,1)
%o A068608 y=vector(10000);L=0;d=1;n=0;
%o A068608 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));
%o A068608 x=vector(10100);L=1;d=-1;n=0;
%o A068608 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));
%o A068608 \\ Position in spiral
%o A068608 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)))};
%o A068608 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)));
%o A068608 angle(v,w)=atan2(v[1]*w[2]-v[2]*w[1],v[1]*w[1]+v[2]*w[2]);
%o A068608 move=[2,1;1,2;-1,2;-2,1;-2,-1;-1,-2;1,-2;2,-1]; \\ 8 Knight moves
%o A068608 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};
%o A068608 getb(pos)=b[pos[1]+m+1, pos[2]+m+1];
%o A068608 inring(n, p)=!(abs(p[1])<n&&abs(p[2])<n)&&abs(p[1])<=n+1&&abs(p[2])<=n+1;
%o A068608 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
%Y A068608 Cf. A068609, A068610, A068611, A068612, A068613, A068614, A068615, A306659, A306660.
%K A068608 nonn,look
%O A068608 0,2
%A A068608 Hans Secelle and Albrecht Heeffer (albrecht.heeffer(AT)pandora.be), Mar 09 2002