OFFSET
0,2
COMMENTS
LINKS
Samples of these types of puzzles can be found at this site.
Index entries for linear recurrences with constant coefficients, signature (8,-19,16,-4).
FORMULA
a(n) = A204091(n+1)/2 - 2^(n+1) + 2.
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.
G.f.: (1-5x+12x^2-4x^3)/((1-x)(1-2x)(1-5x+2x^2)).
EXAMPLE
The following 17 boards illustrate K(2):
('Z', '/')
('Z', '|')
('V', '/')
('V', '|')
('G', 'G')
('G', '/')
('G', '|')
('/', 'Z')
('/', 'V')
('/', 'G')
('/', '/')
('/', '|')
('|', 'Z')
('|', 'V')
('|', 'G')
('|', '/')
('|', '|')
MATHEMATICA
LinearRecurrence[{8, -19, 16, -4}, {1, 3, 17, 91}, 40]
PROG
(Python)
def a(n, d={0:1, 1:3, 2:17, 3:91}):
.if n in d:
..return d[n]
.d[n]=8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4)
.return d[n]
(Python)
#Produces a(n) through enumeration and also displays boards:
def Kprint(n):
.print('The following generate boards with a unique solution')
.s=0
.for x in product(['Z', 'V', 'G', '/', '|'], repeat=n):
..#Taking care of the no mirror case
..if '/' not in x and '|' not in x:
...if 'Z' not in x and 'V' not in x:
....s+=1
....print(x)
..else:
...#Splitting x up into a list pieces
...y=list(x)
...z=list()
...while y:
....if '/' in y or '|' in y:
.....if '/' in y and '|' in y:
......m = min(y.index('/'), y.index('|'))
.....else:
......if '/' in y:
.......m=y.index('/')
......else:
.......m=y.index('|')
.....if y[0] not in ['/', '|']: #Don't need to add blank pieces to z
......z.append(y[:m])
.....y=y[m+1:]
....else:
.....z.append(y)
.....y=[]
...#For each element in the list checking for Z&V together
...goodword=True
...for w in z:
....if 'Z' in w and 'V' in w:
.....goodword=False
...if goodword:
....s+=1
....print(x)
.return s
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David Nacin, Jan 10 2012
STATUS
approved