Now, consider a permutation puzzle [1]} on a transposition tree described as follows: Given a transposition tree \(T\)  having \(n\)  vertices labeled from 1 to \(n\) , place \(n\)  markers, each of which is labeled from 1 to \(n\) , at the vertices of \(T\)  arbitrarily in such a way that each vertex of \(T\)  is paired with an exactly one marker. Let \(P\)  be such an arbitrary initial position of markers. Each legal move of the puzzle is to interchange the markers placed at the ends of an edge in \(T\) . The terminal position of markers, denoted \(Q\) , is the position in which each marker is paired with each vertex of \(T\)  having the same label. The puzzle is to find a sequence of legal moves from a given initial position \(P\)  to the final position \(Q\)  with the minimum number of legal moves.
