How to Solve the Towers of Hanoi Puzzle

This guide will allow the user to complete the towers of Hanoi puzzle with relative ease. It was also serve as a simple introduction to the topic of recursion.

• Towers of Hanoi Puzzle
• Computer or scratch paper
• Pen/pencil

The first step is to determine how many discs you are going to attempt to solve the puzzle for. We will begin with one disc and move up to 3 discs. The best way to use recursion to help you solve the puzzle is by using either scratch paper or your computer to keep track of the moves made in each step and separating them by the number of discs you used for that step. There are only a few rules to this puzzle...

1. Move all of the discs to the third pole in as few moves as possible.
2. Never place a larger disc on top of a smaller disc

With the initial set up we have one disc on the first pole. The object of the puzzle is to move the discs from pole A to pole C in as few moves as possible. For one disc this can be accomplished in one move.

Now that we have solved the puzzle for one disc we will move on to two discs. The introduction to recursion comes into play here. We remember that in the first step with one disc we were able to move from pole A to pole C in one move, while following the rules we learned in setup we know that if we did this then we would not be able to move the second disc to pole C without violating rule two and placing the larger disc on the smaller one. To solve this we would instead start by moving the first disc to pole B and then the second disc to pole C. Now we are able to place the smaller disc onto pole C without violating any rules and this puzzle has been solved in 3 moves. The pattern that starts to emerge is the number of moves from the previous step, then the new move with the introduction of the new disc plus the moves from the previous step. Lets try to show this in the next step.

With three discs we will use recursion to solve this problem. In the first two steps, we saw that it took one move for one disc and three moves for two discs. This means that following our formula for three discs it will take 3 + 1 + 3 = 7 moves to solve. Now knowing the number of moves is pointless if you don't know how to make the moves. we saw previously that if we modified the moves we made for one disc, we could solve for two discs. Now taking the moves we saw for two discs and trying to solve them for getting the third disc to pole C.

Using what we saw in step 3 we can create a pattern that helps us solve for any number of discs. By solving the step before we know how to get all of the discs from pole A to pole C without violating the rule. By switching what we did for pole C to pole B we can solve the puzzle for the previous step and then move the new largest disc to pole C, then by retracing the steps we took to get all of the discs to pole B we can then shift them all to pole C and complete the puzzle. This is what recursion is, by using the solutions to the previous problem we can solve the new problem as it grows larger.