Tower of Hanoi Problem (TOH) - Data Structure

Tower of Hanoi Problem (TOH) - Data Structure, Tower of Hanoi Problem (TOH) - Data Structure, Tower of Hanoi Problem (TOH) - Data Structure

TOH ( Tower of Hanoi) is a mathematical game or puzzle. It consist 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 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.

for example, 
Tower of Hanoi Problem (TOH)

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 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 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" */  
}

You May Also Like...