A272773 - OEIS

%I #23 Jan 07 2019 03:23:46

%S 1,8,56,360,2240,13696,82808,496656,2961136,17573608,103911424,

%T 612577272,3602222736,21137815952,123811421128,724064474968,

%U 4228582808424

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

%C The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).

%C The Moore neighborhood characterizes king tours. - _Rainer Rosenthal_, Jan 06 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 # In order to avoid crossings consider the n midpoints, too.

%p # If there are 2*n+1 then the path is self-avoiding and uncrossed.

%p isNice := proc(Ldir) local Delta, dir, ep, mp, 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       mp := ep + Delta[dir];

%p       ep := mp + Delta[dir];

%p       path := {op(path), mp, ep};

%p    od;

%p    return evalb(nops(path)=2*nops(Ldir)+1);

%p end:

%p # Count only king tours which are nice, i.e. self-avoiding and uncrossed.

%p A272773 := 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 isNice(p) then count := count+1; fi;

%p    od:

%p    return count;

%p end: # _Rainer Rosenthal_, Jan 06 2019

%t 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 Cf. A272763, A001411, A323140, A323141.

%K nonn,walk,more

%O 0,2

%A _Giovanni Resta_, May 06 2016

%E a(5)-a(7) corrected by _Rainer Rosenthal_, Jan 06 2019

%E a(8)-a(16) from _Hugo Pfoertner_, Jan 06 2019