Technology

Tower of Hanoi Problem (TOH) with Recursive Algorithm

TOH ( Tower of Hanoi) is a mathematical game or puzzle. It consists of 3 pegs A, B, and C. N Disks of different diameters are placed on peg A so that a larger disk is always below a smaller disk.

The aim is to move the N disks to peg C using peg B as an auxiliary. Only the top disk on any peg may be moved to any other peg and a larger disk may never rest on a smaller one.

A recursive algorithm for TOH,

  • To move n disks from peg A to peg C, using peg B as auxiliary.
  • If n==1, move the single disk from A to C
  • Stop.
  • Move the top n-1 disk from A to B, using C as an auxiliary.
  • Move the remaining disk from A to C.
  • Move the n-1 disks from B to C, using A as auxiliary.
  • Tower of Hanoi
transfer(n, from, aux)
{
if(n==1)
{
move disk n 'from ' to 'to'
}

transfer(n-1, from, aux, to)
move disk n 'from' to 'to'
transfer (n-1, aux, to, from)
}

To calculate the steps for a tower of Hanoi tracing follow below step,

If N = 2, steps 2^2-1 = 3

If N = 5, steps 2^5-1 = 31

N = 1,
transfer (1, from, to, aux {

/* from "A", to "C", aux "B" */

n==1 (true)
move disk 1 'from' to 'to'

/* from "A", to "C" */
}

Tuts

About Author

Tutsmaster.org provides tutorials related to tech and programmings. We are also setting up a community for the users and students.

You may also like

waterfall model
Technology

Advantages and Disadvantages of Waterfall Model

Waterfall Model is one of the major and crucial system development models which was developed for System development. This is
Cloud Computing
Technology

What is Cloud Computing? Benefits and Characteristics

Cloud computing is the on-demand availability of computer system resources, especially data storage and computing power, without direct active management