cp's OEIS Frontend

A272568 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.

%I A272568 #15 Jan 08 2019 12:29:59
%S A272568 0,0,2,20,256,2086,16376,121418,871258,6077730,41586532,280783434,
%T A272568 1875742356,12432917916,81868580330,536476588416,3501125753910,
%U A272568 22778101455784
%N A272568 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 A272568 César Eliud Lozada, <a href="/A272568/a272568.pdf">List of paths for n=1..5</a>
%p A272568 pathCount:=proc(N)
%p A272568   local g1, g2,nStep,gg, nCells, nRow,nCol,nPrev,aNext,nNext, hh, n:
%p A272568   nCells:=N^(2); g1:=[[1]];
%p A272568   for nStep from 1 to N do
%p A272568      g2:=[];
%p A272568      for gg in g1 do
%p A272568 nPrev := gg[-1] ;
%p A272568 nRow:=1+floor((nPrev-1)/(N)); nCol:=1+((nPrev-1) mod N);
%p A272568 aNext:=[];
%p A272568 if nRow-2>=1 then
%p A272568    if nCol-1>=1 then aNext:=[op(aNext),nPrev-2*N-1] fi;
%p A272568    if nCol+1<= N then aNext:=[op(aNext),nPrev-2*N+1] fi;
%p A272568 end if;
%p A272568 if nRow-1>=1 then
%p A272568    if nCol-2>=1 then aNext:=[op(aNext),nPrev-N-2] fi;
%p A272568    if nCol+2<=N then aNext:=[op(aNext),nPrev-N+2] fi;
%p A272568 end if;
%p A272568 if nRow+1<=N then
%p A272568    if nCol-2>=1 then aNext:=[op(aNext),nPrev+N-2] fi;
%p A272568    if nCol+2<=N then aNext:=[op(aNext),nPrev+N+2] fi;
%p A272568 end if;
%p A272568 if nRow+2<=N then
%p A272568    if nCol-1>=1 then aNext:=[op(aNext),nPrev+2*N-1] fi;
%p A272568            if nCol+1<= N then aNext:=[op(aNext),nPrev+2*N+1] fi;
%p A272568 end if;
%p A272568 for nNext in aNext do
%p A272568    if nNext<1 or nNext>nCells or (nNext in gg) then next fi;
%p A272568    g2:=[op(g2),[op(gg),nNext]];
%p A272568 end do:
%p A272568      end do:
%p A272568      g1:=g2;
%p A272568   end do:
%p A272568 #output: comment this block if output is not required
%p A272568   if N>=3 and N<=5 then
%p A272568      hh:=fopen(cat("KnightPaths_",N,".txt"),WRITE);
%p A272568      for n from 1 to nops(g1) do
%p A272568         fprintf(hh,"%4d: %s\n",n,convert(g1[n],string));
%p A272568      end do:
%p A272568      fclose(hh);
%p A272568   end if;
%p A272568   return nops(g1);
%p A272568 end proc:
%p A272568 lis:=[seq(pathCount(N),N=1..7)];
%Y A272568 Cf. A272469.
%K A272568 nonn,walk,more
%O A272568 1,3
%A A272568 _César Eliud Lozada_, May 02 2016
%E A272568 a(9)-a(15) from _Giovanni Resta_, May 03 2016
%E A272568 a(16)-a(18) from _Bert Dobbelaere_, Jan 08 2019