Complexity of the Path Multi-Peg Tower of Hanoi. Academic Article uri icon

abstract

  • The Tower of Hanoi problem with h 4 pegs is long known to require a sub-exponential number of moves in order to transfer a pile of n disks from one peg to another. In this paper we discuss the Pathh variant, where the pegs are placed along a line, and disks can be moved from a peg to its nearest neighbor(s) only. Whereas in the simple variant there are h(h 1)/2 bi-directional interconnections among pegs, here there are only h 1 of them. Despite the significant reduction in the number of interconnections, the task of moving n disks between any two pegs is still shown to grow sub-exponentially as a function of the number of disks.

publication date

  • January 1, 2005