Tower of Hanoi

The Tower of Hanoi (also known as the Tower of Brahma) is a mathematical game or puzzle invented by E. Lucas in 1883.  The Tower of  Hanoi games consists of pegs arranged in a stand, and 8 circular discs of wood or cardboard each of which has a hole in the middle, so that pegs can be easily put through it. 

The discs placed on the pegs are of different sizes, and initially, all the discs are placed on one peg so that the biggest disc is at the bottom, and the smallest disc is at the top. This arrangement of discs in the Tower of Hanoi game is known as a tower.

Tower of Hanoi Problem

There are 3 pegs in the Tower of Hanoi problem and a disc of different size. Each disc has a hole in the middle so that any peg can be easily fit. At the beginning of the Tower of Hanoi game, all n discs are on the first peg, arranged such that the largest disc is at the top, and the smallest disc is at the bottom. 

The goal of the Tower of Hanoi game is to move all the discs on the third peg, in a similar order, that is the smallest disc on the top, and in an increasing order towards the bottom. 

But, there are some restrictions to how the discs are moved (which makes the Tower of Hanoi problem non-trivial).

• The only type of move that is allowed is to grab one disc from the top of one peg and drop it into another peg. That implies that you cannot drop several pegs at one time.

• The larger disc cannot lie above a smaller disc.

Tower of Hanoi Solution

The Tower of Hanoi game can be played with any number of discs, although many toy versions have around 7 to 9 discs. The minimum number of moves needed to solve a puzzle is 2ⁿ - 1, where n is the total number of discs. With the Tower of Hanoi 4 discs, the Tower of Hanoi puzzle can be solved with 15 moves (2⁴ - 1 = 15).

Tower of Hanoi Algorithm

To understand the Tower of Hanoi algorithm, we will first learn how to solve the Tower of Hanoi problem with a smaller number of discs, say 1 or 2, we will mark the three rods with source, destination, and auxiliary.

But if we have 2 discs,

First, we will move the smaller (top) disc from the peg source to the peg auxiliary.

Then we will move the larger (bottom) disc from the peg source to the peg destination.

Finally, we will move the smaller disc (top) from the peg auxiliary to the peg destination.

With this, we can easily design an algorithm for the Tower of Hanoi algorithm with more than two disks. We will divide the stack of disks into two different parts.

• The larger (nth) disc in one part

• And, all other (n-1) disks in the second part.

Our goal is to move disk n from peg source to peg destination and then place all other (n - 1) disks above it. Following are the steps to move 2 discs.

Step 1 − Move (n -1) disks from peg source to peg auxiliary.

Step 2 − Move larger (nth) disk from peg source to peg destination.

Step 3 − Move n -1 disks from the peg auxiliary to the peg destination.

Tower of Hanoi Recursion

Here, we will learn to solve the Tower of Hanoi puzzle using the Tower of Hanoi recursion method with an algorithm.

Let's take an example of the Tower of Hanoi with 2 discs:

In the diagram below, disc 1 is placed on top of disc 2 in peg 1. The aim is to move both the disc in the peg B recursively.

Here are the steps to move both the disc to peg B recursively

Here are the steps to move both the disc to peg B recursively.

1. The first step is to move Disc 1 from peg A to peg C.

2. The second step is to move Disc 2 from peg A to peg B

3. At last, move Disc 1 from peg C to peg B.

This Tower of Hanoi solutions with 2 discs takes 3 steps.

Tower of Hanoi Recursion Algorithm can be driven as follows:

START

Procedure Hanoi(disk, A, B, C)

 If Disk = 1, Then,

Move Disk from peg A to peg B            

ELSE

Hanoi(disk - 1, A, C, B)       Step 1

Move disk from peg A to peg B           Step 2

Hanoi(disk - 1, C, B, A)      Step 3

END IF

END Procedure

STOP

Example of Tower of Hanoi With Solution

1. How Do You Solve the Tower of Hanoi With 3 Discs?

Solution:

With 3 discs, the Tower of Hanoi problem can be solved in 7 steps. The minimum number of moves required to solve a Tower of Hanoi puzzles  is 2ⁿ - 1, where n is the total number of discs

If we have 3 discs - 1, 2, and 3 discs stacked in peg A, then the following are the steps to solve the Tower of Hanoi problem recursively with 3 discs.

Let, 

Disc 1 = Red Color

Disc 2 = White Color

Disc 3 = Green Color

1. The first step is to move Disc 1 from peg A to peg C

2. The second step is to move Disc 2 from peg A to peg B.

3. The third step is to move Disc 1 from peg C to peg B

4. The fourth step is to move Disc 3 from peg A to peg C

5. The fifth step is to move Disc 1 from peg B to peg A

6. The sixth step is to move Disc 2 from peg B to peg C

7. The seventh step is to move Disc 1 from peg A to peg C

2. How Do You Solve the Tower of Hanoi With 4 Discs?

Solution:

With 4 discs, the Tower of Hanoi problem can be solved in 15 steps. The minimum number of moves required to solve a Tower of Hanoi puzzles is 2ⁿ - 1, where n is the total number of discs

If we have 4 discs - 1, 2, 3, and 4 discs stacked in Rod A, then the following are the steps to solve the Tower of Hanoi problem from source Rod A to a destination Rod C recursively with 4 discs.

Rod A: [1,2,3,4]  Rod B: [ ] Rod C: [ ]

Steps:

Step 1: Move Disk 1 from Rod A to Rod B

Rod A:  [4, 3, 2]  Rod B: [1] Rod C: [ ]

Step 2: Move disk 2 from Rod A to Rod C

Rod A: [4, 3]  Rod B: [1]  Rod C: [2]

Step 3:  Move disk 1 from Rod B to Rod C

Rod A: [4, 3] Rod B: [ ] Rod C: [2, 1]

Step 4: Move disk 3 from Rod A to Rod B

Rod A: [4] Rod B: [3] Rod C: [2, 1]

Step 5: Move disk 1 from RodC to Rod A

Rod A: [4, 1] Rod B: [3] Rod C: [2]

Step 6: Move disk 2 from RodC to Rod B

Rod A: [4, 1] Rod B: [3, 2] Rod C: [ ]

Step 7: Move disk 1 from Rod A to Peg B

Rod A: [4] Rod B: [3, 2, 1] Rod C: [ ]

Step 8: Move disk 4 from Rod A to Rod C

Rod A: [ ] Rod B: [3, 2, 1] Rod C: [4]

Step 9: Move disk 1 from Rod B to Rod C

Rod A: [ ] Rod B: [3, 2] Rod C: [4, 1]

Step 10: Move disk 2 from Rod B to Rod A

Rod A: [2] Rod B: [3] Rod C: [4, 1]

Step 11: Move disk 1 from RodC to Rod A

Rod A: [2, 1] Rod B: [3] Rod C: [4]

Step 12: Move disk 3 from Rod B to Rod C

Rod A: [2, 1] Rod B: [ ] Rod C: [4, 3]

Step 13: Move disk 1 from Rod A to Rod B

Rod A: [2] Rod B: [1] Rod C: [4, 3]

Step 14: Move disk 2 from Rod A to Rod C

Rod A: [ ] Rod B: [1] Rod C: [4, 3, 2]

Step 15: Move disk 1 from Rod B to Rod C

Rod A: [ ] Rod B: [ ] Rod C: [4, 3, 2, 1]