NIST

towers of Hanoi

(classic problem)

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.

Author: PEB

Implementation

(JavaScript)
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 5 August 2021.
HTML page formatted Thu Aug 5 16:22:42 2021.

Cite this as:
Paul E. Black, "towers of Hanoi", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 5 August 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/towersOfHanoi.html