Definition: Given three posts (towers) and n disks of decreasing sizes, move the disks from one post to another one at a time without putting a larger disk on a smaller one. The minimum is 2n-1 moves. The "ancient legend" was invented by De Parville in 1884.
Note: A solution using recursion is: to move n disks from post A to post B 1) recursively move the top n-1 disks from post A to C, 2) move the nth disk from A to B, and 3) recursively move the n-1 disks from C to B. A solution using iteration is: on odd-numbered moves, move the smallest disk clockwise. On even-numbered moves, make the single other move which is possible.
[GCG92] gives generalizations of the puzzle, algorithms, and proofs.
Background and a recursive and an iterative solution.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 November 2011.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Paul E. Black, "towers of Hanoi", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 November 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/towersOfHanoi.html