cp's OEIS Frontend

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

%I A272763 #18 Jan 05 2019 18:33:29
%S A272763 1,8,56,368,2336,14576,89928,550504,3349864,20290360,122445504,
%T A272763 736685008,4421048016,26475370088,158257613848,944493430152,
%U A272763 5628996811904
%N A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).
%C A272763 Moore neighborhood :
%C A272763 o o o
%C A272763 o x o
%C A272763 o o o
%C A272763 Von Neumann neighborhood (A001411):
%C A272763   o
%C A272763 o x o
%C A272763   o
%C A272763 Note that the path avoids already visited lattice points, but can intersect itself (two diagonal steps). A nonintersecting version is A272773.
%C A272763 The Moore neighborhood characterizes king tours. # _Rainer Rosenthal_, Jan 05 2019
%p A272763 # For starting point stp and list Ldir of n directions (1..8)
%p A272763 # construct the points of the whole path and count them.
%p A272763 # If there are n+1 then the path is self-avoiding.
%p A272763 isSelfAvoiding := proc(Ldir) local Delta, dir, ep, path;
%p A272763    Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
%p A272763    ep := [0,0]; path := {ep};
%p A272763    for dir in Ldir do
%p A272763       ep := ep + Delta[dir];
%p A272763       path := {op(path), ep};
%p A272763    od;
%p A272763    return evalb(nops(path)=nops(Ldir)+1);
%p A272763 end:
%p A272763 # Count only king tours which are self-avoiding
%p A272763 A272763 := proc(n) local count, T, p;
%p A272763    count := 0:
%p A272763    T := combinat[cartprod]([seq([$1..8], j=1..n)]):
%p A272763    while not T[finished] do
%p A272763       p := T[nextvalue]();
%p A272763       if isSelfAvoiding(p) then count := count+1; fi;
%p A272763    od:
%p A272763    return count;
%p A272763 end: # _Rainer Rosenthal_, Jan 05 2019
%t A272763 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 *)
%Y A272763 Cf. A001411, A272773, A300665.
%K A272763 nonn,walk,more
%O A272763 0,2
%A A272763 _Francois Alcover_, May 05 2016
%E A272763 a(13)-a(16) from _Giovanni Resta_, May 06 2016