The Man of Law's Puzzle

This puzzle has the elegance of fitting into two of my on going puzzle collections. Firstly it is the second of the Canterbury Puzzles by Dudeney, part 1 here, and secondly it is a prisoner themed puzzle, parts 1, 2 and 3 available.

The Man of Law guards a prison with 9 dungeons. Between the cells are narrow passageways that the guards can shuttle prisoners along. Each of the prisoners are numbered from 1 to 8 and are initially arranged as below but the Man of Law wants to move them into order, starting with number 1 in the left most room.

To quote the book itself: "The prisoner may move at a time along the passage to the dungeon that doth happen to be empty, but never, on pain of death, may two men be in any dungeon at the same time. How may it be done? If the reader makes a rough plan on a sheet of paper and uses numbered counters he will find it an interesting pastime to arrange the prisoners in the fewest possible moves. As there is never more than one vacant dungeon at a time to be moved into, the moves may be recorded in this simple way, 3-2-1-6, and so on."

Sorry about the inherent sexism, but worth it for the word "doth". Anyway, off you go. Answer and analysis at the bottom.

Notice that we can arrange the dungeon in a much more pleasing way as a square. This becomes the equivalent of the 8-puzzle (perhaps more famous in its 15-puzzle form). Dudeney was actually the inventor of this sort of sliding problem, although the Man of Law's Puzzle was written after he had made wooden versions of the same thing. 

The shortest solution to the original problem takes 26 moves and one such way to achieve that move count is: 1, 2, 3, 1, 2, 6, 5, 3, 1, 2, 6, 5, 3, 1, 2, 4, 8, 7, 1, 2, 4, 8, 7, 4, 5, 6.

For the 8 puzzle in general here's a graph showing the maximum number of moves needed for different starting positions:

Optimum move length for different starting positions.

Notice the odd/even parity causing a little dip at the top of the bell curve and the freakish 2 set ups that require 31 moves on the right hand side of the graph (they are mirror images of each other and have everything in exactly the wrong place). As the puzzles get bigger it gets harder to work out the optimum solution and the whole thing is np complete. We seem to have solved the 4x4 case as a maximum of 80 moves, but beyond that we only have bounds.