Data Structure & Algorithms - Tower of Hanoi - Data Structure & Algorithms

What is Tower of Hanoi?

A mathematical puzzle consisting of three towers and more than one ring is known as Tower of Hanoi.

Tower of Hanoi

The rings are of different sizes and are stacked in ascending order, i.e., the smaller one sits over the larger one. In some of the puzzles, the number of rings may increase, but the count of the tower remains the same.

What are the rules to be followed by Tower of Hanoi?

The Tower of Hanoi puzzle is solved by moving all the disks to another tower by not violating the sequence of the arrangements.

The rules to be followed by the Tower of Hanoi are -

  • Only one disk can be moved among the towers at any given time.
  • Only the "top" disk can be removed.
  • No large disk can sit over a small disk.

Tower of Hanoi puzzle with n disks can be solved in minimum2n−1 steps. This presentation shows that a puzzle with 3 disks has taken23- 1 = 7 steps.

Algorithm

The algorithm is written by knowing how to solve the problem with few disks, say 1 or 2. Three towers are taken with the names, source, destination and aux (only to help moving the disks). If there is only one disk, then it can easily be moved from source to destination peg.

If there are 2 disks −

•First, move the smaller (top) disk to aux peg.

•Then, move the larger (bottom) disk to destination peg.

•And finally, move the smaller disk from aux to destination peg.

Now an algorithm can be designed for the Tower of Hanoi with more than two disks. The stack of disks is divided into two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

The goal is to move the disk n from the source to destinations and put all other (n1) disks onto it. The same are applied in a recursive way for all the set of disks.

The steps to follow are −

A recursive algorithm for Tower of Hanoi can be driven as follows −

To understand the implementation of Data Structure Tower of Hanoi in C programming, click here


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics