**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]

### Like this:

Like Loading...

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.

Solution:Joe managed to place all 36 cards sunny side up.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.

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:I copied your neat exit method Jim.