# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1241: Jigsaw squares

From New Scientist #2397, 31st May 2003 [link]

George created a novel jigsaw by dissecting a wooden rectangle into 13 square pieces. The pieces had sides which were all different whole numbers of centimetres, and two had sides which are consecutive integers. They fit together in the arrangement shown, but you should not assume that the pieces are drawn to scale.

George’s mother found the squares lying around, and arranged them all together neatly to form a rectangle, with the same dimensions as George’s, but not in his arrangement. All seven of George’s edge pieces were also edge pieces in his mother’s jigsaw, but her layout had one more edge piece.

What were the dimensions of that piece?

[enigma1241]

### One response to “Enigma 1241: Jigsaw squares”

1. Jim Randell 13 April 2015 at 8:14 am

I used a variety of tools to solve this puzzle.

Firstly I labelled the 13 squares in the diagram from (apparently) smallest to (apparently) largest, a, b, c, d, e, f, g, h, i, j, k, l, m.

Then by considering vertical slices through the diagram we get 7 equations linking subsets of these variables to the height of the rectangle, x:

x = k + l = a + e + f + l = d + e + f + i = b + f + g + i = g + h + i = c + h + m = m + j

By considering horizontal slices through the diagram we get 6 equations linking subsets of these variables to the width of the rectangle, y:

y = i + l + m = d + g + l + m = a + d + g + k +m = c + e + g + j + k = b + e + h + j + k = f + h + j + k

These, along with the area constraint:

xy = a² + b² + c² + d² + e² + f² + g² + h² + i² + j² + k² + l² + m²

Give us 14 equations in 15 variables, so we can rewrite the system to give us the values in the term of a single variable.

I used the SymPy symbolic maths library to do this:

```from sympy import symbols, Eq, solve
from enigma import printf

(a, b, c, d, e, f, g, h, i, j, k, l, m, x, y) = symbols(tuple('abcdefghijklmxy'))

eqs = (
# horizontal slices
Eq(x, k + l),
Eq(x, a + e + f + l),
Eq(x, d + e + f + i),
Eq(x, b + f + g + i),
Eq(x, g + h + i),
Eq(x, c + h + m),
Eq(x, m + j),
# vertical slices
Eq(y, i + l + m),
Eq(y, d + g + l + m),
Eq(y, a + d + g + k + m),
Eq(y, c + e + g + j + k),
Eq(y, b + e + h + j + k),
Eq(y, f + h + j + k),
# area constraint
Eq(x * y, a * a + b * b + c * c + d * d + e * e + f * f + g * g + h * h + i * i + j * j + k * k + l * l + m * m),
)

for s in solve(eqs, dict=True):
for (k, v) in s.items():
printf("{k} = {v}")
printf()
```

This runs in 3.9s and gives me the following results:

For positive integers n:

a = 3n
b = 5n
c = 9n
d = 11n
e = 14n
f = 19n
g = 20n
h = 24n
i = 31n
j = 33n
k = 36n
l = 39n
m = 42n
x = 75n
y = 112n

We require the values to be all different (which they are), and for two of the values to be consecutive, which means n=1 (the consecutive values are f and g, having values of 19 and 20 respectively).

So we now know that George packed a 3×3, 5×5, 9×9, 11×11, 14×14, 19×19, 20×20, 24×24, 31×31, 33×33, 36×36, 39×39 and a 42×42 square into a 75×112 rectangle. Thus:

The 7 squares in the perimeter of George’s packing are: 19, 24, 31, 33, 36, 39, 42.

George’s Mum also packed the squares into a 75×112 rectangle, but in a (non-trivially) different way

I wrote my own rectangle packer for Enigma 1251 (based on my code for Enigma 17), but here I’ve solved the packing problem with a MiniZinc model:

```% dimensions of the grid to pack
int: W = 112;
int: H = 75;

% rectangles to pack
int: n = 13;
array[1..n, 1..2] of int: rect = array2d(1..n, 1..2, [
3, 3, 5, 5, 9, 9, 11, 11, 14, 14, 19, 19, 20, 20, 24, 24, 31, 31, 33, 33, 36, 36, 39, 39, 42, 42,
]);

% position and dimensions of the packed rectangles
array[1..n] of var 1..W: x;
array[1..n] of var 1..H: y;
array[1..n] of var 1..W: w;
array[1..n] of var 1..H: h;

% the packed rectangles correspond to the rectangles
constraint forall (i in 1..n) (((w[i] == rect[i, 1]) /\ (h[i] == rect[i, 2])) \/ ((w[i] == rect[i, 2]) /\ (h[i] == rect[i, 1])));

% the rectangles are inside the grid
constraint forall (i in 1..n) (not(x[i] + w[i] > W + 1) /\ not(y[i] + h[i] > H + 1));

% there are no overlaps
constraint forall (i, j in 1..n where i < j) (not((x[i] < x[j] + w[j]) /\ (x[j] < x[i] + w[i]) /\ (y[i] < y[j] + h[j]) /\ (y[j] < y[i] + h[i])));

% solve it
solve satisfy;

% output the placements
output [ show(i) ++ ": " ++ show(w[i]) ++ "x" ++ show(h[i]) ++ " @ " ++ show(x[i]) ++ "," ++ show(y[i]) ++ "\n" | i in 1..n ];
```

(Note that the orientation constraint could be simplified here, as the rectangles we are packing are squares).

This program runs in 718ms (using: mzn-g12lazy -a enigma1241.mzn), and produces two separate packings, George’s shown above, and the packing shown below (along with their rotations and reflections).

This second packing is the one that George’s Mum made.

The 8 squares in the perimeter of this packing are: 19, 20, 24, 31, 33, 36, 39, 42.

Solution: The extra edge piece in George’s Mum’s packing is the 20×20 square.