Enigmatic Code

Programming Enigma Puzzles

Enigma 1475: Lines of thought

From New Scientist #2637, 5th January 2008

Joe cut out a number of small square cards. On some of them he drew a thin red line joining the centres of two opposite sides and on the others he drew a thin red line joining the centres of two adjacent sides.

Penny’s challenge was to select 24 cards and arrange them in a 6-card by 4-card rectangle so as to produce a number of small areas, each with a complete single boundary of thin red lines, with a total area equal to five-sixteenths of the total card area.

Penny could choose any combination of cards – for example, 10 of the first and 14 of the second – but only some of the combinations would lead to her meeting the challenge.

How many of the combinations?

[enigma1475]

2 responses to “Enigma 1475: Lines of thought”

1. Jim Randell 9 December 2012 at 10:47 am

I thought this sounded like a tricky one to code up, but when I set about it it was actually surprisingly simple, but still fun. The following recursive Python approach runs in 150ms.

```from collections import namedtuple, defaultdict
from itertools import product
from enigma import printf

# each edge is split into two segments, whichare on the
# exterior (0) or interior (1) of the shape
# u - top edge (up)
# d - lower edge (down)
# l - left edge
# r - right edge
# measure the area of the tile in eighths of a tile
# i - interior area of the tile
# tiles are of type A (half split) or type B (corner split)
# t - type of the tile
Tile = namedtuple('Tile', 'u d l r i t')

# types of tile
(A, B) = ('A', 'B')

tiles = [
#     u  u    d  d    l  l    r  r   i  t
Tile((0, 1), (0, 1), (0, 0), (1, 1), 4, A),
Tile((1, 0), (1, 0), (1, 1), (0, 0), 4, A),
Tile((1, 1), (0, 0), (1, 0), (1, 0), 4, A),
Tile((0, 0), (1, 1), (0, 1), (0, 1), 4, A),
Tile((0, 0), (0, 1), (0, 0), (0, 1), 1, B),
Tile((1, 1), (1, 0), (1, 1), (1, 0), 7, B),
Tile((0, 0), (1, 0), (0, 1), (0, 0), 1, B),
Tile((1, 1), (0, 1), (1, 0), (1, 1), 7, B),
Tile((1, 0), (0, 0), (1, 0), (0, 0), 1, B),
Tile((0, 1), (1, 1), (0, 1), (1, 1), 7, B),
Tile((0, 1), (0, 0), (0, 0), (1, 0), 1, B),
Tile((1, 0), (1, 1), (1, 1), (0, 1), 7, B),
]

# x, y - dimensions of the grid
# g - the grid
# n - number of tiles to place
# r - accumulate results
def solve(x, y, g, n, r):
# are we done?
if n == 0:
# count the interior area and types of tiles
(a, c) = (0, { A: 0, B: 0 })
for (i, j) in product(range(x), range(y)):
t = g[i][j]
a += t.i
if t.t in c: c[t.t] += 1
if a == 60:
r[(c[A], c[B])] += 1
return
# find an empty space
for (i, j) in product(range(x), range(y)):
if g[i][j] is None: break
# find a tile to fit there
for t in tiles:
if not all((g[i-1][j] is None or g[i-1][j].d == t.u,
g[i+1][j] is None or g[i+1][j].u == t.d,
g[i][j-1] is None or g[i][j-1].r == t.l,
g[i][j+1] is None or g[i][j+1].l == t.r)): continue
g[i][j] = t
# and try to fill the remaining squares
solve(x, y, g, n - 1, r)
g[i][j] = None

# a blank tile
E = Tile((0, 0), (0, 0), (0, 0), (0, 0), 0, 0)

# make a 6x4 grid, surrounded by blank tiles (so an 8x6 grid)
(x, y) = (6, 8)
g = list([None] * y for i in range(x))
for (i, j) in product(range(x), range(y)):
if not(0 < i < x - 1 and 0 < j < y - 1): g[i][j] = E

r = defaultdict(int)
solve(x, y, g, (x - 2) * (y - 2), r)

# output the results
for k in sorted(r.keys()):
printf("{k[0]}A + {k[1]}B: {n} solutions", n=r[k])
printf("SOLUTION: {n} combinations", n=len(r))
```

Solution: There are 5 different combinations.

Instead of considering two different types of card and worrying about their rotations and determining the interior and exterior of shapes I instead considered 12 possible tiles which take all possible arrangements into account.

The edges of the tiles are split into two segments and labelled either 0 or 1 (for “0utside” and “1nside” to distinguish the exterior and interior segments). I then consider a 6 x 8 grid where the perimeter is filled with empty tiles that consist entirely of exterior edges. The problem is then simply to fit tiles into the grid so that the edges match up. And find solutions where the interior (coloured in) area is 60 (measuring in eighths of squares, so the entire 4 x 6 grid has an area of 192).

