Enigmatic Code

Programming Enigma Puzzles

Enigma 179: Dominoes

From New Scientist #1324, 23rd September 1982 [link]

Enigma 179

“Let’s have an easier one,” said Uncle Dick. So here is an easier one, based on an idea of George Glæser which I heard from John Mason. The picture shows a full set of 21 dominoes, from 0-0 to 5-5, arranged in a 6 × 7 block. All I ask you to do is mark in the boundaries between the dominoes. There is only one possible arrangement.

[enigma179]

Advertisements

One response to “Enigma 179: Dominoes

  1. Jim Randell 27 March 2014 at 8:30 am

    This Python program works by pairing up the squares, either horizontally or vertically, to divide the grid into non-duplicate dominoes. It labels the pairings with negative numbers to distinguish them from the domino pips. The program runs in 39ms.

    from enigma import chunk, printf
    
    # grid dimensions (columns, rows)
    (N, M) = (6, 7)
    
    # number of dominoes to fit
    D = (N * M) // 2
    
    grid = [
      0, 0, 1, 4, 5, 2,
      4, 4, 0, 2, 4, 2,
      4, 3, 2, 3, 1, 0,
      5, 3, 5, 1, 1, 0,
      5, 3, 1, 5, 3, 5,
      3, 0, 4, 2, 2, 1,
      1, 2, 4, 3, 0, 5,
    ]
    
    # update grid <g> placing domino <n> at <i>, <j>
    def update(g, i, j, n):
      g = list(g)
      g[i] = g[j] = n
      return g
    
    # g = grid
    # n = label of next domino (1 to D)
    # D = number of dominoes to place
    # ds = dominoes already placed
    def solve(g, n, D, ds):
      # are we done?
      if n > D:
        # output the pairings
        for r in chunk(g, N):
          print(r)
        print()
      else:
        # find the next unassigned square
        for (i, d) in enumerate(g):
          if d < 0: continue
          (y, x) = divmod(i, N)
          # find placements for the domino
          js = list()
          # horizontally
          if x < N - 1 and not(g[i + 1] < 0): js.append(i + 1)
          # vertically
          if y < M - 1 and not(g[i + N] < 0): js.append(i + N)
          # try possible placements
          for j in js:
            d = tuple(sorted((g[i], g[j])))
            if d not in ds:
              solve(update(g, i, j, -n), n + 1, D, ds.union([d]))
          break
    
    solve(grid, 1, D, set())
    

    Solution: The arrangement of dominoes is shown below:

    Enigma 179 - Solution

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: