Enigmatic Code

Programming Enigma Puzzles

Enigma 1616: One good turn

From New Scientist #2781, 9th October 2010 [link]

Joe’s 3-by-3 grid can be made to represent any of the six faces of a die by placing nine counters, coloured on one side and white on the other. Joe placed the nine counters with just the one in the centre coloured side up. Penny’s task this week is to increase the number represented to 4 by turning over counters. But, of course, there is a catch. Every time Penny decides which counter to turn over she has to remember to turn over all counters in squares that are immediately adjacent, horizontally and vertically. Not only that, she has to record how many counters she turns over each time, and the total has to be the minimum possible.

What is that minimum?

[enigma1616]

Advertisements

One response to “Enigma 1616: One good turn

  1. jimrandell 28 December 2011 at 4:13 pm

    The following Python program does a breadth first search to find the minimum number of flips required to reach all possible outcomes from the starting position. It runs in 4.3s (2.0s under PyPy).

    start  = "000" + "010" + "000"
    finish = "101" + "000" + "101"
    
    # actually, due to symmetry we only need to consider first moves of a corner, edge and centre
    r0 = list(map(str, (0, 1, 4)))
    r1 = list(map(str, range(9)))
    
    # track the minimum number of moves to get to a certain position
    mc = {}
    
    # initiate a breadth first search
    def search(l):
      while len(l) > 0:
        n = []
        for p, m, c in l:
          if p in mc:
            if mc[p] < c: continue # we already have a lower min for this position
          else:
            mc[p] = c
          if p != finish:
            # try each turn
            for s in (r0 if len(l) == 1 else r1):
              if len(m) > 0 and m[-1] == s: continue
              n.append(flip(p, m, c, s))
        l = n
    
    # do a flip
    
    f = { '0': '1', '1': '0' }
    
    def flip(p, m, c, s):
      p0, p1, p2, p3, p4, p5, p6, p7, p8 = p
      if   s == '0':
        return ( f[p0] + f[p1] +   p2  + f[p3] +   p4  +   p5  +   p6  +   p7  +   p8,  m + s, c + 3 )
      elif s == '1':
        return ( f[p0] + f[p1] + f[p2] +   p3  + f[p4] +   p5  +   p6  +   p7  +   p8,  m + s, c + 4 )
      elif s == '2':
        return (   p0  + f[p1] + f[p2] +   p3  +   p4  + f[p5] +   p6  +   p7  +   p8,  m + s, c + 3 )
      elif s == '3':
        return ( f[p0] +   p1  +   p2  + f[p3] + f[p4] +   p5  + f[p6] +   p7  +   p8,  m + s, c + 4 )
      elif s == '4':
        return (   p0  + f[p1] +   p2  + f[p3] + f[p4] + f[p5] +   p6  + f[p7] +   p8,  m + s, c + 5 )
      elif s == '5':
        return (   p0  +   p1  + f[p2] +   p3  + f[p4] + f[p5] +   p6  +   p7  + f[p8], m + s, c + 4 )
      elif s == '6':
        return (   p0  +   p1  +   p2  + f[p3] +   p4  +   p5  + f[p6] + f[p7] +   p8,  m + s, c + 3 )
      elif s == '7':
        return (   p0  +   p1  +   p2  +   p3  + f[p4] +   p5  + f[p6] + f[p7] + f[p8], m + s, c + 4 )
      elif s == '8':
        return (   p0  +   p1  +   p2  +   p3  +   p4  + f[p5] +   p6  + f[p7] + f[p8], m + s, c + 3 )
    
    # list of [ <current-pos>, <moves>, <count> ]
    search([(start, '', 0)])
    
    print("found {n} configurations".format(n=len(mc)))
    print("{p} => {m} flips".format(p=finish, m=mc[finish]))
    

    Solution: The minimum number of counters turned over is 33.

    You can also use this program to find the minimum number of flips required to reach other representations of dice faces (1 → 0 flips, 2 → 11 flips, 3 → 22 flips, 4 → 33 flips, 5 → 12 flips, 6 → 13 flips).

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: