Enigmatic Code

Programming Enigma Puzzles

Enigma 1314: Times table

From New Scientist #2472, 6th November 2004

Enigma 1314

From a full set of dominoes, I have taken just those that have a 1, 2, 3 or 4 at each end. I then arranged them into a rectangle, as shown, with each domino occupying two adjacent squares. The numbers are the product of the entries in that row or column. Just four dominoes are horizontal.

Which ones?

[enigma1314]

Advertisements

One response to “Enigma 1314: Times table

  1. Jim Randell 25 June 2014 at 8:29 am

    This Python program tries to fit the dominoes into the grid recursively, checking the products as rows and columns are completed. It runs in 3.2s.

    from enigma import diff, multiply, chunk, sprintf, printf
    
    # numbers of rows and columns in the grid
    (R, C) = (4, 5)
    
    # the products of the rows and columns
    rows = (8, 768, 12, 108)
    columns = (36, 4, 64, 18, 48)
    
    # the dominoes to place
    dominoes = (
      (1, 1), (1, 2), (1, 3), (1, 4),
      (2, 2), (2, 3), (2, 4),
      (3, 3), (3, 4),
      (4, 4),
    )
    
    # update the grid, checking the products as rows/columns are completed
    def update(g, *vs):
      g = list(g)
      for (i, v) in vs:
        g[i] = v
        # check products
        (r, c) = divmod(i, C)
        # are we completing a row?
        row = g[r * C:r * C + C]
        if None not in row and multiply(row) != rows[r]: return
        # are we completing a column?
        col = g[c:R * C:C]
        if None not in col and multiply(col) != columns[c]: return
      return g
    
    # g - grid so far
    # ds - dominoes remaining
    # h - count of horizontal dominoes
    # s - sequence of placements
    def solve(g, ds, h=0, s=[]):
      # are we done?
      if not ds:
        if h == 4:
          # show the layout
          printf("{s}", s=' '.join(sprintf("[{a}-{b}]@({p},{q})") for (p, a, q, b) in s))
          # find the horizontal dominoes
          hs = sorted((a, b) for (p, a, q, b) in s if q == p + 1)
          printf("{h} horizontal => {hs}", hs=' '.join(sprintf("[{a}-{b}]") for (a, b) in hs))
      elif h < 5:
        # find the next non-empty spot
        i = g.index(None)
        (r, c) = divmod(i, C)
        # determine placements for the domino
        ps = list()
        # try to fit the domino horizontally
        if c < C - 1 and g[i + 1] is None: ps.append((i, 1))
        # try to fit the domino vertically
        if r < R - 1 and g[i + C] is None: ps.append((i, C))
        for (i, j) in ps:
          for d in ds:
            # try to fit the domino one way
            (a, b) = d
            g2 = update(g, (i, a), (i + j, b))
            if g2: solve(g2, diff(ds, [d]), (h + 1 if j == 1 else h), s + [(i, a, i + j, b)])
            # try to fit the domino the other way
            if a == b: continue
            g2 = update(g, (i, b), (i + j, a))
            if g2: solve(g2, diff(ds, [d]), (h + 1 if j == 1 else h), s + [(i, b, i + j, a)])
    
    # start with an empty grid and all the dominoes
    solve([None] * (R * C), dominoes)
    

    Solution: The four horizontal dominoes are: 1-2, 2-2, 3-4 and 4-4.

    Here is a diagram of the layout of the dominoes (horizontal dominoes are shown in red, vertical dominoes in blue):

    Enigma 1314 - Solution

    There are two other ways to lay out the dominoes which give the same numerical grid, but each of them has six horizontal dominoes:

    Enigma 1314 - Other Layout 1

    Enigma 1314 - Other Layout 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: