# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1112: Patio zones

From New Scientist #2268, 9th December 2000 [link]

George is building a patio, which will be covered using one-foot-square concrete slabs of seven different colours. He has divided the rectangular patio into seven rectangular zones, without any gaps.

Each zone will be covered by slabs of one colour, with five different colours appearing around the perimeter of the patio, and four different colours at the corners. The seven rectangular zones are all different shapes, but all have the same perimeter, which is less than 60 feet.

What are the dimensions of the patio that George is building?

This puzzle is referenced by Enigma 1221.

[enigma1112]

### 3 responses to “Enigma 1112: Patio zones”

1. Jim Randell 5 June 2017 at 9:22 am

At first I missed the fact that the seven zones were rectangular, and was worried that this was going to be quite a tricky problem to solve. Once I realised that the zones were rectangular it seemed like a more tractable problem, which can be solved using rectangle packing.

This Python 3 program runs in 2.17s (or 1.06s using PyPy).

Run: [ @repl.it ]

```from itertools import combinations, product
from collections import defaultdict
from enigma import irange, divisor_pairs, diff, join, arg, printf

# -- rectangle packer --

# determine if rectangle <r> overlaps with a rectangle in <rs>
# return the index in <rs> of an overlapping rectangle, or -1
def overlap(r, rs):
(i1, j1, p1, q1) = r
for (k, (i2, j2, p2, q2)) in enumerate(rs):
if i1 < i2 + p2 and i2 < i1 + p1 and j1 < j2 + q2 and j2 < j1 + q1:
return k
return -1

# fit the rectangles rs into a n x m grid (loose packing)
# n, m - the dimensions of the grid
# rs - dimensions of the rectangles (p, q)
# ps - positions of the rectangles (x, y, p, q)
def pack_loose(n, m, rs, ps=[]):
# are we done?
if not rs:
yield ps
else:
# try to fit the next rectangle into the grid
for (p, q) in set((rs[0], rs[0][::-1])):
# consider possible locations for the rectangle
for (i, j) in product(irange(0, n - p), irange(0, m - q)):
# does this position overlap with any placed rectangles?
r = (i, j, p, q)
if overlap(r, ps) == -1:
# try to place the remaining rectangles
for z in pack_loose(n, m, rs[1:], ps + [r]): yield z

# find the first empty square
def empty(n, m, ps):
for j in irange(0, m - 1):
for i in irange(0, n - 1):
if overlap((i, j, 1, 1), ps) == -1:
return (i, j)

# fit the rectangles rs into a n x m grid (tight packing)
# n, m - the dimensions of the grid
# rs - dimensions of the rectangles (p, q)
# ps - positions of the rectangles (x, y, p, q)
def pack_tight(n, m, rs, ps=[]):
# are we done?
if not rs:
yield ps
else:
# find an empty square
(i, j) = empty(n, m, ps)
# fit one of the remaining rectangles there
for (k, r) in enumerate(rs):
for (p, q) in (r, r[::-1]):
if not(i + p > n or j + q > m):
r = (i, j, p, q)
if overlap(r, ps) == -1:
# and try to replace the remaining rectangles
yield from pack_tight(n, m, rs[:k] + rs[k + 1:], ps + [r])

# output a packed grid
def output_grid(n, m, rs):
# make an empty grid
g = list([0] * n for _ in irange(1, m))
# fill out the rectangles
for (k, (x, y, p, q)) in enumerate(rs, start=1):
for (i, j) in product(irange(x, x + p - 1), irange(y, y + q - 1)):
g[j][i] = k
# output the packing
z = len(str(k))
for r in g:
printf("{r}", r=join((str(x or 0).zfill(z) for x in r), sep=' '))

# -- end --

# use the tight rectangle packer
pack = pack_tight

# fit the rectangles <rs> into an <n> x <m> grid
# according to the required conditions
def fit(n, m, rs):

# find pairs of rectangles that have dimensions that add up to n or m
# pairs: ((p, q), i) -> [ ((p', q'), j), ... ]
(pairs_n, pairs_m) = (defaultdict(list), defaultdict(list))
for (A, B) in combinations(rs, 2):
for (a, b) in product((0, 1), repeat=2):
x = A[a] + B[b]
if x == n:
pairs_n[(A, a)].append((B, b))
pairs_n[(B, b)].append((A, a))
if x == m:
pairs_m[(A, a)].append((B, b))
pairs_m[(B, b)].append((A, a))

# choose a pair to go across the top (n)
for ((A, a), vs) in pairs_n.items():
for (B, b) in vs:
if not(A < B): continue

# look for rectangle C to fill the gap along the left edge (m)
for (C, c) in pairs_m[(A, a ^ 1)]:
if C == B: continue

# look for rectangle D to fill the gap along the right edge (m)
for (D, d) in pairs_m[(B, b ^ 1)]:
if D == A or D == C: continue

# measure the gap between C and D on the bottom edge (n)
g = n - C[c ^ 1] - D[d ^ 1]
if g > 0:

# the remaining rectangles
rs1 = diff(rs, [A, B, C, D])

# find rectangle E to fit in the gap in the perimeter
for (E, e) in product(rs1, (0, 1)):
if E[e] == g and not(E[e ^ 1] > m):

# place A, B, C, D
ps = [
# A is in the top left corner
(0, 0, A[a], A[a ^ 1]),
# B is in the top right corner
(n - B[b], 0, B[b], B[b ^ 1]),
# C is in the bottom left corner
(0, A[a ^ 1], C[c ^ 1], C[c]),
# D is in the bottom right corner
(n - D[d ^ 1], m - D[d], D[d ^ 1], D[d])
]

# place E in the gap between C and D
r = (C[c ^ 1], m - E[e ^ 1], E[e], E[e ^ 1])

# if it packs correctly...
if overlap(r, ps) == -1:
# then pack the remaining (non-perimeter) rectangles
yield from pack(n, m, diff(rs1, [E]), ps + [r])

# try to fit the rectangles into the grid (both ways)
def solve(x, y, rs):
# try the normal way
for s in fit(x, y, rs): yield s
# and the other way (transposing the results)
for s in fit(y, x, rs): yield list((j, i, q, p) for (i, j, p, q) in s)

# verbose output?
verbose = arg('', 0)

# consider semi-perimeters below 30
for p in irange(2, 29):
# possible rectangles
rs = list((a, p - a) for a in irange(1, p // 2))
# choose 7 of the rectangles
for s in combinations(rs, 7):
# max minor and major dimensions of the rectangles
mn = max(a for (a, b) in s)
mj = max(b for (a, b) in s)
# calculate the total area
A = sum(a * b for (a, b) in s)
# consider possible dimensions of the patio (x <= y)
for (x, y) in divisor_pairs(A):
if x < mn or y < mj: continue
if verbose: printf("[considering: semi-perimeter = {p}, rectangles = {s}, area = {A} = {x} * {y}]")
# try to fit the rectangles into the grid
for ps in solve(x, y, s):
printf("grid = {x} x {y}, rectangles = {ps}")
output_grid(x, y, ps)
printf()
break
```

Solution: George’s patio is 26 feet by 32 feet.

The seven rectangular areas are: 2×25, 3×24, 5×22, 6×21, 7×20, 8×19, 13×14. Each having a perimeter of 54 feet.

Here’s a diagram of how the rectangular areas fit together:

The program considers 15,705 different collections of rectangles and grids, which would take a long time of we passed each of them to the pack() function directly, and we would have to examine the results to check that the results are in the required configuration (i.e. with five different regions making up the perimeter, and four of these in the corners). Instead I use this information to pack five rectangles along the perimeter, and if that is possible then we only have two remaining rectangles to fit into the central hole (which I do use the rectangle packer for, although it is a bit of overkill).

2. geoffrounce 5 June 2017 at 4:33 pm

This Enigma proved an ideal candidate for MinZinc, consisting mainly of geometrical constraints
to check the packing of the rectangles. It was also quite fast – 129 msec in Geocode (bundled) and relatively short code. I found the perimeter of the seven rectangles to be 54 ft.

I used the diagram Jim included in the Enigma 1221, as it had the same requirements for colours.

```% A Solution in MiniZinc
%
% This solution uses Jim's diagram of seven areas in Enigma 1221: Flower Beds
%                     M (width)
%        ----------------------------
%        |      |         E         |
%        |      |-------------------|
%        |      |     |     D       |
%        |   F  | G   |-------------|
%     N  |      |     |        |    |
%(Height)|      |     |    C   | B  |
%        |      |     |        |    |
%        | --------------------|    |
%        |           A         |    |
%        |--------------------------|
%

include "globals.mzn";

% overall rectangle dimensions
var 1..100:M;  % overall width
var 1..100:N;  % overall height

set of int: Dim = 1..100;

% widths of all rectangles
var Dim: wa; var Dim: wb; var Dim: wc; var Dim: wd; var Dim: we;
var Dim: wf; var Dim: wg;

var 4..59: perim;  % perimeter of each of 7 rectangles < 60

% heights of all rectangles
var Dim: ha; var Dim: hb; var Dim: hc; var Dim: hd; var Dim: he;
var Dim: hf; var Dim: hg;

% all rectangle heights and widths are different for A,B,C,D,E,F
constraint all_different ( [wa, wb, wc, wd, we, wf, wg, ha, hb,
hc, hd, he, hf, hg]);

% perimeter of all rectangles ( eg pa = perimeter of A)
var Dim: pa; var Dim: pb; var Dim: pc; var Dim: pd; var Dim: pe;
var Dim: pf; var Dim: pg;

% area of all rectangles (eg ab = area of B)
var Dim: aa; var Dim: ab; var Dim: ac; var Dim: ad; var Dim: ae;
var Dim: af; var Dim: ag;

var 100..9999 : area = M * N;   % overall area of main rectangle
% (inc. 7 separate rectangles)

% Main Rectangle - width constraints (eg wf = width of F)
constraint wf + we == M /\ wf + wg + wd == M /\ wa + wb == M
/\ wf + wg + wc + wb == M;

% Main Rectangle - height constraints (eg hf = height of F)
constraint hf + ha == N /\ he + hg + ha == N /\
he + hd + hc + ha == N /\ he + hd + hb == N;

% Sub rectangle area constraints ie M*N = A + B + C + D + E + F + G
constraint area = (wa * ha) + (wb * hb) + (wc * hc) + (wd * hd)
+ (we * he) + (wf * hf) + (wg * hg);

% Sub rectangle perimeter constraints
constraint  2*(we + he) = perim /\ 2*(wf + hf) = perim /\ 2*(wa + ha) = perim
/\ 2*(wb + hb) = perim /\ 2*(wc + hc) = perim /\ 2*(wd + hd) = perim
/\ 2*(wg + hg) = perim;

solve satisfy;

output [ "M = " ++ show(M) ++ " N = " ++ show(N) ++
", overall patio dimensions" ++ "\n" ++
"ha = " ++ show(ha) ++ " wa = " ++ show(wa) ++
", hb = " ++ show(hb) ++ " wb = " ++ show(wb) ++ "\n" ++
"hc = " ++ show(hc) ++ " wc = " ++ show(wc) ++
", hd = " ++ show(hd) ++ " wd = " ++ show(wd) ++ "\n" ++
"he = " ++ show(he) ++ " we = " ++ show(we) ++
", hf = " ++ show(hf) ++ " wf = " ++ show(wf) ++ "\n" ++
"hg = " ++ show(hg) ++ " wg = " ++ show(wg) ];

% Output
% M = 26 N = 32, overall patio dimensions
% ha = 7 wa = 20, hb = 21 wb = 6   (A & B)
% hc = 14 wc = 13, hd = 8 wd = 19  (C & D)
% he = 3 we = 24, hf = 25 wf = 2   (E & F)
% hg = 22 wg = 5 (G)
% ----------
% Finished in 129msec
%

```
• Jim Randell 7 June 2017 at 10:48 am

Labelling the rectangles from 1 to 7 (corresponds with A to G in my program) we can get quite a compact MiniZinc model.

```include "globals.mzn";

% width and height of the seven rectangles
array[1..7] of var 1..29: w;
array[1..7] of var 1..29: h;

% the rectangles all have the same semi-perimeters less than 30
var 1..29: sp;
constraint forall (i in 1..7) (w[i] + h[i] = sp);

% the rectangles are all different (so all dimensions are different)
constraint all_different(w ++ h);

% width of grid
var 2..57: width;
constraint all_equal([width, w[1] + w[2], w[3] + w[6] + w[2], w[3] + w[5] + w[7] + w[2], w[3] + w[5] + w[4]]);

% height of grid
var 2..57: height;
constraint all_equal([height, h[1] + h[3], h[1] + h[6] + h[5], h[1] + h[6] + h[7] + h[4], h[2] + h[4]]);

% the rectangles fill the grid
constraint sum (i in 1..7) (w[i] * h[i]) = width * height;

solve satisfy;
```

On my machine this runs in 96ms with the [[ mzn-g12fd ]] solver (and only 98ms if [[ mzn-g12fd -a ]] is used).

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