The complexity of an optimal algorithm for the generalized tower of hanoi problem

Abstract

The Generalized Tower of Hanoi Problem is the transformation of an arbitrary initial configuration of n discs distributed among three pegs to an arbitrary final configuration, subject to the well-known Tower of Hanoi rules.The total number of disc moves in an optimal algorithm for this problem is computed, and expressed in terms of two binary numbers. A simple criterion is derived, to decide whether in an optimal algorithm the largest disc is moved once or twice

Keywords:

• Tower of Hanoi problem
• optimal algorithm
• complexity