Free puzzles / Question / Magic Squares Problem.
The Spanish Dungeon.
Not fifty miles from Cadiz stood in the middle ages a castle, all traces
of which have for centuries disappeared. Among other interesting
features, this castle contained a particularly unpleasant dungeon
divided into sixteen cells, all communicating with one another, as shown
in the illustration.
Now, the governor was a merry wight, and very fond of puzzles withal.
One day he went to the dungeon and said to the prisoners, "By my
halidame!" (or its equivalent in Spanish) "you shall all be set free if
you can solve this puzzle. You must so arrange yourselves in the sixteen
cells that the numbers on your backs shall form a magic square in which
every column, every row, and each of the two diagonals shall add up the
same. Only remember this: that in no case may two of you ever be
together in the same cell."
One of the prisoners, after working at the problem for two or three
days, with a piece of chalk, undertook to obtain the liberty of himself
and his fellow-prisoners if they would follow his directions and move
through the doorway from cell to cell in the order in which he should
call out their numbers.
He succeeded in his attempt, and, what is more remarkable, it would seem
from the account of his method recorded in the ancient manuscript lying
before me, that he did so in the fewest possible moves. The reader is
asked to show what these moves were.
Answer
+-----+-----+-----+-----+
| | | | |
| 8 | 5 | 10 | 11 |
|_____|_____|_____|_____|
| | | | |
| 16 | 13 | 2 | 3 |
|_____|_____|_____|_____|
| | | | |
| 1 | 12 | 7 | 14 |
|_____|_____|_____|_____|
| | | | |
| 9 | 4 | 15 | 6 |
| | | | |
+-----+-----+-----+-----+
In attempting to solve this puzzle it is clearly necessary to seek such
magic squares as seem the most favourable for our purpose, and then
carefully examine and try them for "fewest moves." Of course it at once
occurs to us that if we can adopt a square in which a certain number of
men need not leave their original cells, we may save moves on the one
hand, but we may obstruct our movements on the other. For example, a
magic square may be formed with the 6, 7, 13, and 16 unmoved; but in
such case it is obvious that a solution is impossible, since cells 14
and 15 can neither be left nor entered without breaking the condition of
no two men ever being in the same cell together.
The following solution in fourteen moves was found by Mr. G.
Wotherspoon: 8-17, 16-21, 6-16, 14-8, 5-18, 4-14, 3-24, 11-20, 10-19,
2-23, 13-22, 12-6, 1-5, 9-13. As this solution is in what I consider the
theoretical minimum number of moves, I am confident that it cannot be
improved upon, and on this point Mr. Wotherspoon is of the same opinion.