A recursive algorithm for the multi-peg tower of hanoi problem

Abstract

This paper gives a recursive algorithm to solve the multi-peg Tower of Hanoi problem. The algorithm is based on the dynamic programming equation satisfied by the optimal value function, M(n, p), where M(n, p) denotes the minimum number of moves required to solve the problem with n discs and p pegs. This algorithm is the only one available, particularly for the case when p⩾5.

Keywords:

• Algorithms
• Multi-Peg Tower of Hanoi
• minimum partition numbers
• recurrence relations

C.R. Categories:

• F.2.2
• G.2.1

AMS (1991) Subject Classification:

• Primary 90C31