Enigmatic Code

Programming Enigma Puzzles

Enigma 1578: About turn

From New Scientist #2743, 16th January 2010 [link]

Joe placed six lettered counters on a 3-by-2 grid as shown, reading ENIGMA anticlockwise, and then he removed the E. Penny then slid the counters around, successively moving them up, down or across into a gap, so that after Joe replaced the E in its original position, the letters read ENIGMA clockwise.

What was the smallest number of counters that Penny needed to move to achieve this?

[enigma1578]

Advertisements

One response to “Enigma 1578: About turn

  1. jimrandell 9 February 2012 at 9:06 am

    The following Python code does a depth first search, and finds the solution in 44ms.

    from enigma import concat, printf
    
    # moves on the grid:
    # 0 1 2
    # 3 4 5
    # according to the empty square record the moved piece and the arrangement of the grid
    moves = (
      ( ('1', (1, 0, 2, 3, 4, 5)), ('3', (3, 1, 2, 0, 4, 5)) ), # 0
      ( ('0', (1, 0, 2, 3, 4, 5)), ('2', (0, 2, 1, 3, 4, 5)), ('4', (0, 4, 2, 3, 1, 5)) ), # 1
      ( ('1', (0, 2, 1, 3, 4, 5)), ('5', (0, 1, 5, 3, 4, 2)) ), # 2
      ( ('0', (3, 1, 2, 0, 4, 5)), ('4', (0, 1, 2, 4, 3, 5)) ), # 3
      ( ('1', (0, 4, 2, 3, 1, 5)), ('3', (0, 1, 2, 4, 3, 5)), ('5', (0, 1, 2, 3, 5, 4)) ), # 4
      ( ('2', (0, 1, 5, 3, 4, 2)), ('4', (0, 1, 2, 3, 5, 4)) ), # 5
    )
    
    # a depth first search of the possibilities
    def solve(start, finish):
      # set up the initial state and final state
      states = [ ( list(start), '' ) ]
    
      # already visited states
      visited = {}
      while states:
        next = []
        for (s, m) in states:
          s = concat(*s)
          if s in visited: continue
          if s == finish:
            printf("{start} -> {finish}: solved in {n} moves: {m}", n=len(m))
            return
          visited[s] = m
    
          for i, p in moves[s.index('E')]:
            next.append((tuple(s[x] for x in p), m+i))
        states = next
    
    
    solve('NEAIGM', 'AENMGI')
    

    Solution: The minimum number of moves is 20.

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: