# Tower of Hanoi

Rings:

Steps: 0

## About the Tower of Hanoi

The Tower of Hanoi is a game created by Édouard Lucas, a French mathematician, in 1883. The object of the game is to move the stack of $$n$$ disks to another rod, in their original order. Only one disk may be moved at a time, and a disk may never be placed on top of a smaller disk. The minimum number of moves required in any game is $$2^n - 1$$.

## Using the Applet

Choose the number of disks you would like to start with from the menu. Click on a stack to select its top disk, then click the stack you would like to move that disk to. You cannot place a disk onto a stack with a smaller disk. To unselect a disk, click on its stack again.

The text field next to the game displays a binary string that tracks the movements of each disk. The $$i$$ bit in the string refers to the $$i$$ disk, where the largest disk has index 0. When a disk is moved, its state is changed. Note that the sequence of strings does not encode where the disk was placed nor the current state of the game at any time; only the identity of each disk moved is recorded. One of the optimum solutions to the puzzle will yield the Gray code.