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?



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
        for a, b in candidates[x]:
          fit(x, a, b)
      except Solved:
        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}]")
    # 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)

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: