Enigmatic Code

Programming Enigma Puzzles

Enigma 321: Going to pieces

From New Scientist #1469, 15th August 1985 [link]

I have a puzzle consisting of eight jigsaw type pieces. Each sturdy piece has been cut from a piece of card 2 inches by 3 inches, by removing one or more of the six 1 inch by 1 inch squares into which it can be divided. For example, one of the pieces is as shown:

Enigma 321

The card is the same on both sides and the pieces can be used either way up. For three-quarters of the pieces (like the one shown) this is no advantage, but the other pieces are different when turned over. No two pieces of the puzzle are the same.

The pieces can all be put together to form a large rectangle and, although this can be done by several different arrangements of the pieces, you can only get a large rectangle of one particular size.

What is the size of the large rectangular jigsaw which we can make?

[enigma321]

Advertisements

9 responses to “Enigma 321: Going to pieces

  1. Jim Randell 27 November 2015 at 9:02 am

    The published solution is that the rectangle is 3″ × 9″, and I have found 6 different collections of 8 pieces that can be assembled to make rectangles of (only) 3×9. But I have also found 2 different collections of 8 pieces that can be assembled to make rectangles of (only) 2×13.

    Here’s my Python program. It takes quite a long time to run to completion (5h56m).

    from itertools import combinations, product
    from copy import deepcopy
    from enigma import divisor_pairs, irange, printf
    
    # some pieces are "chiral" (different if flipped over)
    # and some are "achiral" (the same if flipped over)
    #
    # let's start with the achiral ones, and give each shape
    # in all possible orientations
    
    pieces = [
    
      # p0: 1 square - 1x1 block ["O1"]
      (
        [(0, 0)],
      ),
    
      # p1: 2 squares - 2x1 block ["I2"]
      (
        [(0, 0), (1, 0)],
        [(0, 0), (0, 1)],
      ),
    
      # p2: 3 squares - linear, 3x1 block ["I3"]
      (
        [(0, 0), (1, 0), (2, 0)],
        [(0, 0), (0, 1), (0, 2)],
      ),
    
      # p3: 3 squares - L shape ["V3"]
      (
        [(0, 0), (1, 0), (1, 1)],
        [(1, 0), (0, 1), (1, 1)],
        [(0, 0), (1, 0), (0, 1)],
        [(0, 0), (0, 1), (1, 1)],
      ),
    
      # p4: 4 squares - square, 2x2 block ["O4"]
      (
        [(0, 0), (1, 0), (0, 1), (1, 1)],
      ),
    
      # p5: 4 squares - T shape ["T4"]
      (
        [(1, 0), (0, 1), (1, 1), (2, 1)],
        [(0, 0), (0, 1), (1, 1), (0, 2)],
        [(0, 0), (1, 0), (2, 0), (1, 1)],
        [(1, 0), (0, 1), (1, 1), (1, 2)],
      ),
    
      # p6: 5 squares - U shape (as shown) ["U", "U5"]
      (
        [(0, 0), (0, 1), (1, 1), (2, 1), (2, 0)],
        [(0, 1), (0, 0), (1, 0), (2, 0), (2, 1)],
        [(1, 0), (0, 0), (0, 1), (0, 2), (1, 2)],
        [(0, 0), (1, 0), (1, 1), (1, 2), (0, 2)],
      ),
    
      # 6 squares, 3x2 block, is not used ["O6"]
    
      # and now the chiral ones
    
      # p7: 4 squares - S shape ["Z4"]
      (
        [(0, 0), (1, 0), (1, 1), (2, 1)],
        [(0, 1), (1, 1), (1, 0), (2, 0)],
        [(0, 0), (0, 1), (1, 1), (1, 2)],
        [(1, 0), (1, 1), (0, 1), (0, 2)],
      ),
    
      # p8: 4 squares - L shape ["L4"]
      (
        [(0, 0), (1, 0), (2, 0), (2, 1)],
        [(0, 1), (1, 1), (2, 1), (2, 0)],
        [(0, 0), (1, 0), (2, 0), (0, 1)],
        [(0, 1), (1, 1), (2, 1), (0, 0)],
        [(0, 0), (0, 1), (0, 2), (1, 2)],
        [(1, 0), (1, 1), (1, 2), (0, 2)],
        [(0, 0), (0, 1), (0, 2), (1, 0)],
        [(1, 0), (1, 1), (1, 2), (0, 0)],
      ),
    
      # p9: 5 squares - P shape ["P", "P5"]
      (
        [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1)],
        [(2, 0), (1, 0), (0, 0), (0, 1), (1, 1)],
        [(2, 1), (1, 1), (0, 1), (0, 0), (1, 0)],
        [(0, 1), (1, 1), (2, 1), (2, 0), (1, 0)],
        [(0, 2), (0, 1), (0, 0), (1, 0), (1, 1)],
        [(1, 2), (1, 1), (1, 0), (0, 0), (0, 1)],
        [(0, 0), (0, 1), (0, 2), (1, 2), (1, 1)],
        [(1, 0), (1, 1), (1, 2), (0, 2), (0, 1)],
      ),
    ]
    
    # try to place piece p at x, y in grid grid of dimensions a, b
    # using label n
    def place(p, y, x, n, grid, a, b):
      g = deepcopy(grid)
      for (dy, dx) in p:
        (py, px) = (y + dy, x + dx)
        try:
          q = g[py][px]
        except IndexError:
          return None
        if q is not None:
          return None
        g[py][px] = n
      return g
    
    # try to fit pieces ps into grid grid of dimensions a, b
    def fit(ps, n, grid, a, b):
      if not ps:
        yield grid
      else:
        # choose a piece
        for p in ps[0]:
          # try to place the piece at x, y
          for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
            g = place(p, y, x, n, grid, a, b)
            if g is not None:
              for r in fit(ps[1:], n + 1, g, a, b): yield r
    
    # choose 2 chiral pieces and 5 achiral pieces
    for (ps1, ps2) in product(combinations((7, 8, 9), 2), combinations((0, 1, 2, 3, 4, 5), 5)):
    
      # combine them, along with p6, to form the 8 pieces of the puzzle
      ps = ps1 + ps2 + (6,)
    
      # count the number of squares
      n = sum(len(pieces[i][0]) for i in ps)
      printf("\nn={n}, ps={ps}", ps=sorted(ps))
    
      # consider possible rectangles
      ds = list((a, b) for (a, b) in divisor_pairs(n) if not(a < 2 or b < 3))
      if len(ds) < 1: continue
      printf("possible rectangles = {ds}")
    
      d = 0
      for (a, b) in ds:
        printf("trying {a}x{b} ...")
    
        # create an a x b empty grid and assemble the pieces into it
        grid = list([None] * b for _ in irange(1, a))
        for g in fit(list(pieces[i] for i in ps), 1, grid, a, b):
          # output a completed grid
          for r in g:
            printf("{r}")
          printf()
          d += 1
          # we only need one way to complete the grid
          break
    
      # if there's only one completed grid then this is a solution
      if d == 1:
        printf("SOLUTION: n={n}, {a}x{b} rectangle\n")
    

    Each of the arrangements found can be broken into sub-rectangles which can be rotated and reassembled in a different order to give a different way to assemble the pieces (and many have non-rectangular sub-shapes that can be removed, re-assembled in a different way to make the same shape and then replaced into the hole to give a new way to assemble the pieces). So it is clear that there are many ways to assemble the pieces into a rectangle of a given size.

    It appears, then, that the puzzle is flawed.

    Here are my 2 sets of pieces that can be assembled into a 2×13 rectangle (in multiple ways), the pieces correspond to the following named pieces in my program – (specified as (achiral) + (chiral)):

    (p0, p1, p2, p3, p4, p6) + (p7, p8)
    (p0, p1, p2, p3, p5, p6) + (p7, p8)

    Enigma 321 - Solution 2x13

    (The chiral pieces are shown in shades of grey, the achiral pieces are coloured. The piece given in the puzzle text is coloured red).

    The minimum dimension of any assembled rectangle is 2 as the example piece given (p6) has a minimum dimension of 2, so 2×13 is the only possible rectangle that can be constructed from 8 pieces with a total area of 26.

    The collections of pieces that can be assembled in to a 3×9 rectangle (in multiple ways) are given below, the corresponding pieces are:

    (p0, p1, p2, p4, p5, p6) + (p7, p8)
    (p0, p1, p3, p4, p5, p6) + (p7, p8)
    (p0, p1, p2, p3, p4, p6) + (p7, p9)
    (p0, p1, p2, p3, p5, p6) + (p7, p9)
    (p0, p1, p2, p3, p4, p6) + (p8, p9)
    (p0, p1, p2, p3, p5, p6) + (p8, p9)

    Enigma 321 - Solution 3x9

    Again this is the only possible rectangle that can be constructed from 8 pieces with a total area of 27.

    There are also 4 different collections of 8 pieces that can be assembled to make rectangles of 2×14 and 4×7, and also 2 different collections of 8 pieces that can be assembled to make rectangles of 3×10 and 5×6.

  2. Brian Gladman 3 December 2015 at 11:34 am

    I have put my solution here as I needed more control over comment content than WordPress offers.

    • Hugh Casement 3 December 2015 at 8:14 pm

      Brian,
      The puzzle as originally formulated says that each piece has at least one of the six squares removed.  With that restriction I find only ten pieces, of which three look different when reversed, and a maximum possible area of 35 units.  Is there a way to modify the conditions so that “you can get only one size” becomes true?

      • Brian Gladman 3 December 2015 at 10:57 pm

        Yes, my code solves the puzzle but it does more than this as well so I allowed all possible shapes including the one with six squares. But I agree that I should have an option to remove the use of the ‘all six squares’ shape. I’m not sure that I understand your question about the ‘only one size’ criterion.

        • Brian Gladman 4 December 2015 at 9:54 am

          I think your query amounts to a desire to have a program that gives puzzle solutions directly rather than giving output that has to be inspected to find solutions. If so I have changed the code to provide a ‘puzzle’ mode and a more general one.

        • Hugh Casement 4 December 2015 at 2:22 pm

          Did I express myself badly?  Jim showed that there is no unique solution to the puzzle as originally formulated.  You have shown that there are lots more solutions if we modify the conditions.  I was hoping for a minimum modification that would yield a unique solution, so that we could “rescue” the flawed puzzle.

          • Jim Randell 4 December 2015 at 3:41 pm

            One way (or two ways really) to rescue the puzzle would be instead of requiring p6 (the “U” pentomino) to be present in the set of 8 pieces, to require either p2 (the “I” tromino) or p3 (the “V” tronimo) to be absent from the set of 8 pieces. (The requirement for 6 achiral and 2 chiral pieces remains). Then there are only solutions for the 3×9 rectangle. (They are the 1st and 2nd of the 3×9 diagrams I gave above – the 1st one omits p3 (orange in the other diagrams) the 2nd one omits p2 (green in the other diagrams)).

  3. Jim Randell 4 December 2015 at 3:08 pm

    I found a site that provides a Python based framework for solving Polyform Puzzles [ http://puzzler.sourceforge.net/ ].

    Here is my program modified to use this solver. It’s a bit tricky to control it to solve the multiple rectangles required for this puzzle, but it runs much faster than my original solution. It takes just 2.89s, and finds the same set of solutions I gave above.

    import puzzler.coordsys
    from puzzler.puzzles.polyominoes import Polyominoes12345
    from StringIO import StringIO
    
    from itertools import product, combinations
    from enigma import irange, divisor_pairs, printf
    
    # pieces (<number of squares>, <polyform identifier>)
    pieces = (
      # achiral
      (1, "O1"), # p0
      (2, "I2"), # p1
      (3, "I3"), # p2
      (3, "V3"), # p3
      (4, "O4"), # p4
      (4, "T4"), # p5
      (5, "U"),  # p6
      # chiral
      (4, "Z4"), # p7
      (4, "L4"), # p8
      (5, "P"),  # p9
    )
    
    # suitable settings for the solver (we only want one answer)
    settings = puzzler.process_command_line()
    settings.stop_after = 1
    
    # fit the pieces ps into an a x b grid using the Polyform solver
    # return the number of solutions found (0 or 1)
    def solve(ps, a, b):
    
      # collect polyform ids
      ks = tuple(pieces[i][1] for i in ps)
    
      # make a solver
      class Enigma321(Polyominoes12345):
        height = a
        width = b
        piece_data = dict((k, Polyominoes12345.piece_data[k]) for k in ks)
    
      # capture the output
      output = StringIO()
    
      # run the solver
      puzzler.run(Enigma321, output_stream=output, settings=settings)
      r = output.getvalue()
    
      # output the working
      printf("{r}")
    
      # return the number of solutions
      return int("\n1 solution," in r)
    
    # choose 2 chiral pieces and 5 achiral pieces
    for (ps1, ps2) in product(combinations((7, 8, 9), 2), combinations((0, 1, 2, 3, 4, 5), 5)):
    
      # combine them, along with p6, to form the 8 pieces of the puzzle
      ps = ps1 + ps2 + (6,)
    
      # count the number of squares
      n = sum(pieces[i][0] for i in ps)
      printf("\nn={n}, ps={ps}", ps=sorted(ps))
    
      # consider possible rectangles
      ds = list((a, b) for (a, b) in divisor_pairs(n) if not(a < 2 or b < 3))
      if len(ds) < 1: continue
      printf("possible rectangles = {ds}")
    
      d = 0
      for (a, b) in ds:
        printf("trying {a}x{b} ...")
        d += solve(ps, a, b)
    
      # if there's only one completed grid then this is a solution
      if d == 1:
        printf("SOLUTION: n={n}, {a}x{b} rectangle\n")
    

    Under the hood I think it is using the same Knuth algorithm that Brian used in his solution.

    For completeness I should point out, that if we don’t require p6 (the “U” pentomino), but do require 6 achiral and 2 chiral pieces there are three additional solutions:

    One set of 8 pieces that can be assembled into (only) a 5×5 rectangle – (p0, p1, p2, p3, p4, p5) + (p7, p8).

    Two sets of 8 pieces that can be assembled into (only) a 2×13 rectangle – (p0, p1, p2, p3, p4, p5) + (p7, p9) and (p0, p1, p2, p3, p4, p5) + (p8, p9).

  4. Brian Gladman 4 December 2015 at 10:00 pm

    Yes, polyform puzzler uses Donald Knuth’s Dancing Links algorithm. In my solution, I originally missed the need to include the U shape so I got some extra solutions (I have left these in my pictures). I now get the same results for the 3 x 9 rectangle but I am still seeing four rather than two solutionns for the 2 x 13 rectangle. This appears to arise because I am not constraining the solution to include two chiral shapes – two of my solutions have only one chiral shape.

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: