# Tower of Hanoi Puzzle | Example, Number of Moves

The problem of tower of Hanoi was brought in 1883 by M.Claus (Lucas). It consists of disks and three pegs.

It is one of the vary popular example in data structure.

Tower of Hanoi Puzzle:

All the disks have different diameters and holes in the middle.

They are placed over one another in such an order that the disk with the largest diameter is placed on the bottom and the disk with smaller is placed above and so on.

The disk with the smallest diameter is placed at the top.

#### Example

Let us discuss the problem by considering three disks.

Initially, all the disks are placed over one another on the peg A. Our objective is to shift all the disks from peg A to peg C using intermediate peg B.

There are some rules to solve this problem.

1. Only one disk can be shifted at a time.
2. A disk can be shifting from any peg to any other.
3. Only top disk on any peg may be shifted to any other peg.
4.  No larger disks can be placed on a smaller disk.

Here is how you can solve the Tower of Hanoi problem for three disk.

In case of three disks you can find the solution manually but for a larger number of disks like four or more than four then the situation becomes quite complex.

The problem has a recursive nature which leads to a straight forward recursive solution.

Assume there are N disks, if N=1, then you simply shift the disk from peg A to peg C.

When N>1, then you can divide the original problem into three subproblems and solve them sequentially as follows.

1. Move the first(N-1) disks from peg A to peg B using intermediate peg C.
2. Move disk N (largest) from peg A to peg C using intermediate peg B
3. Move (N-1) disks from peg B to peg C using the intermediate peg A.

#### Algorithm

We can solve this problem by using recursion.

Algorithm to solve Tower of Hanoi puzzle using recursion:

MOVE(N, SRC, INT, DEST)- This algorithm shifts (N>0) number of disks from source peg (SRC) to destination peg (DEST) using the intermediate peg (INT).

```1. If (N=1) then  //shifting a single disk
Write "shift single disk from "SRC "to" DEST

Else  //shifting N-1 disk recursively
a)      MOVE (N-1,SRC,DEST,INT)
b)      DEST<-SRC  //shift disk from SRC peg to DEST peg
c)       MOVE(N-1,INT,SRC,DEST)
//end of if structure

2. Return.```

#### Python Program

If you understand the algorithm it’s pretty easy to implement the Tower of Hanoi problem with recursion.

Prerequisite:

Program to solve Tower of Hanoi:

```def hanoi(disks, source, auxiliary, target):
if disks == 1:
print('Move disk 1 from peg {} to peg {}.'.format(source, target))
return

hanoi(disks - 1, source, target, auxiliary)
print('Move disk {} from peg {} to peg {}.'.format(disks, source, target))
hanoi(disks - 1, auxiliary, source, target)

disks = int(input('Enter number of disks: '))
hanoi(disks, 'A', 'B', 'C')
```

Output

Case 1: when number of disk is 4

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

Case 2: when number of disk is 2

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

Case 3: when number of disk is 1

```Enter number of disks: 1
Move disk 1 from peg A to peg C.```

Try giving a different number of dicks as user input and check the output. This simple recursive solution works for any number of disks.

#### Minimum Number of Disk Move

Did you observe the number of minimum disks move required to solve the Tower of Hanoi problem?

Lets find it programmatic way.

```count = 0
def hanoi(disks, source, auxiliary, target):
global count
if disks == 1:
count = count + 1
return

hanoi(disks - 1, source, target, auxiliary)
count = count + 1
hanoi(disks - 1, auxiliary, source, target)

disks = int(input('Enter number of disks: '))
hanoi(disks, 'A', 'B', 'C')
print("Minimum number of disks move: ", count)
```

Output:

Case 1: when number of disks are 3

```Enter number of disks: 3
Minimum number of disks move: 7```

Case 2: when number of disks are 5

```Enter number of disks: 5
Minimum number of disks move: 31```

Look at the minimum number of disks (as an output) for a given number of disks.

If `n` is the number of the disks, then it requires `(2^n)-1` number of disk moves to solve the problem.

I hope you understand the Tower of Hanoi problem and how to solve it using recursion. If you have any questions, you can ask me in the comment. Keep learning!