# 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:

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]

### 10 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)
#
# 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) = (O1 I2 I3 V3 O4 U5) + (Z4 L4)
(p0 p1 p2 p3 p5 p6) + (p7 p8) = (O1 I2 I3 V3 T4 U5) + (Z4 L4)

(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:

(p0 p1 p2 p4 p5 p6) + (p7 p8) = (O1 I2 I3 O4 T4 U5) + (Z4 L4)
(p0 p1 p3 p4 p5 p6) + (p7 p8) = (O1 I2 V3 O4 T4 U5) + (Z4 L4)
(p0 p1 p2 p3 p4 p6) + (p7 p9) = (O1 I2 I3 V3 O4 U5) + (Z4 P5)
(p0 p1 p2 p3 p5 p6) + (p7 p9) = (O1 I2 I3 V3 T4 U5) + (Z4 P5)
(p0 p1 p2 p3 p4 p6) + (p8 p9) = (O1 I2 I3 V3 O4 U5) + (L4 P5)
(p0 p1 p2 p3 p5 p6) + (p8 p9) = (O1 I2 I3 V3 T4 U5) + (L4 P5)

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.

• Jim Randell 23 February 2020 at 12:53 pm

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 693ms.

Run: [ @repl.it ]

import polyominoes
from itertools import combinations, product
from enigma import divisor_pairs, join, printf

# 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
ks = achiral + chiral + always
pieces = dict(zip(ks, polyominoes.shapes(ks)))

# choose 2 chiral pieces and 5 achiral pieces
for (ks1, ks2) in product(combinations(chiral, 2), combinations(achiral, 5)):

# combine them, along with p6, to form the 8 pieces of the puzzle
ps = list(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
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
for g in polyominoes.fit(list(pieces[i] for i in ps), b, a):
# output a completed grid
polyominoes.output_grid(g)
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")

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.