Enigmatic Code

Programming Enigma Puzzles

Enigma 179: Dominoes

From New Scientist #1324, 23rd September 1982 [link]

“Let’s have an easier one,” said Uncle Dick. So here is an easier one, based on an idea of George Glæser which I heard from John Mason. The picture shows a full set of 21 dominoes, from 0-0 to 5-5, arranged in a 6 × 7 block. All I ask you to do is mark in the boundaries between the dominoes. There is only one possible arrangement.

[enigma179]

One response to “Enigma 179: Dominoes”

1. Jim Randell 27 March 2014 at 8:30 am

This Python program works by pairing up the squares, either horizontally or vertically, to divide the grid into non-duplicate dominoes. It labels the pairings with negative numbers to distinguish them from the domino pips. The program runs in 39ms.

```from enigma import chunk, printf

# grid dimensions (columns, rows)
(N, M) = (6, 7)

# number of dominoes to fit
D = (N * M) // 2

grid = [
0, 0, 1, 4, 5, 2,
4, 4, 0, 2, 4, 2,
4, 3, 2, 3, 1, 0,
5, 3, 5, 1, 1, 0,
5, 3, 1, 5, 3, 5,
3, 0, 4, 2, 2, 1,
1, 2, 4, 3, 0, 5,
]

# update grid <g> placing domino <n> at <i>, <j>
def update(g, i, j, n):
g = list(g)
g[i] = g[j] = n
return g

# g = grid
# n = label of next domino (1 to D)
# D = number of dominoes to place
# ds = dominoes already placed
def solve(g, n, D, ds):
# are we done?
if n > D:
# output the pairings
for r in chunk(g, N):
print(r)
print()
else:
# find the next unassigned square
for (i, d) in enumerate(g):
if d < 0: continue
(y, x) = divmod(i, N)
# find placements for the domino
js = list()
# horizontally
if x < N - 1 and not(g[i + 1] < 0): js.append(i + 1)
# vertically
if y < M - 1 and not(g[i + N] < 0): js.append(i + N)
# try possible placements
for j in js:
d = tuple(sorted((g[i], g[j])))
if d not in ds:
solve(update(g, i, j, -n), n + 1, D, ds.union([d]))
break

solve(grid, 1, D, set())
```

Solution: The arrangement of dominoes is shown below: