Enigmatic Code

Programming Enigma Puzzles

Enigma 1592: Seeing spots

From New Scientist #2757, 24th April 2010 [link]

If you take a domino set and discard all those dominoes which involve a 5 or a 6, leaving 15 dominoes with a 0, 1, 2, 3 or 4 at each end, then the rest can be laid out, spotty sides up, to form a 5-by-6 rectangle. Then, taking the number of spots in each square as that square’s value, the product of each row can be calculated by multiplying together the values of the six squares in that row.

Your task is to lay out the dominoes so that the five products are all different, less than 1000, and in increasing order as you come down the rectangle. Just one row must have a product which is odd, just one must have a product which is a power of 2, and just one other must have a product which is a non-zero perfect square.

List the products of the five rows.

[enigma1592]

Advertisements

One response to “Enigma 1592: Seeing spots

  1. jimrandell 23 January 2012 at 8:54 am

    This one is easier to solve with pencil and paper, than it is to make a program to try all possibilities. Nevertheless here is a programmatic solution.

    It seemed that generating the entire solution space and then looking for an answer would take a long time, so I split the problem into two phases (much like my paper solution). The first phase considers the possible partitioning of the the six 1’s, 2’s, 3’s and 4’s to create four rows with the necessary products. Careful reading of the puzzle is required, the “just one other” part means that the square must be from one of the rows other than the odd number and the power of two. The second phase is to take each of the candidate set of rows and try to tile it with the dominoes, generating and testing possibilities for each row in turn to avoid having to test huge numbers of potential grids. Once we find a suitable tiling of the grid we stop looking.

    In the end the program runs in a very satisfactory 152ms.

    Run: [ @repl.it ]

    from collections import Counter
    from itertools import combinations, combinations_with_replacement, permutations
    from enigma import multiply, is_square
    
    # we have 6 of 0, 1, 2, 3, 4
    
    # it follows that all 0's must be in the first row
    
    # the row with the odd product must consist solely of 1's and 3's
    
    # the row that's a power of two must consist solely of 1's, 2's and 4's (i.e. not 3's)
    
    def generate():
      # we start with 6 copies of 1, 2, 3 and 4
      n1 = Counter({1: 6, 2: 6, 3: 6, 4: 6})
      # find row with the odd product (3^6 is less that 1000)
      for ones in range(0, 7):
        ro = [1]*ones + [3]*(6 - ones)
        po = multiply(ro)
    
        n2 = n1.copy()
        n2.subtract(ro)
        # the row whose product is a power of two (cannot contain 3's)
        for r2 in set(combinations(n2.elements(), 6)):
          if 3 in r2: continue
          r2 = list(r2)
          p2 = multiply(r2)
          if not(p2 < 1000): continue
    
          n3 = n2.copy()
          n3.subtract(r2)
          # find the remaining two rows
          for ra in set(combinations(n3.elements(), 6)):
            ra = list(ra)
            pa = multiply(ra)
            if not(pa < 1000): continue
            # let's find the square first
            if not(is_square(pa)): continue
            # and it can't be another odd row or power of two
            if pa % 2: continue
            if set(ra).issubset((1, 2, 4)): continue
    
            # and the remaining row
            n4 = n3.copy()
            n4.subtract(ra)
            rb = sorted(n4.elements())
            pb = multiply(rb)
            if not(pb < 1000): continue
            # it can't be square
            if is_square(pb): continue
            # and it can't be another odd row or power of two
            if pb % 2: continue
            if set(rb).issubset((1, 2, 4)): continue
    
            # yield the rows sorted by product
            yield sorted((ro, r2, ra, rb), key=multiply)
    
    
    # what dominoes do we have?
    dominoes = set(combinations_with_replacement(range(5), 2))
    
    # check to see if the rows can be tiled as dominoes
    def check(rs):
      # the top row is always 0's
      g = [tuple([0] * 6)] + [None]*4
      # take a fresh set of dominos
      ds = dominoes.copy()
      # and an empty set of domino places
      ps = [[None]*6 for i in range(5)]
      # now try possible permutations for each row...
      for g[1] in set(permutations(rs[0])):
        # and try to tile that row with dominoes
        if not fit(g, 0, ds, ps): continue
        for g[2] in set(permutations(rs[1])):
          if not fit(g, 1, ds, ps): continue 
          for g[3] in set(permutations(rs[2])):
            if not fit(g, 2, ds, ps): continue
            for g[4] in set(permutations(rs[3])):
              if not fit(g, 3, ds, ps): continue
              if not fit(g, 4, ds, ps): continue
              # we've managed to tile all the rows...
              # output the products
              print(tuple(multiply(r) for r in g))
              # output the grids
              for i in range(5):
                print(g[i], ' '.join(ps[i]), sep='   ')
              # we only need one way of fitting the dominoes
              return
    
    def fit(g, y, ds, ps):
      # find an empty square
      for x in range(6):
        if ps[y][x] is not None: continue
        # can we fit a horizontal domino in it?
        if x < 5 and ps[y][x+1] is None:
          d = tuple(sorted((g[y][x], g[y][x+1])))
          if d in ds:
            ps[y][x], ps[y][x+1] = 'W', 'E'
            ds.remove(d)
            if fit(g, y, ds, ps):
              return True
            ps[y][x] = ps[y][x+1] = None
            ds.add(d)
    
        # can we fit a vertical domino in it
        if y < 4 and ps[y+1][x] is None:
          d = tuple(sorted((g[y][x], g[y+1][x])))
          if d in ds:
            ps[y][x], ps[y+1][x] = 'N', 'S'
            ds.remove(d)
            if fit(g, y, ds, ps):
              return True
            ps[y][x] = ps[y+1][x] = None
            ds.add(d)
    
        return False
      return True
    
    
    seen = []
    for rs in generate():
      if rs in seen: continue
      check(rs)
      seen.append(rs)
    
    print("checked {n} possibilities".format(n=len(seen)))
    

    Solution: The products of the rows are 0, 24, 27, 512 and 576.

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: