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]

Advertisements

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])
    
    # start with the first row of colours
    colours([ 'G', 'S', 'R', 'W' ] + ['']*12, 4)
    

    Solution: The other three squares on that row are: Holly on a Red background, Ivy on a Silver background and Mistletoe on a Gold background.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: