We close this section by describing the main ideas behind Theorem REF  (an interested reader may refer to [1]} for further details). Consider a permutation puzzle on a transposition tree \(T\)  having \(n\)  vertices. Let \(p\)  be a permutation for position \(P\)  as an assignment of \(n\)  markers to the \(n\)  vertices of \(T\) . The marker \(i\)  is said to be homed if \(i=p(i)\) . If there exists any unhomed marker in the assignment, either one of two cases occurs. The first case is that there exists an edge of \(T\)  involving two unhomed markers \(x\)  and \(y\)  such that they need to move toward each other for the final position \(Q\) . The second case is that there exists an edge of \(T\)  involving one unhomed marker \(x\)  and one homed marker \(y\)  such that \(x\)  needs to move toward \(y\)  for the final position \(Q\) . In both cases, interchanging markers \(x\)  and \(y\)  reduces the number of steps in Theorem REF . Finally, if there is no such case in the assignment (i.e., all markers are homed), then the number is reduced to 0.
