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.

Enigma 1241

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]

Advertisements

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:

    Enigma 1241 - Solution George

    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).

    Enigma 1241 - Solution Mum

    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.

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: