On the design of a constructive algorithm to solve the multi-peg towers of Hanoi problem
The multi-peg Towers of Hanoi problem is still open. No provably optimal constructive algorithm to solve the problem is known. The minimum number of moves required is also unknown. This paper analyses the properties of an optimal algorithm and presents a deterministic algorithm to solve the problem. An execution trace of the algorithm is given. An important conjecture called the serialization conjecture is presented. The proposed algorithm is proved to be optimal subject to thc validity of the conjecture. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
towers of hanoi combinatorial problem design of algorithm recursive formulation dynamic programming combinatorial explosion