# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1767: Not over easy

From New Scientist #2935, 21st September 2013 [link]

Joe always likes his fried eggs sunny side up. During breakfast in a motel in North Carolina he was given 36 cards, printed on one side with the motel’s name and address, and on the other with two eggs sunny side up. With the cards were instructions to place them on the table one by one and sunny side up to try to make a 6×6 array with all cards sunny side up. As always with puzzles, there was a catch. If, as a card was placed, it touched edge to edge one or more cards, those cards had to be turned over. In solving the puzzle, Joe placed as many cards sunny side up as was possible.

How many did he manage?

[enigma1767]

### 3 responses to “Enigma 1767: Not over easy”

1. Jim Randell 19 September 2013 at 9:07 am

This Python program considers a grid of 0 (card placed sunny side up), 1 (card placed sunny side down) and None (card not placed). It works backwards by starting with a grid entirely filled out with 0’s (the required finishing position), and then removes a 0 at each step (flipping any adjacent values), until the grid is empty. At which point the reverse of this sequence of moves will generate the finishing position starting from an empty grid. There are many solutions, so this program exits after it has found the first one. It runs in 32ms.

I was going to write code to consider other possible finishing positions, but that seems to not be necessary. The code will also generate move sequences for N×N squares when N is specified on the command line.

```from enigma import irange

import sys
N = 6 if len(sys.argv) < 2 else int(sys.argv[1])
N2 = N * N

# compute the adjacency matrix
(y, x) = divmod(i, N)
a = list()
if x > 0: a.append(i - 1)
if y > 0: a.append(i - N)
if x < N - 1: a.append(i + 1)
if y < N - 1: a.append(i + N)
return tuple(a)

adj = list(adjacent(i) for i in irange(0, N2 - 1))

# remove a zero from g, and flip any adjacent values
def assign(g, i):
g = list(g)
g[i] = None
for j in adj[i]:
if g[j] is not None: g[j] ^= 1
return g

class Solved(Exception): pass

# g - grid to solve
# n - number remaining to remove
# s - sequence of moves to solve
def solve(g, n, s):
if n == 0:
raise Solved(s)
else:
# find the zeroes
z = list(i for (i, x) in enumerate(g) if x == 0)
# attempt to remove each one
for i in z:
solve(assign(g, i), n - 1, [i] + s)

# initial grid
g = [0] * N2
try:
solve(g, N2, [])
except Solved as e:
print(e)
```

Solution: Joe managed to place all 36 cards sunny side up.

• Jim Randell 25 September 2013 at 9:30 am

Again working backwards from a fully completed grid we see that each time we remove a card labelled 0 we must flip the cards adjacent to it along the shared edges. For each shared edge the card on one side of it is flipped when card on the other side is removed (and then the edge is no longer shared between cards). So we can see that the number of cards flipped in a complete solution is equal to the number of shared edges in the initial grid.

In order to remove a card it must be showing 0 (“sunny side up”), and so have undergone an even number of flips. So if we take the specific case of the final card it will be displaying 0 only if there was initially an even number of shared edges in the grid. If there was an odd number, it will be displaying 1, and cannot be removed. Meaning that it is not possible to achieve a maximal solution on a grid with an odd number shared edges.

Considering a general N×M grid, there are M×(N – 1) vertical shared edges and N×(M – 1) horizontal shared edges.

In the case where N and M are the same parity (including a square grid, where M = N, as in the original puzzle), both these numbers are even, so there is an even number of shared edges and a maximal solution may be possible. But in the case where N and M have different parities the total number of shared edges is odd and so a maximal solution will not be possible, but a solution where all but one of the cards is showing 0 may be possible.

Below is a minor modification of my original program to solve for the general N×M problem. In the case when N and M have different parities the solution grid is set up with one corner displaying 1 (“sunny side down”), so it searches for a solution with NM – 1 cards placed sunny side up. I’ve not proved that it will always find a solution, but in my experimentation it always has.

```from enigma import irange, printf

import sys
N = 6 if len(sys.argv) < 2 else int(sys.argv[1])
M = N if len(sys.argv) < 3 else int(sys.argv[2])
NM = N * M

# compute the adjacency matrix
(y, x) = divmod(i, N)
a = list()
if x > 0: a.append(i - 1)
if y > 0: a.append(i - N)
if x < N - 1: a.append(i + 1)
if y < M - 1: a.append(i + N)
return tuple(a)

adj = list(adjacent(i) for i in irange(0, NM - 1))

# remove a zero from g, and flip any adjacent values
def assign(g, i):
g = list(g)
g[i] = None
for j in adj[i]:
if g[j] is not None: g[j] ^= 1
return g

class Solved(Exception): pass

# g - grid to solve
# n - number remaining to remove
# s - sequence of moves to solve
def solve(g, n, s):
if n == 0:
raise Solved(s)
else:
# find the zeroes
z = list(i for (i, x) in enumerate(g) if x == 0)
# attempt to remove each one
for i in z:
solve(assign(g, i), n - 1, [i] + s)

# initial grid
g = [0] * NM
if (N % 2) != (M % 2): g[0] = 1
n = g.count(0)

try:
solve(g, NM, [])
except Solved as e:
printf("{n}: {e}")
```

Note: If you want to explore “large grids” (of around 900 cards or more) you will need to increase Python’s default recursion limit. Add the following at line 7:

```sys.setrecursionlimit(10000)
```
2. Brian Gladman 19 September 2013 at 9:15 pm

I copied your neat exit method Jim.

```# After a card has been placed on the table it will be
# turned over by each edge that will in future have a
# card placed next to it.  So cards can only be placed
# in positions in which an even number of their edges
# will be 'exposed' in this way.

# create the initial number of exposed edges for each
# card and a list of card positions adjacent to it
def init(N):
m = []
# for each position in the N by N grid
for k in range(N * N):
# the column and row positions
j, i = divmod(k, N)
# adjacent card indexes (t) and exposed edges (u)
t, u = tuple(), 4
# inner cards have 4 exposed edges, corner cards
# have two and edge cards have three
if j in (0, N - 1):
u = 2 if i in (0, N - 1) else 3
if i in (0, N - 1):
u = 2 if j in (0, N - 1) else 3
# compile a tuple of adjacent card positions
if j:
t += (k - N,)
if j < N - 1:
t += (k + N,)
if i:
t += (k - 1,)
if i < N - 1:
t += (k + 1,)
m += [(u, t)]
return m

def place(grid, seq, m, N):
# if all cards are 'sunny side' up
if all(v == 1 for v in grid):
# terminate the recursion and return the result
raise StopIteration(seq)
else:
# look for an empty cell
for k, v in enumerate(grid):
if not v:
# calculate its number of exposed edges
e = m[k][0] - sum(1 for i in m[k][1] if grid[i])
# if this is even we can place a card here
if not e % 2:
break
else:
return
# place the next card
g = grid[:]
g[k] = 1
# turn over adjacent cards
for i in m[k][1]:
g[i] *= -1
# and place further cards
place(g, seq + [k], m, N)

# set up initial grid and card data
N = 6
m = init(N)
grid = [0] * (N * N)
try:
# try to place cards
place(grid, [], m, N)
except StopIteration as seq:
print(seq)
```