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.
The above is a trustworthy plan of a certain Russian prison in Siberia. All the cells are numbered, and the prisoners are numbered the same as the cells they occupy. The prison diet is so fattening that these political prisoners are in perpetual fear lest, should their pardon arrive, they might not be able to squeeze themselves through the narrow doorways and get out. And of course it would be an unreasonable thing to ask any government to pull down the walls of a prison just to liberate the prisoners, however innocent they might be. Therefore these men take all the healthy exercise they can in order to retard their increasing obesity, and one of their recreations will serve to furnish us with the following puzzle.
Show, in the fewest possible moves, how the sixteen men may form themselves into a magic square, so that the numbers on their backs shall add up the same in each of the four columns, four rows, and two diagonals without two prisoners having been at any time in the same cell together. I had better say, for the information of those who have not yet been made acquainted with these places, that it is a peculiarity of prisons that you are not allowed to go outside their walls. Any prisoner may go any distance that is possible in a single move.