Enigmatic Code

Programming Enigma Puzzles

Enigma 195: More dominoes

From New Scientist #1341, 20th January 1983 [link]

The picture shows a full set of 28 dominoes, from 0-0 to 6-6, arranged in an 8 × 7 block. Please mark in the boundaries between the dominoes.

Enigma 195

[enigma195]

Advertisements

One response to “Enigma 195: More dominoes

  1. Jim Randell 30 May 2014 at 9:10 am

    The same code used for Enigma 179 can be used to solve this puzzle.

    This Python program runs in 57ms.

    from enigma import chunk, printf
    
    # grid dimensions (columns, rows)
    (N, M) = (8, 7)
    
    # number of dominoes in the grid
    D = (N * M) // 2
    
    grid = [
      2, 3, 1, 5, 3, 3, 0, 4,
      2, 4, 4, 6, 6, 4, 5, 2,
      6, 5, 0, 0, 2, 4, 3, 3,
      0, 5, 0, 1, 0, 4, 1, 5,
      3, 3, 6, 1, 4, 6, 1, 4,
      1, 5, 5, 2, 0, 0, 1, 6,
      2, 1, 6, 6, 3, 2, 2, 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 195 - 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: