Enigmatic Code

Programming Enigma Puzzles

Enigma 1374: Dominoes to the power of two

From New Scientist #2534, 14th January 2006

Using a standard set of dominoes, I laid out a row end-to-end such that (in typical domino style) touching ends were the same (e.g. 6-3, 3-5, 5-5, 5-1 etc). I started with 0-0 and then added dominoes so that the total number of pips in the row equalled 1, then 4, then 9, working my way though each perfect square and continuing as far as possible. My row could not have been shorter at any stage.

Having reached the highest square possible I was left with five dominoes, four of which were doubles.

What were those five dominoes?

[enigma1374]

Advertisements

One response to “Enigma 1374: Dominoes to the power of two

  1. Jim Randell 10 November 2013 at 9:43 am

    I adapted my solution to Enigma 1450 (which is a similar problem, but with triangular numbers instead of square numbers) to give a constructive solution. This is a Python 3 program that runs in 66ms.

    from collections import defaultdict
    from enigma import irange, flatten, csum, is_square, Accumulator, printf
    
    # a set of dominoes by number of pips
    ds = defaultdict(set)
    for a in irange(0, 6):
      for b in irange(0, a):
        ds[a + b].add((b, a))
    
    # find all chains of dominoes that sum n (ignore 0-0 to make things easier)
    # n - desired sum
    # p - number of pips at the end of the chain
    # ds - dominoes (indexed by number of pips)
    # chain - chain of dominoes used so far
    # returns chains as a list of (<chain>, <number of pips at end of chain>)
    def dominoes(n, p, ds, chain):
      r = []
      # find dominoes that can start the chain
      for i in irange(1, n):
        for d in ds[i]:
          if d not in chain and p in d:
            # q is the other end of the domino
            q = d[d.index(p) ^ 1]
            if p + q == n:
              r.append(([d], q))
            else: 
              for (c2, q2) in dominoes(n - (p + q), q, ds, chain + [d]):
                r.append(([d] + c2, q2))
      # return chains of minimal length
      if len(r) < 1: return []
      m = min(len(x[0]) for x in r)
      return list(x for x in r if len(x[0]) == m)
    
    # output a chain (although without matching the ends of the dominoes)
    def output(chain):
      return ' '.join(str(d[0]) + '-' + str(d[1]) for d in chain)
    
    # add dominoes to the chain that sum n
    # chain - the chain created so far
    # n - number of pips to add to the chain
    # fn - function to generate next number of pips
    # p - number of pips at the end of the chain
    # ds - dominoes (indexed by number of pips)
    def solve(chain, n, fn, p, ds):
      # find minimal next chains
      cs = dominoes(n, p, ds, chain)
      if not cs:
        # the chain cannot be extended further
        # return the n, the chain, the remaining dominoes
        yield (n, chain, set(flatten(ds.values())).difference(chain))
      else:
        # extend the chain
        for (c, q) in cs:
          yield from solve(chain + c, fn(n), fn, q, ds)
    
    m = Accumulator(fn=min)
    # start with the initial chain given
    for (n, c, r) in solve([(0, 0)], 1, (lambda x: x + 2), 0, ds):
      # record chains with five remaining dominoes, 4 of them doubles
      if len(r) == 5 and sum(1 for (a, b) in r if a == b) == 4:
        printf("[{n} / {c} / {r}]", c=output(c), r=output(sorted(r)))
        # record the indices of the squares
        ss = tuple(i for (i, n) in enumerate(csum(a + b for (a, b) in c)) if is_square(n) is not None)
        # we want the largest square, but the smallest indices
        m.accumulate_data((-n, ss), (c, r))
    
    # output the solution
    (c, r) = m.data
    printf("{c} / {r}", c=output(c), r=output(sorted(r)))
    

    Solution: The five remaining dominoes are: 0-2, 1-1, 2-2, 3-3, 5-5.

    There are two chains that achieve the maximum possible square with five dominoes remaining, of which four are doubles. These are:

    0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, 1-5, 5-2, 2-6, 6-3, 3-5, 5-0, 0-4, 4-6, 6-6, 6-0, 0-3, 3-1, 1-4, 4-4, 4-2 (unused: 0-2, 1-1, 2-2, 3-3, 5-5).

    0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-3, 3-1, 1-4, 4-6, 6-0, 0-5, 5-1, 1-6, 6-6, 6-2, 2-0, 0-3, 3-5, 5-5, 5-2, 2-4 (unused: 0-4, 1-1, 2-2, 3-3, 4-4).

    But the puzzle requires that the chain “could not have been shorter at any stage”. To do this I examine the indices at the chain at which square totals are achieved and choose the smallest tuple. For the two cases above the indices are:

    (0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22)
    (0, 1, 2, 3, 4, 5, 6, 8, 10, 13, 15, 19, 22)

    and so the first chain is the answer to the puzzle, as each index is ≤ the corresponding index in the other solution(s).

    But it’s not guaranteed that there would be a solution. If the second sequence went …, 10, 13, 14, 19, … then each sequence would be the shortest at different indices so there would be no overall solution that is the shortest at every stage. However given that there is a solution, it will be the smallest when they are lexicographically ordered.

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: