Список голосов Thank You

[Димыч]

Так, я вроде решил. Для кратчайшей перестановки надо получить минимальное число циклов, в которых «место назначения» каждой фигуры там, где стоит следующая. Для перестановки фигур в цикле длины N нужен N+1 ход. Мы не можем разнести одинаковые фигуры в разные циклы — два цикла с одинаковыми фигурами можно объединить, поменяв «места назначения» этих фигур. Значит в кратчайшей перестановке все фигуры одного вида всегда будут в одном цикле. С другой стороны, в цикле должны быть фигуры минимум двух видов, иначе они уже стоят на своих местах. Из 12 различных видов фигур можно сделать максимум 6 циклов. Уникальные фигуры меняем местами попарно, получая циклы длины 2, парные меняем с также парными, получая циклы длины 4, белые пешки меняем с черными, получая цикл длины 16. Итого 3+3+5+5+5+17=38 ходов.