# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1314: Times table

From New Scientist #2472, 6th November 2004

From a full set of dominoes, I have taken just those that have a 1, 2, 3 or 4 at each end. I then arranged them into a rectangle, as shown, with each domino occupying two adjacent squares. The numbers are the product of the entries in that row or column. Just four dominoes are horizontal.

Which ones?

[enigma1314]

### One response to “Enigma 1314: Times table”

1. Jim Randell 25 June 2014 at 8:29 am

This Python program tries to fit the dominoes into the grid recursively, checking the products as rows and columns are completed. It runs in 3.2s.

```from enigma import diff, multiply, chunk, sprintf, printf

# numbers of rows and columns in the grid
(R, C) = (4, 5)

# the products of the rows and columns
rows = (8, 768, 12, 108)
columns = (36, 4, 64, 18, 48)

# the dominoes to place
dominoes = (
(1, 1), (1, 2), (1, 3), (1, 4),
(2, 2), (2, 3), (2, 4),
(3, 3), (3, 4),
(4, 4),
)

# update the grid, checking the products as rows/columns are completed
def update(g, *vs):
g = list(g)
for (i, v) in vs:
g[i] = v
# check products
(r, c) = divmod(i, C)
# are we completing a row?
row = g[r * C:r * C + C]
if None not in row and multiply(row) != rows[r]: return
# are we completing a column?
col = g[c:R * C:C]
if None not in col and multiply(col) != columns[c]: return
return g

# g - grid so far
# ds - dominoes remaining
# h - count of horizontal dominoes
# s - sequence of placements
def solve(g, ds, h=0, s=[]):
# are we done?
if not ds:
if h == 4:
# show the layout
printf("{s}", s=' '.join(sprintf("[{a}-{b}]@({p},{q})") for (p, a, q, b) in s))
# find the horizontal dominoes
hs = sorted((a, b) for (p, a, q, b) in s if q == p + 1)
printf("{h} horizontal => {hs}", hs=' '.join(sprintf("[{a}-{b}]") for (a, b) in hs))
elif h < 5:
# find the next non-empty spot
i = g.index(None)
(r, c) = divmod(i, C)
# determine placements for the domino
ps = list()
# try to fit the domino horizontally
if c < C - 1 and g[i + 1] is None: ps.append((i, 1))
# try to fit the domino vertically
if r < R - 1 and g[i + C] is None: ps.append((i, C))
for (i, j) in ps:
for d in ds:
# try to fit the domino one way
(a, b) = d
g2 = update(g, (i, a), (i + j, b))
if g2: solve(g2, diff(ds, [d]), (h + 1 if j == 1 else h), s + [(i, a, i + j, b)])
# try to fit the domino the other way
if a == b: continue
g2 = update(g, (i, b), (i + j, a))
if g2: solve(g2, diff(ds, [d]), (h + 1 if j == 1 else h), s + [(i, b, i + j, a)])