HermitМожно построить граф где каждой из вершин будет соответствовать определённое положение пятнашек. 
Там будет всего 6*5!=720 вершин. Соединить дугами возможный переходы поля из одного состояния в другое и посчитать минимальные пути от состояния, которое изображено на рисунке до всех возможных состояний, где 4 над пятью в правом ряду. 
Самое меньшее и будет ответом.
MentВы заучились, батенька. Впрочем, с удовольствием на это посмотрю.
Без проблем!
http://www.hermit.besaba.com/project1.ex-Там где 10000 - значит пути нет.
Добавлено через 1 минуту
Извините, что не очень красиво и удобно, просто делал в жутчайшей спешке, чтобы разблокировать тему.