The Solution to the Towers of Hanoi
Created | Updated Jul 28, 2003
The Problem
The towers of Hanoi starts with three pegs, with different sized discs on the left peg (as shown below):
There are two rules for moving the discs:
- Only one disc may be moved at once.
A disc may only be moved onto an empty peg, or onto a larger sized disc (i.e. a larger disc cannot be placed on top of a smaller one).
The aim is to move the whole tower from the left peg onto the right peg in the smallest possible number of moves. The number of discs can vary, but the greater the number of discs the more moves are required to complete the puzzle, and the more difficult the puzzle becomes.
This is the solution to the problem when there are three discs:
The fewest number of moves in which the puzzle with three discs can be completed is seven moves.
The problem therefore is this:
puzzle can be completed for a given number of discs?
The Solution
The solution to this problem can be found by beginning with the simplest case, with just one disc:
To complete the puzzle in the fewest number of moves, the disc can simply be moved from the left peg to the right peg. |
The solution to the puzzle with one disc is one move. This can now be used to solve the puzzle for two discs:
To complete the puzzle in the fewest number of moves, the small disc must be moved onto the middle peg (to allow the bottom disc to be moved onto the right peg). This first move is the same as the solution to the puzzle with one disc, but this time the disc is being moved to a different peg. |
The next move is to move the large disc to the right peg. |
The puzzle can now be completed by moving the small disc onto the right peg. This move is again the same as the solution to the puzzle with one disc, but from a different peg. |
The solution to the puzzle with two discs is three moves. For the puzzle with two discs to be completed, the move to complete the puzzle with one disc must be made to move the small disc onto the centre peg, followed by a move of the large disc onto the right peg, followed again by the move to complete the puzzle with one disc to move the small disc onto the right peg. In other words, to complete the puzzle with two discs, the move to complete the puzzle with one disc must be made twice, plus an extra move (to move the large disc).
This principle is the same for larger numbers of discs. For the puzzle with n discs to by completed, the combination of moves that are used to complete the puzzle with n - 1 discs must be made to move all of the discs except the largest one onto the centre peg. Then a single move of the largest disc onto the right peg can be made. To complete the puzzle, the combination of moves to complete the puzzle with n - 1 discs must be made to move all of the discs from the centre peg onto the right peg. Therefore, the number of moves which it takes to complete the puzzle with n discs is twice the number of moves it takes to complete the puzzle with n - 1 discs plus 1. If the number of moves to complete the puzzle with n discs is written as mn then:
Or written the other way around:
Using this equation, the following must also be true:
This can be substituted into the original equation to give:
Multipltying out the brackets gives:
Again, using the original equation, the following must be true:
This can be substituted into the equation above, and after multiplying gives:
These substitutions can be continued. It can be seen that this is a sum of successive powers1 of 2. Therefore this equation can be rewritten as:
The substitutions can be continued until the term m1 is reached. Since the coefficient2 of the term mn - a can be seen to be 2a, the coefficient of the term m1 (which is the same as mn - (n - 1) ) must be 2n - 1. Therefore, after further expansions the following equation can be written:
m1 is known to be 1 (since it takes one move to complete the puzzle with one disc). Therefore:
This equation says that mn is equal to a sum of consecutive powers of two, from the power 20 to the power 2n - 1. This summation can be proved3 to be equal to 2n - 1. Therefore, the solution is:
Therefore the fewest number of moves in which the puzzle with n discs can be completed is 2n - 1 moves.
12 to the power of n means 1 times 2 n times. For example, 2 to the power 4 equals 1 x 2 x 2 x 2 x 2 and is written as 2 ^ 4 or 24.2Multiple of. The coefficient of 8mn - 3 is 8.3Proof by induction can be used to prove this.
