# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1374: Dominoes to the power of two

From New Scientist #2534, 14th January 2006

Using a standard set of dominoes, I laid out a row end-to-end such that (in typical domino style) touching ends were the same (e.g. 6-3, 3-5, 5-5, 5-1 etc). I started with 0-0 and then added dominoes so that the total number of pips in the row equalled 1, then 4, then 9, working my way though each perfect square and continuing as far as possible. My row could not have been shorter at any stage.

Having reached the highest square possible I was left with five dominoes, four of which were doubles.

What were those five dominoes?

[enigma1374]

### One response to “Enigma 1374: Dominoes to the power of two”

1. Jim Randell 10 November 2013 at 9:43 am

I adapted my solution to Enigma 1450 (which is a similar problem, but with triangular numbers instead of square numbers) to give a constructive solution. This is a Python 3 program that runs in 66ms.

from collections import defaultdict
from enigma import irange, flatten, csum, is_square, Accumulator, printf

# a set of dominoes by number of pips
ds = defaultdict(set)
for a in irange(0, 6):
for b in irange(0, a):

# find all chains of dominoes that sum n (ignore 0-0 to make things easier)
# n - desired sum
# p - number of pips at the end of the chain
# ds - dominoes (indexed by number of pips)
# chain - chain of dominoes used so far
# returns chains as a list of (<chain>, <number of pips at end of chain>)
def dominoes(n, p, ds, chain):
r = []
# find dominoes that can start the chain
for i in irange(1, n):
for d in ds[i]:
if d not in chain and p in d:
# q is the other end of the domino
q = d[d.index(p) ^ 1]
if p + q == n:
r.append(([d], q))
else:
for (c2, q2) in dominoes(n - (p + q), q, ds, chain + [d]):
r.append(([d] + c2, q2))
# return chains of minimal length
if len(r) < 1: return []
m = min(len(x[0]) for x in r)
return list(x for x in r if len(x[0]) == m)

# output a chain (although without matching the ends of the dominoes)
def output(chain):
return ' '.join(str(d[0]) + '-' + str(d[1]) for d in chain)

# add dominoes to the chain that sum n
# chain - the chain created so far
# n - number of pips to add to the chain
# fn - function to generate next number of pips
# p - number of pips at the end of the chain
# ds - dominoes (indexed by number of pips)
def solve(chain, n, fn, p, ds):
# find minimal next chains
cs = dominoes(n, p, ds, chain)
if not cs:
# the chain cannot be extended further
# return the n, the chain, the remaining dominoes
yield (n, chain, set(flatten(ds.values())).difference(chain))
else:
# extend the chain
for (c, q) in cs:
yield from solve(chain + c, fn(n), fn, q, ds)

m = Accumulator(fn=min)
for (n, c, r) in solve([(0, 0)], 1, (lambda x: x + 2), 0, ds):
# record chains with five remaining dominoes, 4 of them doubles
if len(r) == 5 and sum(1 for (a, b) in r if a == b) == 4:
printf("[{n} / {c} / {r}]", c=output(c), r=output(sorted(r)))
# record the indices of the squares
ss = tuple(i for (i, n) in enumerate(csum(a + b for (a, b) in c)) if is_square(n) is not None)
# we want the largest square, but the smallest indices
m.accumulate_data((-n, ss), (c, r))

# output the solution
(c, r) = m.data
printf("{c} / {r}", c=output(c), r=output(sorted(r)))

Solution: The five remaining dominoes are: 0-2, 1-1, 2-2, 3-3, 5-5.

There are two chains that achieve the maximum possible square with five dominoes remaining, of which four are doubles. These are:

0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, 1-5, 5-2, 2-6, 6-3, 3-5, 5-0, 0-4, 4-6, 6-6, 6-0, 0-3, 3-1, 1-4, 4-4, 4-2 (unused: 0-2, 1-1, 2-2, 3-3, 5-5).

0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-3, 3-1, 1-4, 4-6, 6-0, 0-5, 5-1, 1-6, 6-6, 6-2, 2-0, 0-3, 3-5, 5-5, 5-2, 2-4 (unused: 0-4, 1-1, 2-2, 3-3, 4-4).

But the puzzle requires that the chain “could not have been shorter at any stage”. To do this I examine the indices at the chain at which square totals are achieved and choose the smallest tuple. For the two cases above the indices are:

(0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22)
(0, 1, 2, 3, 4, 5, 6, 8, 10, 13, 15, 19, 22)

and so the first chain is the answer to the puzzle, as each index is ≤ the corresponding index in the other solution(s).

But it’s not guaranteed that there would be a solution. If the second sequence went …, 10, 13, 14, 19, … then each sequence would be the shortest at different indices so there would be no overall solution that is the shortest at every stage. However given that there is a solution, it will be the smallest when they are lexicographically ordered.

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