It turns out the are 59 different grids (although fewer if you eliminate duplicates grids by symmetry, and fewer still if you eliminate duplicate grids that use the same shapes, but rearranged).

It turns out that each of these grids is composed of the following 15 different enclosed shapes.

and here are example solutions using, 4 type A and 20 type B cards (there are 4 such grids):

6 type A and 18 type B cards (there are 4 such grids):

8 type A and 16 type B cards (there are 22 such grids):

10 type A and 14 type B cards (there are 20 such grids):

12 type A and 12 type B cards (there are 9 such grids):

The following code is augmented to produce all grid patterns (regardless of area), and attempt an ASCII art representation of the layout:

```from collections import namedtuple, defaultdict
from itertools import product
from enigma import printf

# each edge is split into two segments, whichare on the
# exterior (0) or interior (1) of the shape
# u - top edge (up)
# d - lower edge (down)
# l - left edge
# r - right edge
# measure the area of the tile in eighths of a tile
# i - interior area of the tile
# tiles are of type A (half split) or type B (corner split)
# t - type of the tile
# s - string representation
Tile = namedtuple('Tile', 'u d l r i t s')

# types of tile
(A, B) = ('A', 'B')

tiles = [
#     u  u    d  d    l  l    r  r   i  t   s
Tile((0, 1), (0, 1), (0, 0), (1, 1), 4, A, ' o o'),
Tile((1, 0), (1, 0), (1, 1), (0, 0), 4, A, 'o o '),
Tile((1, 1), (0, 0), (1, 0), (1, 0), 4, A, 'oo  '),
Tile((0, 0), (1, 1), (0, 1), (0, 1), 4, A, '  oo'),
Tile((0, 0), (0, 1), (0, 0), (0, 1), 1, B, '   /'),
Tile((1, 1), (1, 0), (1, 1), (1, 0), 7, B, 'ooo/'),
Tile((0, 0), (1, 0), (0, 1), (0, 0), 1, B, '  \\ '),
Tile((1, 1), (0, 1), (1, 0), (1, 1), 7, B, 'oo\\o'),
Tile((1, 0), (0, 0), (1, 0), (0, 0), 1, B, '/   '),
Tile((0, 1), (1, 1), (0, 1), (1, 1), 7, B, '/ooo'),
Tile((0, 1), (0, 0), (0, 0), (1, 0), 1, B, ' \\  '),
Tile((1, 0), (1, 1), (1, 1), (0, 1), 7, B, 'o\\oo'),
]

# x, y - dimensions of the grid
# g - the grid
# n - number of tiles to place
# r - accumulate results
def solve(x, y, g, n, r):
# are we done?
if n == 0:
# count the interior area and types of tiles
(a, c) = (0, { A: 0, B: 0 })
for (i, j) in product(range(x), range(y)):
t = g[i][j]
a += t.i
if t.t in c: c[t.t] += 1
printf("area={a} count={c}")
# output the gird
for x in g:
print(''.join(t.s[0:2] for t in x))
print(''.join(t.s[2:4] for t in x))
r[a][(c[A], c[B])] += 1
return
# find an empty space
for (i, j) in product(range(x), range(y)):
if g[i][j] is None: break
# find a tile to fit there
for t in tiles:
if not all((g[i-1][j] is None or g[i-1][j].d == t.u,
g[i+1][j] is None or g[i+1][j].u == t.d,
g[i][j-1] is None or g[i][j-1].r == t.l,
g[i][j+1] is None or g[i][j+1].l == t.r)): continue
g[i][j] = t
# and try to fill the remaining squares
solve(x, y, g, n - 1, r)
g[i][j] = None

# a blank tile
E = Tile((0, 0), (0, 0), (0, 0), (0, 0), 0, 0, '    ')

# make a 6x4 grid, surrounded by blank tiles (so an 8x6 grid)
(x, y) = (6, 8)
g = list([None] * y for i in range(x))
for i, j in product(range(x), range(y)):
if not(0 < i < x - 1 and 0 < j < y - 1): g[i][j] = E

r = defaultdict(lambda: defaultdict(int))
solve(x, y, g, (x - 2) * (y - 2), r)

# output the results
for k in sorted(r.keys()):
printf("area={k}: {n} solutions {a}", n=len(r[k]), a='*** ANSWER ***' if k == 60 else '')
print(dict(r[k]))
```

The maximum enclosed area you can make is 13.5 tiles, using a grid that uses 12 type A and 12 type B cards. It looks like this:

• Hugh Casement 4 October 2014 at 2:57 pm

Brilliant, Jim. Just the sort of detailed analysis we appreciate, as opposed to the one-line answers published in the magazine.