# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1576: The holly and the ivy and the…

From New Scientist #2739, 19th December 2009 [link]

This year I have designed my own Christmas card. It consists of 16 squares pasted onto a card in a closely packed 4-by-4 array. There are four pictures of holly, four of ivy, four of mistletoe and four of fir trees. There are four background colours of gold, silver, red or white, and every combination of plant and background colour (such as holly on a red background) can be found.

In each row and in each column of the array there is one square of each plant and one square of each background colour. In the top row the colours (from left to right) are gold, silver, red and white.

The holly on a gold background touches the ivy on a silver background, whereas no two mistletoe squares are touching, not even at their corners. One row begins with a fir tree on a white background.

What (in order) are the other three squares in that row?

[enigma1576]

### One response to “Enigma 1576: The holly and the ivy and the…”

1. jimrandell 12 February 2012 at 4:15 pm

The following Python program runs in 50ms.

```# the 4x4 grid is represented as a 16 element array

# generate possible colourings
def colours(C, n):
if n > 15:
return symbols(C)
(y, x) = divmod(n, 4)
for c in set(('G', 'S', 'R', 'W')).difference(C[x:n:4], C[y*4:n]):
C[n] = c
colours(C, n+1)

# place symbols
def symbols(C):
# "one row begins with a fir tree on a white background"
F0 = C[0:16:4].index('W', 1)*4
# "no two mistletoe squares are touching"
for M in ((1, 7, 8, 14), (2, 4, 11, 13)):
if F0 in M: continue
S = [''] * 16
S[F0] = 'F'
for i in M: S[i] = 'M'
_symbols(C, S, 0)

# generate possible symbol placements
def _symbols(C, S, n):
if n > 15:
return check(C, S)
if S[n]: return _symbols(C, S, n+1)
(y, x) = divmod(n, 4)
for s in set(('H', 'I', 'M', 'F')).difference(S[x:16:4], S[y*4:y*4+4]):
S[n] = s
_symbols(C, S, n+1)
S[n] = ''

# check for a solution
def check(C, S):
# pair the symbols and the colours
p = list(S[i] + C[i] for i in range(16))
# check we have all possible pairings
if len(set(p)) < 16: return
# "the holly on gold touches the ivy on silver"
(x1, y1) = divmod(p.index('HG'), 4)
(x2, y2) = divmod(p.index('IS'), 4)
if not(abs(x1 - x2) < 2 and abs(y1 - y2) < 2): return
# "what are the other three squares in that row [that begins with a fir tree on white]"
FW = p.index('FW')
print(*p[FW:FW+4])