Explorations in 4-Peg Tower of Hanoi

Ben Houston
Exocortex Technologies
Hassan Masum
Carleton University


We verify that the presumed-optimal Frame-Stewart algorithm for 4-peg Tower of Hanoi is optimal, for up to 20 discs.  In addition, we (a) develop a distributed Tower of Hanoi algorithm, and (b) present 2D and 3D representations of the state transition graphs.  Finally, two variants (k-out-of-order and k-at-a-time) and an analogy with distributed agent software are suggested.

Full Paper Download

Ben Houston and Hassan Masum.  "Explorations in 4-peg Tower of Hanoi."  Carleton University Technical Report TR-04-10, November 2004.  [pdf]

Supplemental Web Materials

2D projections of 4-peg Tower of Hanoi with 2, 3, 4 and 5 discs

3D animations of 4-peg Tower of Hanoi
with 2 and 3 discs

Distributed Tower of Hanoi solver