A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

1, 8, 56, 368, 2336, 14576, 89928, 550504, 3349864, 20290360, 122445504, 736685008, 4421048016, 26475370088, 158257613848, 944493430152, 5628996811904

Offset: 0

Author

Francois Alcover, May 05 2016

Keywords

• nonn
• walk
• more

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

Crossrefs

Cf. A001411, A272773, A300665.

Programs

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 *)

Extensions

a(13)-a(16) from Giovanni Resta, May 06 2016