Carleton University - School of Computer Science
Technical Report TR-04-10
Explorations in 4-peg Tower of Hanoi
Ben Houston & Hassan Masum
Finding an optimal solution to the 4-peg version of the classic Tower of Hanoi problem has been an open problem since the 19th century, despite the existence of a "presumed-optimal" solution. We verify that the presumed-optimal Frame-Stewart algorithm for 4-peg Tower of Hanoi is indeed optimal, for up to 20 discs. We also develop a distributed Tower of Hanoi algorithm, and 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.
Back to 2004 Tech Reports