Hermit
Можно построить граф где каждой из вершин будет соответствовать определённое положение пятнашек. :) Там будет всего 6*5!=720 вершин. Соединить дугами возможный переходы поля из одного состояния в другое и посчитать минимальные пути от состояния, которое изображено на рисунке до всех возможных состояний, где 4 над пятью в правом ряду. :D Самое меньшее и будет ответом.
Всё не так плохо как Вы думаете. Всё намного хуже!