Enigmatic Code

Programming Enigma Puzzles

Enigma 1519: Dominotrix

From New Scientist #2681, 8th November 2008 [link]

Our toddler granddaughter has been staying with us, and she has used our standard set of dominoes (each twice as long as broad) for building castles. Now that she has gone home I have managed to find most of the set, and I can divide these into two unequal lots. Each lot can be arranged into a solid square, and can also be arranged into a closed ring (for example, 6-4#4-2#2-2#2-6). The total number of “pips” in each lot sum to a perfect square.

Which dominoes are still lost?

[enigma1519]

Advertisements

One response to “Enigma 1519: Dominotrix

  1. Jim Randell 11 September 2012 at 6:48 pm

    The following Python program runs in 6.4s (under PyPy).

    As noted in the comments in the code, in the initial stages of the computation it can be deduced analytically what the solution to the puzzle is. But we want to see a constructive solution, so the program goes on to generate all possible sets of dominoes that satisfy the conditions of the puzzle, and verify that they all correspond to the solution.

    My original Perl code ran in 2m6s.

    from itertools import combinations
    from collections import defaultdict
    from enigma import irange, is_square, printf
    
    # let's start with a standard domino set
    # each domino is two squares
    dominoes = set((i, j) for i in irange(0, 6) for j in irange(i, 6))
    
    # count the dominoes, squares and pips
    nd = len(dominoes)
    ns = 2 * nd
    np = sum(sum(d) for d in dominoes)
    printf("totals: {nd} dominoes, {ns} squares, {np} pips")
    
    # the smallest ring uses 4 dominoes (and 8 squares)
    # an even number of dominoes can make a ring
    # so find rings that use a square number of squares
    rings = list(n for n in irange(4, nd, 2) if is_square(2 * n))
    printf("rings: {rings}")
    
    # at this point we see that there are only two possibilities for the rings
    # one with 18 dominoes and one with 8 dominoes
    # (and the remaining two dominoes are missing ones)
    
    # the set of 18 dominoes must form an even square between 76 and 140
    # so it must be 100
    # and the set of 8 dominoes must form an even square between 19 and 77
    # i.e. 36 or 64
    # as the total sum of the complete set is 168 it follows that sets must be:
    # (18 -> 100, 8 -> 64, 2 -> 4) or (18 -> 100, 8 -> 36, 4 -> 32)
    # but the lost set of 2 must sum between 1 and 23 so that leaves only the first possibility.
    
    # so there are two missing dominoes that sum 4
    # i.e. (0-0, 1-3), (0-0, 2-2), (0-1, 1-2)
    # but as the pips on both the rings come in even counts that means that the pips on the
    # lost set must also come in pairs, leaving (0-0, 2-2) as the only possibility
    
    # but we want a constructive proof, so let's carry on...
    
    # try to complete the ring r, using dominoes ds
    def make_ring(r, ds):
      n = len(ds)
      if n == 0:
        if r[0] != r[-1]: return None
        return r
    
      # place the next domino
      for i in range(n):
        (a, b) = ds[i]
        if a == r[-1]:
          rr = make_ring(r + [a, b], ds[:i] + ds[i+1:])
          if rr: return rr
        elif b == r[-1]:
          rr = make_ring(r + [b, a], ds[:i] + ds[i+1:])
          if rr: return rr
    
    # see if the dominoes in ds can form a ring
    def ring(ds):
      # count the pips
      ps = defaultdict(int)
      for a, b in ds:
        ps[a] += 1
        ps[b] += 1
      # they must come in pairs to form a ring
      if any(v % 2 > 0 for v in ps.values()): return None
    
      # remove any doubles from the ring
      # (although there must be non-doubles too)
      doubles = list(a for a, b in ds if a == b)
      if any(ps[d] == 2 for d in doubles): return None
      ds2 = list((a, b) for a, b in ds if a != b)
    
      # can we make a ring from the remaining dominoes?
      return make_ring(list(ds2[0]), ds2[1:])
    
    # find combinations of the rings that leave a few dominoes missing
    lost = defaultdict(int)
    for (a, b) in combinations(rings, 2):
      if not(a < b): (a, b) = (b, a)
      r = nd - (a + b)
      if not(r > 0): continue
      printf("considering rings of length {a} & {b}, with {r} dominoes missing")
    
      # select set a of the dominoes
      for da in combinations(dominoes, a):
        pa = sum(sum(d) for d in da)
        # the sum of the ring must be even, and a sqaure
        if pa % 2 > 0: continue
        if not is_square(pa): continue
        # can we form a ring with them?
        ra = ring(da)
        if not ra: continue
        # now pick the remainder of the dominoes
        for dr in combinations(dominoes.difference(da), 2):
          pr = sum(sum(d) for d in dr)
          # and the total of set b will be...
          pb = np - (pa + pr)
          # and that sum must also be an even square
          if pb % 2 > 0: continue
          if not is_square(pb): continue
          # can set b form a ring?
          db = dominoes.difference(da, dr)
          rb = ring(db)
          if not rb: continue
          lost[tuple(sorted(dr))] += 1
          printf("lost dominoes: {dr}", dr=sorted(dr))
          printf("set a: {da}, pips={pa}", da=sorted(da))
          printf("ring a: {ra}")
          printf("set b: {db}, pips={pb}", db=sorted(db))
          printf("ring b: {rb}")
          printf()
    
    for (k, v) in lost.items():
      printf("lost dominoes: {k} [{v} solutions]")
    

    Solution: The lost dominoes are 0-0 (double blank) and 2-2 (double two).

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: