Scribd
Upload
71 views7 pages

Tower of Hanoi

The document summarizes the Tower of Hanoi puzzle. It consists of three rods and disks of different sizes that can slide onto any rod. The objective is to move the entire stack of disks, starting in descending order of size on one rod, to another rod following three rules: only one disk can move at a time, a disk can only be placed on a larger disk, and the minimum number of moves required is 2^n - 1, where n is the number of disks. An algorithm for solving the puzzle recursively is provided.

Uploaded by

senathipathik
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
71 views7 pages

Tower of Hanoi

The document summarizes the Tower of Hanoi puzzle. It consists of three rods and disks of different sizes that can slide onto any rod. The objective is to move the entire stack of disks, starting in descending order of size on one rod, to another rod following three rules: only one disk can move at a time, a disk can only be placed on a larger disk, and the minimum number of moves required is 2^n - 1, where n is the number of disks. An algorithm for solving the puzzle recursively is provided.

Uploaded by

senathipathik
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Created By

ANKIT S. CHITNAVIS
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.

The objective of the puzzle is to move the entire stack to another rod, obeying
the following rules:
1.Only one disk must be moved at a time.

2.Each move consists of taking the upper disk from one of the rods and
sliding it onto another rod, on top of the other disks that may already
be present on that rod.

3.No disk may be placed on top of a smaller disk.


The puzzle can be played with any number of disks.

 The minimum number of moves required to solve a Tower of Hanoi puzzle is

2n - 1
where n is the number of disks.
Solution for Tower of Hanoi :-
For an even number of disks:

make the legal move between pegs A and B


make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For an odd number of disks:

make the legal move between pegs A and C


make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete.
In each case, a total of 2ⁿ-1 moves are made.
Algorithm

Input :- Input of discs in Tower of Hanoi , specification of ORG as from the piller
and DES as to piller,INT as the intemediate piller.

Output :- Steps of moves of N discs from piller ORG to DCS piller.

Steps
1. if N>0 then
2. move(N-1 ,ORG ,DES ,INT)
3. ORG DES (move from ORG to DES)
4. move(N-1 ,INT ,ORG ,DES)
5. end if
6. stop
For N=3 , how will this recursion solve the problem as shown

Move(1,A,B,C) A C ( 1)

Move(2,A,C,B) A B A B (2)

Move(1,C,A,B) C B (3)
Move(3,A,B,C) A C A C (4)
Move(1,B,C,A)
B A (5)

Move(2,B,A,C) B C B C (6)

MoveE(1,A,B,C) A C (7)
Example :-
For 3 disk Move= - 1= 7
Thank You

You might also like