# 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).