# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1450: Triangular dominoes

From New Scientist #2611, 7th July 2007

Using a standard set of dominoes, I laid out the chain 0-0 0-1 1-1 1-2 2-2 in one direction so that the total number of “pips” in the chain reached every one of the triangular numbers 1 3 6 10 … in turn up to the greatest possible triangular number.

If there was a choice of routes from one triangular number to the following one (as for example in the next one to that shown, which might be 2-0 0-3 or 2-3), I preferred the route using the smaller or smallest number of dominoes that allowed me to continue. Having reached the highest triangular number that I could in this manner, I found that I had more than five dominoes in my hand left unused.

Which were these dominoes?

[enigma1450]

Advertisements

### One response to “Enigma 1450: Triangular dominoes”

1. Jim Randell 17 March 2013 at 9:52 am

This Python program solves the problem recursively. It runs in 36ms.

```from collections import defaultdict
from enigma import irange, flatten, Accumulator, printf

# dominoes by number of pips
ds = defaultdict(set)
for a in irange(0, 6):
for b in irange(0, a):
ds[a + b].add((b, 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
# p - number of pips at the end of the chain
# ds - dominoes (indexed by number of pips)
# m - accumulator for results
def solve(chain, n, p, ds, m):
# find minimal next chains
cs = dominoes(n, p, ds, chain)
if cs:
for (c, q) in cs:
solve(chain + c, n + 1, q, ds, m)
else:
# the chain cannot be extended further, find the remaining dominoes
r = set(flatten(ds.values())).difference(chain)
# if there are more than 5 we have a possible solution
if len(r) > 5: m.accumulate_data(n - 1, (r, chain))
printf("[{n} / {chain} / {r}]", n=n-1, chain=output(chain), r=output(sorted(r)))

m = Accumulator(fn=max)
# start with the initial chain given
solve([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], 5, 2, ds, m)

# output the chain to the largest triangular number
(n, (r, chain)) = (m.value, m.data)
printf("{n} / {chain} / {r}", chain=output(chain), r=output(sorted(r)))
```

Solution: The six unused dominoes are 0-2, 0-4, 0-6, 1-4, 1-6 and 2-6.