Tower of Hanoi Algorithm

Tower of Hanoi is a mathematical puzzle where we have three towers and n disks. The objective of the puzzle is to move the entire stack to another tower, obeying the following simple rules: 

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

Approach

Take an example for 2 disks : Let tower 1 = ‘A’, tower 2 = ‘B’, tower 3 = ‘C’.

Step 1 : Shift first disk from ‘A’ to ‘B’.

Step 2 : Shift second disk from ‘A’ to ‘C’.

Step 3 : Shift first disk from ‘B’ to ‘C’.

The pattern here is : Shift ‘n-1’ disks from ‘A’ to ‘B’. Shift last disk from ‘A’ to ‘C’. Shift ‘n-1’ disks from ‘B’ to ‘C’.

Sample

Input  − 3

Output   − A to B 

              A to C 

             B to C 

            A to B 

            C to A 

            C to B 

A to B  Explanation − uses recursive function & solves the tower of Hanoi

Implementation of Hanoi Tower In C

#include <stdio.h>
 
void towers(int, char, char, char);
 
int main()
{
    int num;
 
    printf("Enter the number of disks : ");
    scanf("%d", &num);
    printf("The sequence of moves involved in the Tower of Hanoi are :\n");
    towers(num, 'A', 'C', 'B');
    return 0;
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {
        printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
        return;
    }
    towers(num - 1, frompeg, auxpeg, topeg);
        printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg);
    towers(num - 1, auxpeg, topeg, frompeg);
}

Output

Enter the number of disks : 3
The sequence of moves involved in the Tower of Hanoi are :
 
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C

Implementation of Hanoi Tower In Python

# Recursive Python function to solve tower of hanoi


def TowerOfHanoi(n, from_rod, to_rod, aux_rod):
	if n == 0:
		return
	TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)
	print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
	TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)


# Driver code
N = 3

# A, C, B are the name of rods
TowerOfHanoi(N, 'A', 'C', 'B')

# Contributed By Harshit Agrawal

Time complexity: O(2^N), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2^N
Auxiliary Space: O(N), Function call stack space

Important Notice

If you’re a college student and have skills in programming languages, Want to earn through blogging? Mail us at geekycomail@gmail.com

For more Programming related blogs Visit Us Geekycodes . Follow us on Instagram.