Multi-peg Tower of Hanoi

We consider Stewart's algorihm for solving the multi-peg Hanoi Tower problem.

Algorithm

Stewart's algorithm solves the -peg -disc from source to destination as follows:

• choose a height (see below) ;
• move the -high upper part of the tower to any peg different from source and destination, say number peg ;
• move the -high lower part from source to destination using all pegs except ;
• move the from to destination.

See below for an illustration of this algorithm for n=10 discs.

(Short) analysis

The number of steps to solve the -peg -disc problem satisfies the recurrence relation:

with

and

for all

For any , an optimal choice is any element of the argmin set . The number of paths that can generated by the algorithm satisfies the following recurrence:

with

if

or

.

Below are some empirical curves of the above quantities.

• p=3

• p=4

• p=5

• p=6

• p=7

• p=8

• p=9

Graphical illustration of the algorithm

• 3 pegs:

• 4 pegs:

• 5 pegs:

• 6 pegs:

References

Sandi Klavžar, Uroš Milutinović, Ciril Petr. On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem. Discrete Applied Mathematics. Volume 120, Issues 1–3, 15 August 2002, Pages 141-157.
Thierry Bousch. La quatrième tour de Hanoï. Bull. Belg. Math. Soc. Simon Stevin Volume 21, Number 5 (2014), 895-912.