# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1519: Dominotrix

From New Scientist #2681, 8th November 2008 [link]

Our toddler granddaughter has been staying with us, and she has used our standard set of dominoes (each twice as long as broad) for building castles. Now that she has gone home I have managed to find most of the set, and I can divide these into two unequal lots. Each lot can be arranged into a solid square, and can also be arranged into a closed ring (for example, 6-4#4-2#2-2#2-6). The total number of “pips” in each lot sum to a perfect square.

Which dominoes are still lost?

[enigma1519]

### One response to “Enigma 1519: Dominotrix”

1. Jim Randell 11 September 2012 at 6:48 pm

The following Python program runs in 6.4s (under PyPy).

As noted in the comments in the code, in the initial stages of the computation it can be deduced analytically what the solution to the puzzle is. But we want to see a constructive solution, so the program goes on to generate all possible sets of dominoes that satisfy the conditions of the puzzle, and verify that they all correspond to the solution.

My original Perl code ran in 2m6s.

```from itertools import combinations
from collections import defaultdict
from enigma import irange, is_square, printf

# each domino is two squares
dominoes = set((i, j) for i in irange(0, 6) for j in irange(i, 6))

# count the dominoes, squares and pips
nd = len(dominoes)
ns = 2 * nd
np = sum(sum(d) for d in dominoes)
printf("totals: {nd} dominoes, {ns} squares, {np} pips")

# the smallest ring uses 4 dominoes (and 8 squares)
# an even number of dominoes can make a ring
# so find rings that use a square number of squares
rings = list(n for n in irange(4, nd, 2) if is_square(2 * n))
printf("rings: {rings}")

# at this point we see that there are only two possibilities for the rings
# one with 18 dominoes and one with 8 dominoes
# (and the remaining two dominoes are missing ones)

# the set of 18 dominoes must form an even square between 76 and 140
# so it must be 100
# and the set of 8 dominoes must form an even square between 19 and 77
# i.e. 36 or 64
# as the total sum of the complete set is 168 it follows that sets must be:
# (18 -> 100, 8 -> 64, 2 -> 4) or (18 -> 100, 8 -> 36, 4 -> 32)
# but the lost set of 2 must sum between 1 and 23 so that leaves only the first possibility.

# so there are two missing dominoes that sum 4
# i.e. (0-0, 1-3), (0-0, 2-2), (0-1, 1-2)
# but as the pips on both the rings come in even counts that means that the pips on the
# lost set must also come in pairs, leaving (0-0, 2-2) as the only possibility

# but we want a constructive proof, so let's carry on...

# try to complete the ring r, using dominoes ds
def make_ring(r, ds):
n = len(ds)
if n == 0:
if r[0] != r[-1]: return None
return r

# place the next domino
for i in range(n):
(a, b) = ds[i]
if a == r[-1]:
rr = make_ring(r + [a, b], ds[:i] + ds[i+1:])
if rr: return rr
elif b == r[-1]:
rr = make_ring(r + [b, a], ds[:i] + ds[i+1:])
if rr: return rr

# see if the dominoes in ds can form a ring
def ring(ds):
# count the pips
ps = defaultdict(int)
for a, b in ds:
ps[a] += 1
ps[b] += 1
# they must come in pairs to form a ring
if any(v % 2 > 0 for v in ps.values()): return None

# remove any doubles from the ring
# (although there must be non-doubles too)
doubles = list(a for a, b in ds if a == b)
if any(ps[d] == 2 for d in doubles): return None
ds2 = list((a, b) for a, b in ds if a != b)

# can we make a ring from the remaining dominoes?
return make_ring(list(ds2[0]), ds2[1:])

# find combinations of the rings that leave a few dominoes missing
lost = defaultdict(int)
for (a, b) in combinations(rings, 2):
if not(a < b): (a, b) = (b, a)
r = nd - (a + b)
if not(r > 0): continue
printf("considering rings of length {a} & {b}, with {r} dominoes missing")

# select set a of the dominoes
for da in combinations(dominoes, a):
pa = sum(sum(d) for d in da)
# the sum of the ring must be even, and a sqaure
if pa % 2 > 0: continue
if not is_square(pa): continue
# can we form a ring with them?
ra = ring(da)
if not ra: continue
# now pick the remainder of the dominoes
for dr in combinations(dominoes.difference(da), 2):
pr = sum(sum(d) for d in dr)
# and the total of set b will be...
pb = np - (pa + pr)
# and that sum must also be an even square
if pb % 2 > 0: continue
if not is_square(pb): continue
# can set b form a ring?
db = dominoes.difference(da, dr)
rb = ring(db)
if not rb: continue
lost[tuple(sorted(dr))] += 1
printf("lost dominoes: {dr}", dr=sorted(dr))
printf("set a: {da}, pips={pa}", da=sorted(da))
printf("ring a: {ra}")
printf("set b: {db}, pips={pb}", db=sorted(db))
printf("ring b: {rb}")
printf()

for (k, v) in lost.items():
printf("lost dominoes: {k} [{v} solutions]")
```

Solution: The lost dominoes are 0-0 (double blank) and 2-2 (double two).

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