Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45
The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

The Hanoi Tower is a problem that E. Lucas brought to the western world in 1883. However, the origins of this game may be traced back to ancient Hindu civilization. It is linked with a Hindu temple tale in which someone allegedly employed the puzzle to improve the mental discipline of young priests. So, in this tutorial, you will explore the Tower of Hanoi problem and, ultimately, you will create a solution for it using the C programming language.

Understanding Tower of Hanoi Puzzle

The Tower of Hanoi is a mathematical problem composed of three towers and numerous rings arranged in increasing order of their diameters. The number of towers is constant for this problem, whereas the player can vary the number of rings he wants to use. The image given below depicts the setup of the TOH puzzle.

Tower_of_Hanoi_Setup

There are three towers in this diagram. And one of the towers is decked up with many discs, having the greatest diameter disc at the bottom and the smallest diameter disc at the top. This tower is known as the source tower. And the objective of this game is to move all rings present at the source tower to the destination tower without altering their sequence. 

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Before you get ahead of yourself and deem this problem trivial, there are few crucial aspects to consider. In this problem, you are allowed to move only one disc at a time. Furthermore, you are not enabled to place a larger disc on top of a smaller disc at any instance. That means the approach shown in the image below can never result in an accurate solution.

Order_Disturbance_Tower_of_Hanoi.

Moving forward, let’s look at all the rules involved in this TOH puzzle.

Rules of Tower of Hanoi Puzzle

The Tower of Hanoi problem is solved using the set of rules given below:

  • Only one disc can be moved at a time.
  • Only the top disc of one stack can be transferred to the top of another stack or an empty rod.
  • Larger discs cannot be stacked over smaller ones.

The complexity of this problem can be mapped by evaluating the number of possible moves. The least movements needed to solve the Tower of Hanoi problem with n discs are 2n-1.

Logical Approach to Implement Solution For TOH Problem

In this section, you will implement a logical solution to the four-ring TOH problem. The initial problem setup will be as represented in the image below.

4_Ring_Tower_of_Hanoi_Problem

In order to solve this problem, you are going to utilize an auxiliary or Helper tower. The first move you will make will be to transfer the orange ring to the helper tower.

Tower_of_Hanoi-Step_1

Next, you can move the green disc to the destination tower.

Step_2-Tower_of_Hanoi.

After that, you can move the orange disc to the destination tower. You will place this orange disc above the green disc.

Step_3-Tower_of_Hanoi

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Now, the helper tower is empty. So, you will take out the yellow ring from the source tower to the helper tower.

4_Ring_Tower_of_Hanoi_Problem

Next, you will move the orange ring to the source tower.

Step_5_TOH

Further, you will move the green ring to the helper tower.

Step_6_TOH.

Next, you will move the orange ring to the helper tower. This move will make room for the transfer of the largest disc to the destination tower. 

Step_7-Tower_of_Hanoi

Here, you can bring the largest disc to the destination tower. However, you still need to bring three more discs to our destination tower in order to solve this TOH problem.

Step_8_TOH

Here, you will move the orange ring to the destination tower.

Step_9_TOH

After that, you will move the green ring to the source tower. And you will also transfer the orange ring to the source tower. These two moves will allow you to transfer the second largest disc to the destination tower.

Move_10_and_11_TOH

Here, you will place the second ring at the destination tower. Now, you are only left with the arrangement of two more rings. 

Step_12_Tower_of_Hanoi

You will move the orange ring to the helper tower and the green ring to the destination tower.

Step_13_and_14_TOH.

Finally, you will move the orange disc to the destination tower.

Step_15_TOH

Full Stack Java Developer Course

In Partnership with HIRIST and HackerEarthEXPLORE COURSE
Full Stack Java Developer Course

Coding Implementation of TOH Solution

The TOH puzzle can be solved using a recursive programming paradigm. The C program for building a solution to the four-ring TOH problem is given below.

#include<stdio.h>

#include<conio.h>

void TOH(int n, char source, char destination, char helper_t){

    if(n==0){

        return 0;

    }

    TOH(n-1,source, helper_t,destination);

    printf("\n Move disc %d from tower %c to tower %c",n, source, destination);

    TOH(n-1, helper_t, destination,source);

}

int main()

{

    TOH(4, 'A','B','C');

    return 0;

}

Output:

The console representing 15 ring movements to reach the final solution.

TOH_Output

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Conclusion

In this Tower of Hanoi tutorial, you learned what the TOH problem is. After that, you discovered the logical approach to implement a solution for the TOH problem. Finally, you also looked at the programming implementation of the TOH solution using the C programming language. 

If you're looking for more in-depth training that goes beyond data structures and covers the foundations of interactive application development, Simplilearn's Software Development Courses will prove ideal for you. The courses in this catalog can help you improve your odds of becoming a software developer by aiding you in mastering the art of software development. So, go ahead and start exploring!

Have any questions about this article on the Tower of Hanoi problem? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.