A272568 - OEIS

%I #15 Jan 08 2019 12:29:59

%S 0,0,2,20,256,2086,16376,121418,871258,6077730,41586532,280783434,

%T 1875742356,12432917916,81868580330,536476588416,3501125753910,

%U 22778101455784

%N Number of distinct n-step paths of a knight moving on an n X n chessboard, starting to at a corner and not visiting any cell twice.

%H César Eliud Lozada, <a href="/A272568/a272568.pdf">List of paths for n=1..5</a>

%p pathCount:=proc(N)

%p   local g1, g2,nStep,gg, nCells, nRow,nCol,nPrev,aNext,nNext, hh, n:

%p   nCells:=N^(2); g1:=[[1]];

%p   for nStep from 1 to N do

%p      g2:=[];

%p      for gg in g1 do

%p nPrev := gg[-1] ;

%p nRow:=1+floor((nPrev-1)/(N)); nCol:=1+((nPrev-1) mod N);

%p aNext:=[];

%p if nRow-2>=1 then

%p    if nCol-1>=1 then aNext:=[op(aNext),nPrev-2*N-1] fi;

%p    if nCol+1<= N then aNext:=[op(aNext),nPrev-2*N+1] fi;

%p end if;

%p if nRow-1>=1 then

%p    if nCol-2>=1 then aNext:=[op(aNext),nPrev-N-2] fi;

%p    if nCol+2<=N then aNext:=[op(aNext),nPrev-N+2] fi;

%p end if;

%p if nRow+1<=N then

%p    if nCol-2>=1 then aNext:=[op(aNext),nPrev+N-2] fi;

%p    if nCol+2<=N then aNext:=[op(aNext),nPrev+N+2] fi;

%p end if;

%p if nRow+2<=N then

%p    if nCol-1>=1 then aNext:=[op(aNext),nPrev+2*N-1] fi;

%p            if nCol+1<= N then aNext:=[op(aNext),nPrev+2*N+1] fi;

%p end if;

%p for nNext in aNext do

%p    if nNext<1 or nNext>nCells or (nNext in gg) then next fi;

%p    g2:=[op(g2),[op(gg),nNext]];

%p end do:

%p      end do:

%p      g1:=g2;

%p   end do:

%p #output: comment this block if output is not required

%p   if N>=3 and N<=5 then

%p      hh:=fopen(cat("KnightPaths_",N,".txt"),WRITE);

%p      for n from 1 to nops(g1) do

%p         fprintf(hh,"%4d: %s\n",n,convert(g1[n],string));

%p      end do:

%p      fclose(hh);

%p   end if;

%p   return nops(g1);

%p end proc:

%p lis:=[seq(pathCount(N),N=1..7)];

%Y Cf. A272469.

%K nonn,walk,more

%O 1,3

%A _César Eliud Lozada_, May 02 2016

%E a(9)-a(15) from _Giovanni Resta_, May 03 2016

%E a(16)-a(18) from _Bert Dobbelaere_, Jan 08 2019