Parallelism for multipeg towers of Hanoi

This paper studies parallelism for the multipeg Towers of Hanoi problem, an interesting generalization of the traditional one, by allowing concurrent moves of discs in a single step. Three versions of parallelism are investigated based on two factors: the order of moves of discs and the resource utilization of pegs. Solutions obtained include the minimum numbers of steps and algorithms for moving discs in the minimum numbers of steps. A common technique is presented for deriving the nonrecursive computation of minimum numbers of steps, which discloses a methodology for the study of parallelism in the multipeg Towers.