The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. (Wikipedia)

For n disks, total 2^n – 1 moves are required.

Introduced: 1883
Designer: Édouard Lucas
Genre: Puzzle (Wikipedia)






Tower of Hanoi Solution for 4 disks :

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) A disk can only be moved if it is the
uppermost disk on a stack. i.e. Each move
consists of taking the upper disk from
one of the stacks and placing it on top of another
3) No disk may be placed on top of a smaller disk.

There are many long running time when input more than 10. 2^n-1 is the total moves required for n inputs. O(2^n) is the complexity. With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

The tower of Hanoi (also called the tower of Brahma or the Lucas tower) was invented by a French mathematician Édouard Lucas in the 19th century. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests.

Quick sort is fastest sorting algorithm and Heapsort is slowest sorting algorithm. Where Tower of Hanoi takes O(2^n) which is exponential.

Make it easy to remember as call Toh with n,s,d,a within recursive function call Toh 1st time with n-1,s,a,d and call Toh 2nd time with n-1,a,d,s. Program executes and you get the result. No of stacks initialize in each iteration may cause to internal memory full occur. To overcome this situation, you must careful about input.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner