**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]

### Like this:

Like Loading...

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 ]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:

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.