Enigmatic Code

Programming Enigma Puzzles

Enigma 1586: So touching

From New Scientist #2751, 13th March 2010 [link]

Joe has a special set of white counters numbered on one face 1, 2 or 3 and some of them have the other face coloured green. To test Penny’s logic skills, he placed 36 of his special counters on the table to form a 6 by 6 grid (see right). The number on the top face of a counter indicates the number of counters touching it that have a green lower face. Penny had to find which had green faces.

Numbering the rows and columns from the top-left corner, in which columns are the green-faced counters in the third row?

[enigma1586]

Advertisements

One response to “Enigma 1586: So touching

  1. jimrandell 29 January 2012 at 6:01 pm

    This Python program runs in 37ms:

    import copy
    
    # number grid
    number = [
      [ 2, 1, 1, 2, 1, 2 ],
      [ 1, 3, 3, 2, 3, 1 ],
      [ 2, 3, 2, 2, 3, 2 ],
      [ 2, 1, 3, 2, 1, 2 ],
      [ 1, 3, 1, 1, 2, 2 ],
      [ 1, 2, 1, 1, 1, 1 ]
    ]
    
    # empty colour grid
    colour = [ [None] * 6 for i in range(6) ]
    
    # return a list of the touching pieces
    def touch(i, j):
      r = []
      if i > 0: r.append((i-1, j)) # left
      if i < 5: r.append((i+1, j)) # right
      if j > 0: r.append((i, j-1)) # up
      if j < 5: r.append((i, j+1)) # down
      return r
    
    # fill out uncoloured items in t
    def fill(t, c):
      for (i, j) in t:
        if colour[i][j] is not None: continue
        colour[i][j] = c
    
    # fill out any colours that are fully determined
    def complete():
      progress = False
      for i in range(6):
        for j in range(6):
          # compute the number of touching counters
          t = touch(i, j)
          c = list(colour[x][y] for x, y in t)
    
          # all filled out?
          if None not in c: continue
    
          # should the remaining squares all be not green?
          if c.count(1) == number[i][j]:
            fill(t, 0)
            progress = True
    
          # should the remaining squares all be green?
          elif len(t) - c.count(0) == number[i][j]:
            fill(t, 1)
            progress = True
    
      return progress
    
    def check():
      # check that this is a solution
      for i in range(6):
        for j in range(6):
          # count the number of greens
          n = sum(colour[x][y] for x, y in touch(i, j))
          if not n == number[i][j]: return False
      return True
    
    def output():
      # colouring
      for x in range(6):
        print(''.join('.G'[y] for y in colour[x]))
      # which counters are green in the third row?
      print(list(x+1 for x in range(6) if colour[2][x]))
    
    # attempt to solve the grid
    def solve():
      global colour
      while True:
        # fill out predetermined values
        while complete(): pass
        # are we done?
        for i in range(6):
          for j in range(6):
            if colour[i][j] is not None: continue
            for c in (0, 1):
              colour2 = copy.deepcopy(colour)
              # try the guess
              colour[i][j] = c
              if solve():
                if check():
                  return True
              # restore the previous version
              colour = colour2
            return False
        return check()
    
    if solve():
      output()
    

    Solution: The green faced counters in row 3 are in columns 2, 3 and 4.

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: