Thank you for your interest in NCTM’s Illuminations. Beginning in mid-April, all Illuminations content will be moving to nctm.org/illuminations. Interactives will remain openly available and NCTM members will have access to all Illuminations lessons with new filtering and search options. We hope you will continue to utilize and enjoy these resources on nctm.org.

## Tower of Hanoi

6-8, 9-12
Standards:
Math Content:
Number and Operations

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially three in the applet below), initially stacked in increasing size on one of three pegs.
The goal is to move all the discs from the left peg to the right one.Try to move all the discs using the smallest number of moves possible. Compete against a friend to see who can solve the puzzle in the shortest time or with the fewest number of moves.  This applet is based on the Tower of Hanoi Applet created by David Herzog.

### The Goal

The object of the game is to move all of the disks to the peg on the right.

### Rules

• Only one disc may be moved at a time.
• A disc can be placed either on an empty peg or on top of a larger disc.

### How to Use

• Click-and-drag to move a disc.
• Click the Timer checkbox to turn the timer on or off.
• Vary the difficulty by changing the number of discs. The + and - buttons increase and decrease the number of discs. You will likely have no problem with three discs, but can you solve the puzzle with 12 discs?
• If you need help, select Solution to watch the computer solve the puzzle. The Speed slide determines how fast the discs move.
• Restart returns all of the disks to the left peg.

If you’ve played the game as well as possible, you should have discovered that the minimum number of moves for 1, 2, 3, and 4 disks, respectively, is 1, 3, 7, and 15. If it took you more moves than that, then press the Solution button and watch the computer solve the tower in the minimum number of moves.

1. To figure out how many turns it’ll take for more than 4 disks, find a pattern relating the number of disks to the minimum number of turns it takes to win the game. Write down the minimum number of moves for 1, 2, 3, and 4 disks on a piece of paper. Do you see a pattern? (Hint: Add 1 to each of the numbers. Recognize a pattern now?)
2. Using the timer and a fixed speed setting, measure how long it takes to solve the problem for different number of discs. How long would it take to move 20 disks? 50? 100?
3. Some experts suggest that computing speeds doubles approximately every six months. How long before this applet will be able to finish 100 disks in a second?