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