Connect with us

Data Structure

What is the “Tower of Hanoi?”



Tower of Honai: The tower of Hanoi was invented by a French mathematician Édouard Lucas in the 19th century.

Tower of Honai. Image: HackerEarth

A Tower of Honai is simply a game problem. It is based on three pegs i.e source, middle and destination and a set of a disk of the different sizes.

Each disk has a hole in the centre so that it can be stacked on any of the pegs. Here we have to see how we can use recursion to produce a logical solution.

Recursion is a technique of defining anything in terms of itself. Recursion is mainly use in terms of game development.

if n=3;

Then, the number of steps=2^n-1



Here,n is the number of the disk. The main aim is the movement of the disk. So,the rules for the movement of the disk are:

1. Only one disc can be moved at a time.

2.Each disk must be stacked on any one of the pegs.

3.Transferring the disk from the source peg to the destination peg such that at any point of transformation no lager size disk is placed on the smaller one.

Algorithm for Tower of Hanoi:

  1. Move the top n-1 disk from source peg to middle peg.
  2. Move the bottom most peg nth disk of source peg to destination peg.
  3. Move n-1 disk stacked on middle peg to destination peg.

Application of Tower of Hanoi

  1. It is frequently used in the psychological research of problem-solving.
  2. It is used in the neuropsychological diagnosis and treatment of the executive functions.
  3. It is also used to teach the recursive algorithm for the beginners of the programming student.

Tower of Hanoi is common dynamic programming which is used in the various programming challenges.

Facebook Comments