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 Black.
Entry modified 22 April 2019.
HTML page formatted Mon Apr 22 12:17:39 2019.
Cite this as:
Paul E. Black, "towers of Hanoi", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 22 April 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/towersOfHanoi.html