# 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)

[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
# 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] 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.

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