A300665
Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
Original entry on oeis.org
1, 3, 15, 75, 391, 2065, 11091, 60215, 330003, 1820869, 10103153, 56313047, 315071801, 1768489771, 9953853677, 56158682949, 317505199769, 1798402412539
Offset: 0
For n=2, the a(2)=15 paths are:
.
. 0 . . 0 . . 0 . . 0 2 . 0 . .
. | | | |/ \
. 1 . . 1 . . 1-2 . 1 . . 2-1 .
. | \
. 2 . . . 2 . . . . . . . . . .
.
. 0 . . 0 . . 0 . . 0 . . 0 . 2
. \ \ \ \ \ /
. . 1 . . 1 . . 1 . . 1-2 . 1 .
. / | \
. 2 . . . 2 . . . 2 . . . . . .
.
. 0 2 . 0-1 . 0-1 . 0-1 . 0-1-2
. \| / | \
. . 1 . 2 . . . 2 . . . 2 . . .
.
. . . . . . . . . . . . . . . .
A038373 is the same process, but using only horizontal and vertical moves.
-
(see GitHubGist link)
-
next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s,#] &]
nextpath[p_]:=Outer[Append,{p},valid[p],1]
iterate[p_]:=Flatten[Map[nextpath, p], 2]
Table[Length[Nest[iterate, {{{0,0}}}, n-1]], {n,1,7}]
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.
Original entry on oeis.org
0, 0, 2, 20, 256, 2086, 16376, 121418, 871258, 6077730, 41586532, 280783434, 1875742356, 12432917916, 81868580330, 536476588416, 3501125753910, 22778101455784
Offset: 1
-
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)];
Showing 1-2 of 2 results.
Comments