Python Programming Project

Tower of Hanoi

3. Algorithm for Solving the Tower of Hanoi Problem

In this chapter we will be discussing how to solve the Tower of Hanoi problem. This problem aims at solving the Tower of Hanoi game in the least moves possible. In order to do this we need to recognise a pattern in the moves. While solving the Tower of Hanoi for a small number of disks is easy, it is harder to solve it when there are more disks. Try solving the Tower of Hanoi for 3, 4 and 5 disks. Do you see any pattern?

3.2. Naming conventions

There are 3 poles in this problem. The one from which a disk is taken will be referred to as the source and the one which it needs to go to will be called the destination. The third pole will be referred to as the auxiliary pole.

3.3. Solving the problem

The problem is recursive in nature and can be solved by considering smaller chunks of the entire solution. If there are n disks in a tower then the solution must move the first n-1 disks to the auxiliary position. However, in order for the solution to do this it must move the first n-2 disks to the destination and so on. For example for the solution with three disks the entire tower needs to go to the destination pole but this means that the first 2 disks must go to the auxiliary which means the first disk must go to the destination pole. So in the first step of the recursion the first disk is moved to the destination pole. In the second step the second disk is moved to the auxiliary pole and the first disk is moved on top of this. The last disk is then moved to the destination and the other two disks are moved onto the last disk. The diagram below illustrates this.

In the solution it may be useful to consider changing the definition of each pole for each recursive step. For example for an entire solution with n disks the destination will be the last pole because that is where they need to go. However, for the recursive step with n-1 disks the destination pole is the second as this is where it needs to go. This allows you to generalise the solution while only changing the order of the poles for each step. So if there is a method called solve(source, auxiliary, destination) for solving the entire problem then a subsequent method call for n-1 disks may be solve(source, destination, auxiliary) which effectively switches which position the destination and auxiliary poles are in.

3.4. The Optimal Solution

The optimal solution is the one carried out in the minimum number of moves. It can easily be seen that with one disk the optimal solution is one move and with two disks it requires three moves. With three disks the problem can be solved in seven moves. The moves are as follows –

1. Move the smallest disk to the destination

2. Move the second smallest disk to the auxiliary pole

3. Move the smallest disk to the to the auxiliary pole

4. Move the largest disk to the destination

5. Move the smallest disk to the source

6. Move the second largest disk to the destination

7. Move the smallest disk to the destination

Note that in all optimal solutions one moves are alternated between the smallest disk and another disk. The solution for this can be seen in the following diagrams.

Move 1 –

Move 2 –

Move 3 –

Move 4 –

Move 5 –

Move 6 –

Move 7 –

Recall that we said previously that the optimal number of moves for any game with n disks is 2n-1. This is an easy way to check whether your solution to find the solution finds an optimal solution or a non-optimal solution.