Enigmatic Code

Programming Enigma Puzzles

Enigma 237: Still more dominoes

From New Scientist #1383, 10th November 1983 [link]

The picture shows a full set of 28 dominoes from 0-0 to 6-6, arranged in an 8 × 7 block. This time I have shown where the 6-3 domino goes. Please mark the boundaries between the other dominoes.

Enigma 237

Note: I now have an internet connection at home so I’ll be able to resume my previous posting schedule (a new puzzle every other day). While I’ve been offline I’ve been able to keep up the posting frequency, but the actual times that puzzles were published was a bit variable (up to a day early or a day late). Over the next few days I’ll be checking all the activity that’s happened on the site while I’ve been offline (4 months!). Thank you for your patience.

[enigma237]

Advertisements

One response to “Enigma 237: Still more dominoes

  1. Jim Randell 13 November 2014 at 8:32 am

    Another domino problem. I used the same Python program as for Enigma 195. It runs in 40ms.

    from enigma import chunk, printf
    
    # grid dimensions (columns, rows)
    (N, M) = (8, 7)
    
    # number of dominoes in the grid
    D = (N * M) // 2
    
    grid = [
      4, 3, 0, 1, 1, 4, 6, 0,
      3, 2, 5, 5, 2, 5, 3, 0,
      1, 2, 4, 6, 1, 5, 6, 0,
      6, 3, 5, 3, 1, 2, 2, 4,
      1, 3, 0, 3, 5, 5, 0, 6,
      2, 4, 4, 2, 0, 1, 0, 6,
      6, 1, 3, 2, 4, 4, 5, 6,
    ]
    
    # 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
    
    # place the given domino and solve for the rest
    solve(update(grid, 14, 22, -1), 2, D, set([(3, 6)]))
    

    Solution: The arrangement of dominos is show below:

    Enigma 237 - 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: