# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1491: Tile trials

From New Scientist #2653, 26th April 2008

Dick has a box of rectangular tiles. Each is a different size, the dimensions being 1 × 3, 2 × 4, 3 × 5, 4 × 6 and so on.

He takes some tiles out of the box, first the 1 × 3, then the 2 × 4, then the 3 × 5, and so on, with the aim of fitting together all those that he has taken into a rectangle that has no gaps and no overlaps.

Assuming he takes more than one tile out of the box, how many tiles must he take out to create (a) the smallest possible rectangle, and (b) the next smallest possible rectangle?

[enigma1491]

### One response to “Enigma 1491: Tile trials”

1. Jim Randell 18 November 2012 at 4:14 pm

This is a slightly different approach from my original Perl program that I wrote when the puzzle came out [link]. It’s shorter and faster and runs (under PyPy) in 9.2s. If I’d started off using this approach I probably wouldn’t have bothered writing the C version.

```from itertools import product
from enigma import sqrt, irange, printf

# fit a tile into the grid
# a, b = dimensions of grid
# g = grid
# ts = tiles
def fit(a, b, g, ts):
# are we done?
if len(ts) == 0: return True

# find the first empty square
for (x, y) in product(range(b), range(a)):
if not g[y][x]: break
for t in ts:
# try it in both orientations
for (tx, ty) in (t, t[::-1]):
# does the tile fit in the grid?
(mx, my) = (x + tx, y + ty)
if mx > b or my > a: continue
# is anything in the way of the tile?
if any(g[i][j] for (i, j) in product(range(y, my), range(x, mx))): continue
# place the tile
for (i, j) in product(range(y, my), range(x, mx)): g[i][j] = t[0]
# and try to place the remaining tiles
if fit(a, b, g, list(s for s in ts if s != t)): return True
# remove the tile
for (i, j) in product(range(y, my), range(x, mx)): g[i][j] = 0
# no tile fits in this gap
return False

# output the grid
def output(g):
label = '.123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for r in g:
printf("[{r}]", r=''.join(label[x] for x in r))

# n = number of tiles
# t = total area of the tiles
# ts = tiles
# s = number of solutions
(n, t, ts, s) = (1, 3, [(1, 3)], 0)

# we want to find the first two solutions
while s < 2:
n += 1
t += n * (n + 2)
ts.insert(0, (n, n + 2))

# try factors of t = a x b, not(a > b)
# and not(a < n), else the largest tile can't fit
for a in irange(n, int(sqrt(t) + 0.5)):
(b, r) = divmod(t, a)
if r > 0: continue
printf("[n={n} t={t} = {a}x{b}]")

# make an empty grid
g = [[0] * b for i in range(a)]
# and try to fit the tiles into it
if fit(a, b, g, ts):
printf("solution for {n} tiles, {a} x {b} grid")
output(g)
s += 1
```

Solution: (a) 9 tiles; (b) 11 tiles.

The solution for 9 tiles is a 15×25 grid (for example):

And for 11 tiles it is a 22×29 grid (for example):

If you stop the program from returning as soon as it has found a solution the program finds 336 possible tilings for the 15×25 grid and 64 possible tilings for the 22×29 grid (although this takes no account of symmetrical solutions, so you can divide these numbers by 4 to get the number of essentially different solutions – 84 for the 15×25 grid and 16 for the 22×29 grid).

The next smallest two possible tilings are both with 14 tiles and are for a 25×49 grid and a 35×35 grid.

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