An analysis of the generalized Towers of Hanoi problem

A state-space graph for representing the states and their transitions ofn discs on three pegs is formulated. It is then transformed to a shortest-path tree for representing the shortest paths in transferringn discs in any configurations to a specified peg. The shortest-path tree clearly characterizes the generalized Towers of Hanoi problem; and its use leads to a very simple analysis of the generalized problem. The best-case, the worst-case and the average-case complexities are analyzed.