cp's OEIS Frontend

A204092 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution.

%I A204092 #22 May 22 2025 10:21:35
%S A204092 1,3,17,91,449,2123,9841,45211,206881,945003,4313297,19680571,
%T A204092 89784449,409577483,1868351281,8522666971,38876763361,177338745003,
%U A204092 808940722577,3690027171451,16832256509249,76781232397643,350241657358321,1597645838773531,7287745912705441
%N A204092 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution.
%C A204092 Requiring the last slot contain a mirror results in A204091.  Fixing orientation of mirrors results in A204090.  Fixing orientation and requiring the last slot be a mirror results in A204089.
%H A204092 Samples of these types of puzzles can be found at <a href="http://thegriddle.net/tags/haunted">this site</a>.
%H A204092 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (8,-19,16,-4).
%F A204092 a(n) = A204091(n+1)/2 - 2^(n+1) + 2.
%F A204092 a(n) = 8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4), a(0) = 1, a(1) = 3, a(2) = 17, a(3) = 91.
%F A204092 G.f.: (1-5x+12x^2-4x^3)/((1-x)(1-2x)(1-5x+2x^2)).
%e A204092 The following 17 boards illustrate K(2):
%e A204092 ('Z', '/')
%e A204092 ('Z', '|')
%e A204092 ('V', '/')
%e A204092 ('V', '|')
%e A204092 ('G', 'G')
%e A204092 ('G', '/')
%e A204092 ('G', '|')
%e A204092 ('/', 'Z')
%e A204092 ('/', 'V')
%e A204092 ('/', 'G')
%e A204092 ('/', '/')
%e A204092 ('/', '|')
%e A204092 ('|', 'Z')
%e A204092 ('|', 'V')
%e A204092 ('|', 'G')
%e A204092 ('|', '/')
%e A204092 ('|', '|')
%t A204092 LinearRecurrence[{8, -19, 16, -4}, {1, 3, 17, 91}, 40]
%o A204092 (Python)
%o A204092 def a(n, d={0:1,1:3,2:17,3:91}):
%o A204092  if n in d:
%o A204092   return d[n]
%o A204092  d[n]=8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4)
%o A204092  return d[n]
%o A204092 (Python)
%o A204092 #Produces a(n) through enumeration and also displays boards:
%o A204092 def Kprint(n):
%o A204092  print('The following generate boards with a unique solution')
%o A204092  s=0
%o A204092  for x in product(['Z','V','G','/','|'],repeat=n):
%o A204092   #Taking care of the no mirror case
%o A204092   if '/' not in x and '|' not in x:
%o A204092    if 'Z' not in x and 'V' not in x:
%o A204092     s+=1
%o A204092     print(x)
%o A204092   else:
%o A204092    #Splitting x up into a list pieces
%o A204092    y=list(x)
%o A204092    z=list()
%o A204092    while y:
%o A204092     if '/' in y or '|' in y:
%o A204092      if '/' in y and '|' in y:
%o A204092       m = min(y.index('/'), y.index('|'))
%o A204092      else:
%o A204092       if '/' in y:
%o A204092        m=y.index('/')
%o A204092       else:
%o A204092        m=y.index('|')
%o A204092      if y[0] not in ['/','|']: #Don't need to add blank pieces to z
%o A204092       z.append(y[:m])
%o A204092      y=y[m+1:]
%o A204092     else:
%o A204092      z.append(y)
%o A204092      y=[]
%o A204092    #For each element in the list checking for Z&V together
%o A204092    goodword=True
%o A204092    for w in z:
%o A204092     if 'Z' in w and 'V' in w:
%o A204092      goodword=False
%o A204092    if goodword:
%o A204092     s+=1
%o A204092     print(x)
%o A204092  return s
%Y A204092 Cf. A204089, A204090, A204091.
%K A204092 nonn,easy
%O A204092 0,2
%A A204092 _David Nacin_, Jan 10 2012