cp's OEIS Frontend

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

%I A272773 #23 Jan 07 2019 03:23:46
%S A272773 1,8,56,360,2240,13696,82808,496656,2961136,17573608,103911424,
%T A272773 612577272,3602222736,21137815952,123811421128,724064474968,
%U A272773 4228582808424
%N A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).
%C A272773 The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).
%C A272773 The Moore neighborhood characterizes king tours. - _Rainer Rosenthal_, Jan 06 2019
%p A272773 # For starting point stp and list Ldir of n directions (1..8)
%p A272773 # construct the points of the whole path and count them.
%p A272773 # In order to avoid crossings consider the n midpoints, too.
%p A272773 # If there are 2*n+1 then the path is self-avoiding and uncrossed.
%p A272773 isNice := proc(Ldir) local Delta, dir, ep, mp, path;
%p A272773    Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
%p A272773    ep := [0,0]; path := {ep};
%p A272773    for dir in Ldir do
%p A272773       mp := ep + Delta[dir];
%p A272773       ep := mp + Delta[dir];
%p A272773       path := {op(path), mp, ep};
%p A272773    od;
%p A272773    return evalb(nops(path)=2*nops(Ldir)+1);
%p A272773 end:
%p A272773 # Count only king tours which are nice, i.e. self-avoiding and uncrossed.
%p A272773 A272773 := proc(n) local count, T, p;
%p A272773    count := 0:
%p A272773    T := combinat[cartprod]([seq([$1..8], j=1..n)]):
%p A272773    while not T[finished] do
%p A272773       p := T[nextvalue]();
%p A272773       if isNice(p) then count := count+1; fi;
%p A272773    od:
%p A272773    return count;
%p A272773 end: # _Rainer Rosenthal_, Jan 06 2019
%t A272773 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 *)
%Y A272773 Cf. A272763, A001411, A323140, A323141.
%K A272773 nonn,walk,more
%O A272773 0,2
%A A272773 _Giovanni Resta_, May 06 2016
%E A272773 a(5)-a(7) corrected by _Rainer Rosenthal_, Jan 06 2019
%E A272773 a(8)-a(16) from _Hugo Pfoertner_, Jan 06 2019