OFFSET
0,2
COMMENTS
The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).
The Moore neighborhood characterizes king tours. - Rainer Rosenthal, Jan 06 2019
MAPLE
# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# In order to avoid crossings consider the n midpoints, too.
# If there are 2*n+1 then the path is self-avoiding and uncrossed.
isNice := proc(Ldir) local Delta, dir, ep, mp, path;
Delta := [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]];
ep := [0, 0]; path := {ep};
for dir in Ldir do
mp := ep + Delta[dir];
ep := mp + Delta[dir];
path := {op(path), mp, ep};
od;
return evalb(nops(path)=2*nops(Ldir)+1);
end:
# Count only king tours which are nice, i.e. self-avoiding and uncrossed.
A272773 := proc(n) local count, T, p;
count := 0:
T := combinat[cartprod]([seq([$1..8], j=1..n)]):
while not T[finished] do
p := T[nextvalue]();
if isNice(p) then count := count+1; fi;
od:
return count;
end: # Rainer Rosenthal, Jan 06 2019
MATHEMATICA
mo = Most@Tuples[{-1, 1, 0}, 2]; a[0] = 1; a[tg_, p_: {{0, 0}}] := Block[{e, z = Last@p, w, mv = {}}, Do[w = {z+e, z+2*e}; If[Intersection[w, p] == {}, AppendTo[mv, w]], {e, mo}]; If[tg == 1, Length[mv], Sum[a[tg-1, Join[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Corrected following a suggestion by Rainer Rosenthal, Giovanni Resta, Jan 06 2019 *)
CROSSREFS
KEYWORD
nonn,walk,more
AUTHOR
Giovanni Resta, May 06 2016
EXTENSIONS
a(5)-a(7) corrected by Rainer Rosenthal, Jan 06 2019
a(8)-a(16) from Hugo Pfoertner, Jan 06 2019
STATUS
approved