Enigmatic Code

Programming Enigma Puzzles

Enigma 54: Grid halving

notableFrom New Scientist #1197, 6th March 1980 [link]

Enigma 54“Cut the figure to make two identical parts” is a problem put in 100 Geometric Games, by Pierre Berloquin, which I have been reading. Having done so — not without difficulty — I looked up the solution and found it was quite different from mine.

Interpreting “identical” as including “identical when turned over”, how many ways can you find of cutting the figure into two identical parts?

[enigma54]

Advertisements

One response to “Enigma 54: Grid halving

  1. Jim Randell 7 February 2013 at 8:28 pm

    This is one that I’ve not been able to fully solve programatically in a satisfactory way. But by considering a simplified version of the problem I am able to find the required solutions in a reasonable time.

    The following Python program assumes that the cut divides the figure along the grid lines shown in to two contiguous pieces, and further instead of considering the full 10×6 grid (48 squares) it considers a scaled down 5×3 grid (12 squares). Any solution thus found can obviously be scaled up to become a solution of the original problem. This program runs in 41ms.

    from enigma import printf
    
    # label the pieces:
    # [XX][11][12][13][14]
    # [XX][ 6][ 7][ 8][ 9]
    # [ 0][ 1][ 2][ 3][XX]
    
    # then the adjacency matrix is:
    adj = {
      0: (1,),
      1: (0, 2, 6),
      2: (1, 3, 7),
      3: (2, 8),
      6: (1, 7, 11),
      7: (2, 6, 8, 12),
      8: (3, 7, 9, 13),
      9: (8, 14),
      11: (6, 12),
      12: (7, 11, 13),
      13: (8, 12, 14),
      14: (9, 13),
    }
    
    # extract a shape from a grid
    def extract(g, c):
      s = []
      for r in g:
        s.append(list('#' if c == i else ' ' for i in r))
      # prune away unused elements
      while '#' not in s[0]:
        s.pop(0)
      while '#' not in s[-1]:
        s.pop(-1)
      while '#' not in list(t[0] for t in s):
        for t in s: t.pop(0)
      while '#' not in list(t[-1] for t in s):
        for t in s: t.pop(-1)
      # return the shape
      return s
    
    # rotate a shape
    def rotate(s):
      r = [[] for i in range(len(s[0]))]
      for t in s:
        for (i, c) in enumerate(reversed(t)):
          r[i].append(c)
      return r
    
    # mirror a shape
    def mirror(s):
      return list(list(reversed(t)) for t in s)
    
    # check for a solution
    def check(ps, ss):
      # plot the shape on a 5 x 3 grid
      g = [ [-1] * 5 for i in range(3) ]
    
      for p in adj.keys():
        j, i = divmod(p, 5)
        g[j][i] = 1 if p in ps else 0
    
      # extract the shape
      s1 = extract(g, 1)
      # and its rotations
      s2 = rotate(s1)
      s3 = rotate(s2)
      s4 = rotate(s3)
      # and mirror images
      m1 = mirror(s1)
      m2 = mirror(s2)
      m3 = mirror(s3)
      m4 = mirror(s4)
      # extract the remaining shape
      s0 = extract(g, 0)
      # is it the same?
      if s0 not in (s1, s2, s3, s4, m1, m2, m3, m4): return
    
      s = max(s1, s2, s3, s4, m1, m2, m3, m4)
      if s in ss: return
      ss.append(s)
    
      # print the grid
      for r in g:
        print(''.join(' .X'[i + 1] for i in r))
      print()
    
    def solve(ps, ss):
      # have we selected half the grid?
      if len(ps) == 6:
        check(ps, ss)
        return
      # add in an adjacent piece
      for p in set().union(*(adj[p] for p in ps)).difference(ps):
        solve(ps + [p], ss)
    
    ss = []
    solve([0], ss)
    printf("{n} solutions found", n=len(ss))
    

    Solution: There are three different ways.

    Enigma 54 - Solution 1

    Enigma 54 - Solution 2

    Enigma 54 - Solution 3

    There is also a solution that uses non-contiguous regions.

    Enigma 54 - Solution 4

    I’ve played with some variations on the above program to attempt the more general problem, but the best I’ve come up with is a program to analyse possible cuts along the grid lines. On the 10×6 grid it examined 34,885,420 cuts in 5h37m, and found the same (contiguous) solutions given above.

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: