Programming Enigma Puzzles
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:
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]
 | Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
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 (2h28m).
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)):
(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 (= U5)) 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:
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.
Having used the code above as a starting point for solving Teaser 2996, I then packaged the code dealing with polyominoes into a separate module, and improved on the packing algorithm using Knuth’s Algorithm X (the same approach used by Polyform Puzzler, and by Brian below).
The improved algorithm can then be used to solve this puzzle, giving a program which runs in only 374ms.
Run: [ @replit ]
from enigma import (flatten, multiset, subsets, cproduct, divisor_pairs, singleton, join, printf) import polyominoes # available pieces (achiral, chiral, always included) (achiral, chiral, always) = (x.split() for x in ["O1 I2 I3 V3 O4 T4", "Z4 L4 P5", "U5"]) # map pieces to orientations pieces = polyominoes.shapes(flatten([achiral, chiral, always]), as_map=1) # collect solutions r = multiset() # choose 2 chiral pieces and 5 achiral pieces for (ks1, ks2) in cproduct([subsets(chiral, size=2), subsets(achiral, size=5)]): # combine them, along with p6, to form the 8 pieces of the puzzle ps = flatten([ks1, ks2, always]) # count the number of squares n = sum(len(pieces[i][0]) for i in ps) printf("\nn={n}, ps={ps}", ps=join(ps, sep=" ")) # consider possible rectangles gs = list() for (a, b) in divisor_pairs(n): if a < 2 or b < 3: continue printf("trying {a}x{b} ...") # create an a x b empty grid and assemble the pieces into it for g in polyominoes.fit(list(pieces[i] for i in ps), b, a): # output a completed grid polyominoes.output_grid(g) gs.append((a, b)) # we only need one way to complete the grid break # is there only one possible rectangle? g = singleton(gs) if g is not None: r.add(g) printf("SOLUTION: n={n}, {g[0]}x{g[1]} rectangle\n") printf("\nSOLUTIONS:") for ((a, b), n) in r.most_common(): printf("{a}x{b} rectangle, {n} arrangements")I have put my solution here [{broken link removed}] as I needed more control over comment content than WordPress offers.
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?
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.
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.
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.
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)).
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 (although when I tried to run Brian’s program, it didn’t produce any output after consuming 32.5 hours of CPU time, so I stopped it).
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) = (O1, I2, I3, V3, O4, T4) + (Z4, L4).
Two sets of 8 pieces that can be assembled into (only) a 2×13 rectangle – (p0, p1, p2, p3, p4, p5) + (p7, p9) = (O1, I2, I3, V3, O4, T4) + (Z4, P5) and (p0, p1, p2, p3, p4, p5) + (p8, p9) = (O1, I2, I3, V3, O4, T4) + (L4, P5).
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.