Programming Data Structure Tower of Hanoi Puzzle | Implementation of Recursive Algorithm...

Tower of Hanoi Puzzle | Implementation of Recursive Algorithm | CS School

-

In a Tower of Hanoi puzzle, we have a collection of three pegs. And we also have some number of discs of descending size. All of these discs have hole in the middle, so that we can easily fit them into the peg. In principle we might have n number of discs for the puzzle.

So the Puzzle begins with all discs stacked up from biggest to smallest on one spindle, and the goal is to move entire tower from one spindle to another. Here the condition is we can move only one disc at a time, and also that we can not move bigger disc on top of smaller disc.

Algorithm Of Tower of Hanoi

In a simple Algorithm we can solve the puzzle, Tower of Hanoi. Say we have Two discs in spindle A. So for two discs our algorithm will as follows:

  • Move 1 disc from A to B using C.
  • Move the remaining 1 disc from A to C.
  • Move the Previous 1 disc from B to C using A.

For 3 Discs Algorithm of tower of Hanoi will be as follows:

  • Move 2 discs from A to B using C.
  • Move The last 1 disc from A to C
  • Move again the previous 2 discs from B to C using A.
Tower Of Hanoi Puzzle | Implementation Of Recursive Algorithm | CS School

Here we can see that the puzzle solving process is a recursive approach. Therefore for any number discs, our recursive algorithm will follow the same steps. So for n number of discs the algorithm will be like this:

  • Move (n-1) disk from A to B using C.
  • Move that remaining 1 disc from A to C.
  • Finally, Move (n-1) discs from B to C using A.

Algorithm Implementation of Tower of Hanoi

void TOH (int n, char A, char B, char C){
 //n is the number of discs, and A, B, C are three spindles
    if (n>0){
         TOH((n-1), A, C, B); // using C in the middle
         printf(“Move remainig 1 disc from %c to %c”, A, C);
         TOH((n-1), B, A, C); // using A in the middle
   }
}

Read more articles on Data Structure, here>>

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you