# 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 2^{n}-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 *n*^{th} 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) Mukundan's animation (Java).
## More information

Background and a recursive and an iterative solution.

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 14 November 2011.

HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:

Paul E. Black, "towers of Hanoi", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 14 November 2011. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/towersOfHanoi.html