A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424

Offset: 0

Author

Giovanni Resta, May 06 2016

Keywords

• nonn
• walk
• more

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

Crossrefs

Cf. A272763, A001411, A323140, A323141.

Programs

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

Extensions

a(5)-a(7) corrected by Rainer Rosenthal, Jan 06 2019

a(8)-a(16) from Hugo Pfoertner, Jan 06 2019