# How to implement Tower of Hanoi algorithm in Python

In this Python tutorial, we will learn what is Tower of Hanoi algorithm and how to solve Tower of Hanoi problem in Python. With words it not easy to understand the problem of Tower of Hanoi. Thus, we have put an animation (collected from Wikimedia Commons) to make it more clear to the learners.

## Tower of Hanoi in Python

**Definition of Tower of Hanoi Problem:**

Tower of Hanoi is a mathematical puzzle which consists of three towers or rods and also consists of n disks. The main aim of this puzzle is to move all the disks from one tower to another tower. In order to move the disks, some rules need to be followed. The rules are:-

- Only one disk can be moved at a time.
- The only small disk should have stayed at the top. That means no disk should be placed on top of a disk.
- A disk can be moved from one tower to another tower only if there is no disk on the top of the disk to be moved.

Tower of Hanoi algorithm can be solved in (2 pow n) – 1 steps. For example, if there are 3 disks, then the time to complete this algorithm takes (2 pow 3) -1 = 8 – 1 = 7 steps.

See this animation below to understand more clearly:

### Algorithm for Tower of Hanoi

Consider the three towers as the source, middle, destination. The algorithm for this problem as follows:-

- Move n-1 disks from source tower to middle tower.
- Then, move the nth disk from source tower to destination tower.
- Finally, move n-1 disks from the middle tower to the destination tower.

### Solve Tower of Hanoi Problem in Python

**Python Code:**

def tof(disks, source, middle, target): if disks == 1: print('Move disk 1 from tower {} to tower {}.'.format(source, target)) return tof(disks - 1, source, target, middle) print('Move disk {} from tower {} to tower {}.'.format(disks, source, target)) tof(disks - 1, middle, source, target) disks = int(input('Enter number of disks: ')) tof(disks, 'A', 'B', 'C')

Output:-

Case -1 :

Enter number of disks: 2 Move disk 1 from tower A to tower B. Move disk 2 from tower A to tower C. Move disk 1 from tower B to tower C.

Here the number of disks are 2, so this algorithm took (2 pow 2) – 1 = 4 – 1 = 3 steps.

Case -2 :

Enter number of disks: 3 Move disk 1 from tower A to tower C. Move disk 2 from tower A to tower B. Move disk 1 from tower C to tower B. Move disk 3 from tower A to tower C. Move disk 1 from tower B to tower A. Move disk 2 from tower B to tower C. Move disk 1 from tower A to tower C.

Here the number of disks are 2, so this algorithm took (2 pow 3) – 1 = 8 – 1 = 7 steps.

You can also read,

- How to implement Minimum Edit Distance in Python
- How to implement Longest Common Subsequence in Python

## Leave a Reply