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

Author

César Eliud Lozada, May 02 2016

Keywords

• nonn
• walk
• more

Links

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

Crossrefs

Cf. A272469.

Programs

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)];

Extensions

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

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