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