# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1592: Seeing spots

From New Scientist #2757, 24th April 2010 [link]

If you take a domino set and discard all those dominoes which involve a 5 or a 6, leaving 15 dominoes with a 0, 1, 2, 3 or 4 at each end, then the rest can be laid out, spotty sides up, to form a 5-by-6 rectangle. Then, taking the number of spots in each square as that square’s value, the product of each row can be calculated by multiplying together the values of the six squares in that row.

Your task is to lay out the dominoes so that the five products are all different, less than 1000, and in increasing order as you come down the rectangle. Just one row must have a product which is odd, just one must have a product which is a power of 2, and just one other must have a product which is a non-zero perfect square.

List the products of the five rows.

[enigma1592]

### One response to “Enigma 1592: Seeing spots”

1. jimrandell 23 January 2012 at 8:54 am

This one is easier to solve with pencil and paper, than it is to make a program to try all possibilities. Nevertheless here is a programmatic solution.

It seemed that generating the entire solution space and then looking for an answer would take a long time, so I split the problem into two phases (much like my paper solution). The first phase considers the possible partitioning of the the six 1’s, 2’s, 3’s and 4’s to create four rows with the necessary products. Careful reading of the puzzle is required, the “just one other” part means that the square must be from one of the rows other than the odd number and the power of two. The second phase is to take each of the candidate set of rows and try to tile it with the dominoes, generating and testing possibilities for each row in turn to avoid having to test huge numbers of potential grids. Once we find a suitable tiling of the grid we stop looking.

In the end the program runs in a very satisfactory 152ms.

Run: [ @repl.it ]

```from collections import Counter
from itertools import combinations, combinations_with_replacement, permutations
from enigma import multiply, is_square

# we have 6 of 0, 1, 2, 3, 4

# it follows that all 0's must be in the first row

# the row with the odd product must consist solely of 1's and 3's

# the row that's a power of two must consist solely of 1's, 2's and 4's (i.e. not 3's)

def generate():
# we start with 6 copies of 1, 2, 3 and 4
n1 = Counter({1: 6, 2: 6, 3: 6, 4: 6})
# find row with the odd product (3^6 is less that 1000)
for ones in range(0, 7):
ro = [1]*ones + [3]*(6 - ones)
po = multiply(ro)

n2 = n1.copy()
n2.subtract(ro)
# the row whose product is a power of two (cannot contain 3's)
for r2 in set(combinations(n2.elements(), 6)):
if 3 in r2: continue
r2 = list(r2)
p2 = multiply(r2)
if not(p2 < 1000): continue

n3 = n2.copy()
n3.subtract(r2)
# find the remaining two rows
for ra in set(combinations(n3.elements(), 6)):
ra = list(ra)
pa = multiply(ra)
if not(pa < 1000): continue
# let's find the square first
if not(is_square(pa)): continue
# and it can't be another odd row or power of two
if pa % 2: continue
if set(ra).issubset((1, 2, 4)): continue

# and the remaining row
n4 = n3.copy()
n4.subtract(ra)
rb = sorted(n4.elements())
pb = multiply(rb)
if not(pb < 1000): continue
# it can't be square
if is_square(pb): continue
# and it can't be another odd row or power of two
if pb % 2: continue
if set(rb).issubset((1, 2, 4)): continue

# yield the rows sorted by product
yield sorted((ro, r2, ra, rb), key=multiply)

# what dominoes do we have?
dominoes = set(combinations_with_replacement(range(5), 2))

# check to see if the rows can be tiled as dominoes
def check(rs):
# the top row is always 0's
g = [tuple([0] * 6)] + [None]*4
# take a fresh set of dominos
ds = dominoes.copy()
# and an empty set of domino places
ps = [[None]*6 for i in range(5)]
# now try possible permutations for each row...
for g[1] in set(permutations(rs[0])):
# and try to tile that row with dominoes
if not fit(g, 0, ds, ps): continue
for g[2] in set(permutations(rs[1])):
if not fit(g, 1, ds, ps): continue
for g[3] in set(permutations(rs[2])):
if not fit(g, 2, ds, ps): continue
for g[4] in set(permutations(rs[3])):
if not fit(g, 3, ds, ps): continue
if not fit(g, 4, ds, ps): continue
# we've managed to tile all the rows...
# output the products
print(tuple(multiply(r) for r in g))
# output the grids
for i in range(5):
print(g[i], ' '.join(ps[i]), sep='   ')
# we only need one way of fitting the dominoes
return

def fit(g, y, ds, ps):
# find an empty square
for x in range(6):
if ps[y][x] is not None: continue
# can we fit a horizontal domino in it?
if x < 5 and ps[y][x+1] is None:
d = tuple(sorted((g[y][x], g[y][x+1])))
if d in ds:
ps[y][x], ps[y][x+1] = 'W', 'E'
ds.remove(d)
if fit(g, y, ds, ps):
return True
ps[y][x] = ps[y][x+1] = None

# can we fit a vertical domino in it
if y < 4 and ps[y+1][x] is None:
d = tuple(sorted((g[y][x], g[y+1][x])))
if d in ds:
ps[y][x], ps[y+1][x] = 'N', 'S'
ds.remove(d)
if fit(g, y, ds, ps):
return True
ps[y][x] = ps[y+1][x] = None

return False
return True

seen = []
for rs in generate():
if rs in seen: continue
check(rs)
seen.append(rs)

print("checked {n} possibilities".format(n=len(seen)))
```

Solution: The products of the rows are 0, 24, 27, 512 and 576.