Enigmatic Code

Programming Enigma Puzzles

Enigma 1468: Paving the way

From New Scientist #2629, 10th November 2007

This is a view of the 36 flagstones of Joe’s patio.

Joe has numbered them, so that starting on flagstone 1 (shown) and stepping from one flagstone (not diagonally) to an adjacent one in order, one will finish back on flagstone 1 after stepping on all the other 35. The arrows indicate in which direction to step from certain flagstones.

What are the numbers of the flagstones E, N, I, G, M and A?

[enigma1468]

Advertisements

One response to “Enigma 1468: Paving the way

  1. Jim Randell 29 January 2013 at 8:16 am

    The following Python program runs in 360ms.

    from enigma import chunk, sprintf, printf
    
    # make a 6x6 grid
    g = [0] * 36
    
    # make a list of adjacent squares
    adj = []
    for p in range(36):
      s = []
      y, x = divmod(p, 6)
      if x > 0: s.append(p - 1) # left
      if x < 5: s.append(p + 1) # right
      if y > 0: s.append(p - 6) # up
      if y < 5: s.append(p + 6) # down
      adj.append(s)
    
    # but some moves are restricted
    adj[8] = [2]
    adj[15] = [21]
    adj[26] = [32]
    adj[29] = [28]
    
    def output(g):
      # output the grid
      for r in chunk(g, 6):
        print(' '.join(sprintf("{x:2d}") for x in r))
      printf("ENIGMA = {x}", x=g[18:24])
    
    # solve the grid
    # p - current position
    # g - grid
    def solve(n, p, g):
      g[p] = n
      # are we done
      if n == 36:
        # check we are adjacent to the square with 1 in
        if any(g[i] == 1 for i in adj[p]): output(g)
        return
      # consider the squares adjacent to p
      for q in adj[p]:
        if g[q]: continue
        solve(n + 1, q, g)
        g[q] = 0
    
    # solve the grid from square 10
    solve(1, 10, g)
    

    Solution: The flagstones under ENIGMA are 15, 20, 21, 24, 33, 34.

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: