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.

0, 0, 2, 20, 256, 2086, 16376, 121418, 871258, 6077730, 41586532, 280783434, 1875742356, 12432917916, 81868580330, 536476588416, 3501125753910, 22778101455784

Offset

1,3

Links

Table of n, a(n) for n=1..18.

César Eliud Lozada, List of paths for n=1..5

Maple

pathCount:=proc(N)
  local g1, g2, nStep, gg, nCells, nRow, nCol, nPrev, aNext, nNext, hh, n:
  nCells:=N^(2); g1:=[[1]];
  for nStep from 1 to N do
     g2:=[];
     for gg in g1 do
nPrev := gg[-1] ;
nRow:=1+floor((nPrev-1)/(N)); nCol:=1+((nPrev-1) mod N);
aNext:=[];
if nRow-2>=1 then
   if nCol-1>=1 then aNext:=[op(aNext), nPrev-2*N-1] fi;
   if nCol+1<= N then aNext:=[op(aNext), nPrev-2*N+1] fi;
end if;
if nRow-1>=1 then
   if nCol-2>=1 then aNext:=[op(aNext), nPrev-N-2] fi;
   if nCol+2<=N then aNext:=[op(aNext), nPrev-N+2] fi;
end if;
if nRow+1<=N then
   if nCol-2>=1 then aNext:=[op(aNext), nPrev+N-2] fi;
   if nCol+2<=N then aNext:=[op(aNext), nPrev+N+2] fi;
end if;
if nRow+2<=N then
   if nCol-1>=1 then aNext:=[op(aNext), nPrev+2*N-1] fi;
           if nCol+1<= N then aNext:=[op(aNext), nPrev+2*N+1] fi;
end if;
for nNext in aNext do
   if nNext<1 or nNext>nCells or (nNext in gg) then next fi;
   g2:=[op(g2), [op(gg), nNext]];
end do:
     end do:
     g1:=g2;
  end do:
#output: comment this block if output is not required
  if N>=3 and N<=5 then
     hh:=fopen(cat("KnightPaths_", N, ".txt"), WRITE);
     for n from 1 to nops(g1) do
        fprintf(hh, "%4d: %s\n", n, convert(g1[n], string));
     end do:
     fclose(hh);
  end if;
  return nops(g1);
end proc:
lis:=[seq(pathCount(N), N=1..7)];

Crossrefs

Cf. A272469.

Sequence in context: A099976 A195157 A207151 * A229727 A325409 A155671

Adjacent sequences: A272565 A272566 A272567 * A272569 A272570 A272571

Keyword

nonn,walk,more

Author

César Eliud Lozada, May 02 2016

Extensions

a(9)-a(15) from Giovanni Resta, May 03 2016

a(16)-a(18) from Bert Dobbelaere, Jan 08 2019

Status

approved