|
ChessKingPaths := proc(N, aUsed:=[1])
local nLast, nPrev, nNext, i, j, i1, j1, i2, j2:
global aPath, nPaths;
if N=1 then
aPath:=[[1]]; nPaths:=1; return nPaths;
end if:
if aUsed=[1] then
aPath:=[]; nPaths:=0;
end if;
nLast:=N^(2); #`opposite corner`
nPrev := aUsed[-1] ; #actual position
#Check all possible next cells
i1:=`if`(floor((nPrev-1)/N)=0, 0, -N); i2:=`if`(floor((nPrev-1)/N)=N-1, 0, N);
j1:=`if`((nPrev-1)mod N=0, 0, -1); j2:=`if`((nPrev-1) mod N=N-1, 0, 1);
for i from i1 to i2 by N do
for j from j1 to j2 by 1 do
if i=0 and j=0 then next fi; #`no move`
nNext:=nPrev+i+j;
#`out of bounds or already visited`
if nNext<1 or nNext>nLast or (nNext in aUsed) then next: fi;
#`nLast must be the last one`
if (nNext=nLast and nops(aUsed)<>nLast-1) then next fi:
if nNext=nLast and nops(aUsed)=nLast-1 then #`path completed`
#comment if list is not required. It will consume all memory for N>=5
aPath:=[op(aPath), [op(aUsed), nNext]];
nPaths:=nPaths+1;
break:
else
ChessKingPaths(N, [op(aUsed), nNext]) #move and continue
end if;
end do:
end do:
return nPaths;
end proc:
#For a(n) call this function with parameter n.
#Examples: ChessKingPaths(2), ChessKingPaths(3), ...
#The list of paths is stored in variable aPath.
| 