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]

Advertisements

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
    def adjacent(i):
      (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
      def adjacent(i):
        (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)
    

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: