Предположение такое:
Сформировать двудольный граф, одна доля которого содержит конечные положения, вторая начальные, а ребра соответствуют возможным переходам. Большинство чисел могут прийти на свое место из начальных позиций, удаленных влево и вправо не более, чем на счетчик (с шагом 2), но, скажем, единица направо двигаться не может, так что для нее только одно направление остается, и другие ограничения надо аккуратно рассмотреть.
Для полученного графа ищутся все совершенные паросочетания (в данном случае они же и реберные покрытия).
|