Головоломка юриста

Не рисунке изображен план тюрьмы, в которой находятся 9 темниц. В каждой из них, кроме одной, находится по узнику. Узники находятся в порядке, показанном на рисунке.

Расположить узников по порядку номеров за наименьшее число перемещений. Одного узника за один раз можно перевести по переходу в пустую темницу, но под страхом смерти запрещается двум узникам находиться в одной темнице.
Ответ на загадку:
1, 2, 3, 1, 2-6, 5, 3, 1, 2-6, 5, 3 , 2, 1-4, 8, 7,1, 2-4, 8, 7, 4, 5, 6