# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1653: Cut-free

From New Scientist #2819, 2nd July 2011 [link]

The image, above, shows six dominoes forming a rectangle. The dotted line shows how the rectangle can be cut into two rectangles without cutting through a domino.

I started again with a standard set of 28 dominoes and used some of them to make another rectangle. This time it was impossible to find a line that cuts it into two rectangles without cutting a domino.

I then broke up that rectangle, added two further dominoes from the set, and used them all to make a new rectangle. Once again, it was impossible to find a line that cut this into two rectangles without cutting a domino.

How many dominoes did I use in this last rectangle?

[enigma1653]

### 2 responses to “Enigma 1653: Cut-free”

1. jimrandell 4 December 2011 at 5:07 pm

This was a fun puzzle to solve programatically. The following Python program uses a recursive algorithm to attempt to fit dominoes into grids of various sizes until it finds an indivisible grid. Then it looks for grids that differ by 4 squares (2 dominoes).

Runtime is 1m52s, although using PyPy gets this down to a more acceptable 10.2s.

```from math import sqrt
from collections import defaultdict

class Solved(Exception): pass

def fit(t, a, b):
"fit dominoes into an a x b grid"
g = [[0 for j in range(b)] for i in range(a)]
_fit(t, a, b, g, ord('a'), 0, 0)

def _fit(t, a, b, g, m, n, q):
# are we done?
if n == t:
if divisible(a, b, g): return False
print("indivisible: {n} dominoes ({t} squares, {a}x{b} grid)".format(n=t//2, t=t, a=a, b=b))
for x in g:
print(''.join(map(lambda c: chr(c) if c else '.', x)))
raise Solved()

# no, so find an empty square...
for j in range(b):
for i in range(a):
if not g[i][j]:
# attempt to fit the domino
p = False
if i+1 < a and not g[i+1][j]:
# fit the domino horizontally
g[i][j] = g[i+1][j] = m
# and the rest
if _fit(t, a, b, g, m+1, n+2, q+2) and not p: p = True
# remove the domino
g[i][j] = g[i+1][j] = 0
if j+1 < b and not g[i][j+1]:
# fit the domino vertically
g[i][j] = g[i][j+1] = m
if _fit(t, a, b, g, m+1, n+2, q+1) and not p: p = True
g[i][j] = g[i][j+1] = 0
return p
return False

def divisible(a, b, g):
"check if the grid can be divided"
# check for a horizontal cut or a vertical cut
return any(divisible_h(g, j, a) for j in range(b-1)) or any(divisible_v(g, i, b) for i in range(a-1))

def divisible_h(g, j, a):
return all(g[i][j] != g[i][j+1] for i in range(a))

def divisible_v(g, i, b):
return all(g[i][j] != g[i+1][j] for j in range(b))

candidates = defaultdict(list)
for t in range(2, 58, 2):
# factor t into a and b (st. a <= b)
for a in range(3, int(sqrt(t)) + 2):
b, r = divmod(t, a)
if r > 0: continue
if b < a: continue
candidates[t].append((a, b))

# weed out any candidates that don't have a partner that differs by 4 squares (= 2 dominoes)
l = sorted(candidates.keys())
solved = []
for x in l:
if not(x - 4 in l or x + 4 in l): continue
# try to make an indivisible grid
try:
for a, b in candidates[x]:
fit(x, a, b)
except Solved:
solved.append(x)
if x - 4 in solved:
n = x // 2
print("### SOLUTION: {n} dominoes (and {n2} dominoes) ###".format(n=n, n2=n-2))
```

Solution: The second rectangle used 27 dominoes.

Here is a diagram of the cut-free tiling of the rectangles using 25 and 27 dominoes found by my program:

2. Jim Randell 26 June 2017 at 9:53 am

The following paper on “Fault-free Tilings of Rectangles” [ http://math.ucsd.edu/~ronspubs/81_01_fault_free_tilings.pdf ] establishes the following necessary and sufficient conditions for the existence of a fault-free tiling of a p×q rectangle:

1. pq is divisible by 2;
2. p ≥ 5 and q ≥ 5;
3. (p, q) ≠ (6, 6).

The proof that the 6×6 grid is not fault-free is nice.

This means that all even area grids that have both dimensions greater that 4 have a fault-free tiling, apart from the 6×6 grid.

The following program gives an analytical solution to the puzzle in 40ms, which is much less work than the constructive solution.

```from enigma import irange, divisor_pairs, printf

# find rectangles made from n dominoes that are fault-free
ff = list()
for n in irange(2, 28):
grids = list((p, q) for (p, q) in divisor_pairs(2 * n) if p > 4 and q > 4 and not(p == q == 6))
if grids:
printf("[fault-free = {n} dominoes, grids = {grids}]")
ff.append(n)

# find sets of dominoes which differ by 2
for n in sorted(ff):
if n - 2 in ff:
printf("SOLUTION: rectangle 1 = {m} dominoes, rectangle 2 = {n} dominoes", m=n - 2)
```