OFFSET
0,2
COMMENTS
Moore neighborhood :
o o o
o x o
o o o
Von Neumann neighborhood (A001411):
o
o x o
o
Note that the path avoids already visited lattice points, but can intersect itself (two diagonal steps). A nonintersecting version is A272773.
The Moore neighborhood characterizes king tours. # Rainer Rosenthal, Jan 05 2019
MAPLE
# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# If there are n+1 then the path is self-avoiding.
isSelfAvoiding := proc(Ldir) local Delta, dir, ep, 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
ep := ep + Delta[dir];
path := {op(path), ep};
od;
return evalb(nops(path)=nops(Ldir)+1);
end:
# Count only king tours which are self-avoiding
A272763 := 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 isSelfAvoiding(p) then count := count+1; fi;
od:
return count;
end: # Rainer Rosenthal, Jan 05 2019
MATHEMATICA
mo=Most@Tuples[{-1, 1, 0}, 2]; a[0]=1; a[tg_, p_: {{0, 0}}] := Block[{e, mv = Complement[Last[p] + # & /@ mo, p]}, If[tg == 1, Length@mv, Sum[a[tg - 1, Append[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Giovanni Resta, May 06 2016 *)
CROSSREFS
KEYWORD
nonn,walk,more
AUTHOR
Francois Alcover, May 05 2016
EXTENSIONS
a(13)-a(16) from Giovanni Resta, May 06 2016
STATUS
approved