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