Enigmatic Code

Programming Enigma Puzzles

Tantalizer 447: Marching order

From New Scientist #998, 29th April 1976 [link]

Brother Ambrose, in cell A, desires to visit the chapel, M, for compline. But he belongs to a stern and silent order, which keeps movement and contact to a minimum. No monk may ever enter an occupied room or halt in a corridor. Only one monk may be in movement at any time. Luckily the order is a bit below strength at present and there are only Ambrose, Bernard, Crispin, Ethelbert, Francis, Hadrian, Imogius, Keith and Leo, each in the cell of their letter.

Call it one move when a monk moves from one room to another (possibly passing through other unoccupied rooms). In how few moves can Ambrose get to the chapel, and each other monk return to his own cell?

[tantalizer447]

One response to “Tantalizer 447: Marching order

  1. Jim Randell 15 August 2018 at 8:50 am

    I started off with a depth-first search, but that was taking too long. So I implemented that a breath-first search that attacks the problem from both the initial and final positions, until they meet in the middle.

    There are only 4 unoccupied squares so this limits the maximum length of each move, but even on this simple graph with the additional restriction on the length of moves this approach takes a while to run.

    This Python code executes in 8.3s.

    Run: [ @repl.it ]

    from enigma import irange, update, join, printf
    
    # labels for the cells
    cells = (A, B, C, D, E, F, G, H, I, J, K, L, M) = irange(0, 12)
    
    # adjacent cells
    adj = [
      [B], # A
      [A, C], # B
      [B, D, E], # C
      [C], # D
      [C, F], # E
      [E, G, H], # F
      [F], # G
      [F, I], # H
      [H, J, K], # I
      [I], # J
      [I, L], # K
      [K, M], # L
      [L], # M
    ]
    
    # determine paths up to length 4 (by index)
    paths = list()
    for s in cells:
      row = [None] * 13
      ps = [[s]]
      while ps:
        ps2 = list()
        for p in ps:
          if len(p) > 1:
            # record this path
            row[p[-1]] = set(p[1:])
          if len(p) < 5:
            # extend this path
            for x in adj[p[-1]]:
              if x not in p:
                ps2.append(p + [x])
        ps = ps2
      paths.append(row)
    
    # possible moves 
    def advance(cells, x):
      # find the vacant cells
      vacant = set(i for (i, v) in enumerate(cells) if v == '.')
      # consder each vacant cell as a target
      for t in vacant:
        # find vacant paths to this cell
        for (s, ps) in enumerate(paths):
          m = cells[s]
          if m == '.' or (x and m == x): continue
          # can monk <m> move from <s> to <t>
          p = ps[t]
          if p and vacant.issuperset(p):
            yield (m, s, t)
    
    # reverse a sequence of moves
    reverse = lambda ms: list((m, t, s) for (m, s, t) in reversed(ms))
    
    # find a minimal sequence of moves from <start> to <final>
    def solve(start, final):
      if start == final: return []
      (d0, d1, f) = ({ tuple(start): [] }, { tuple(final): [] }, 1)
      while d0:
        d2 = dict()
        for (cells, ms) in d0.items():
          for (m, s, t) in advance(cells, (ms[-1][0] if ms else None)):
            cells2 = tuple(update(list(cells), (s, t), ('.', m)))
            ms2 = d1.get(cells2, None)
            if ms2: return (ms + [(m, s, t)] + reverse(ms2) if f else ms2 + reverse(ms + [(m, s, t)]))
            if cells2 not in d2: d2[cells2] = ms + [(m, s, t)]
        (d0, d1, f) = (d1, d2, not(f))
    
    # using . to indicate an unnocupied cell, mark the desired start and final states
    #             ABCDEFGHIJKLM
    start = list('ABC.EF.HI.KL.')
    final = list('.BC.EF.HI.KLA')
    
    # find a minimal sequence of moves
    ms = solve(start, final)
    printf("{n} moves: [({start}) -> ({final})]", n=len(ms), start=join(start), final=join(final))
    for (i, (m, s, t)) in enumerate(ms, start=1):
      printf("  {i}: {m} moves from {s} to {t}")
    

    Solution: The minimal number of moves required for Ambrose to get to the chapel and all the other monks to return to their cells is 28.

    In the program I label the cells from 0 (=A) to 12 (=M), the 28 move solution it produces is:

    1: L moves from 11 to 12
    2: K moves from 10 to 11
    3: I moves from 8 to 10
    4: H moves from 7 to 9
    5: F moves from 5 to 8
    6: E moves from 4 to 7
    7: C moves from 2 to 5
    8: B moves from 1 to 4
    9: A moves from 0 to 3
    10: B moves from 4 to 0
    11: C moves from 5 to 1
    12: A moves from 3 to 6
    13: E moves from 7 to 3
    14: F moves from 8 to 2
    15: H moves from 9 to 4
    16: A moves from 6 to 9
    17: I moves from 10 to 6
    18: K moves from 11 to 5
    19: L moves from 12 to 7
    20: A moves from 9 to 12
    21: L moves from 7 to 11
    22: K moves from 5 to 10
    23: I moves from 6 to 8
    24: H moves from 4 to 7
    25: F moves from 2 to 5
    26: E moves from 3 to 4
    27: C moves from 1 to 2
    28: B moves from 0 to 1

    The first 20 moves get A to the chapel (12), and the remaining 8 moves are required to move the remaining 8 monks back to their cells.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: