TOWER OF HANOI

IT259 Data Structures & Algorithms

Tower of Hanoi
 The problem is as follows:
- N discs of decreasing size stacked on one
needle & two empty needles are given.
- It is required to arrange all the discs onto a
second needle in decreasing order of size.
- The Third needle may be used as temporary
storage.
Rules for TOH
 The movement of the discs is restricted by the
following rules:
1. Only one disc may be moved at a time.
2. A disc may be moved from any needle to any
other.
3. At no time may a larger disc rest upon a smaller
disc.

1
1 1
2
2 2
3 3
Needle A Needle B Needle C
(start of problem) (intermediate) (completion of problem)
 Solution of the TOH problem (N=2)
Initial
position

Move-1

Move-2

Move-3
 TOH (N = 3)
1
2 1
3 2 3
A B C A B C
move-4

2
3 1 1 2 3
A B C A B C
move-1 move-5

2
3 2 1 1 3
A B C A B C
move-2 move-6
1
1 2
3 2 3
A B C A B C
move-3 move-7
Solution
 The solution of this problem is:
To move one disc, move it from AC.
To move two discs, move the first disc AB, move
the second from AC, then move the disc from BC.
 In general, the solution of the problem moving N
discs from A to C has three steps:
1. Move N – 1 discs from AB. (sourceinterm)
2. Move Nth disc from AC. (sourcedestination)
3. Move N – 1 discs from BC. (intermdest)
Problem of Tower of Hanoi
 This problem uses STACK as a data structure
for the solution. Because the problem is solved
using recursion.

1 1
2 2
3 3
Needle A Needle B Needle C
(start of problem) (intermediate) (completion of problem)
TOH Algorithm
S I D
 ToH(source, intermediate, destination, no.of disc)
S I D
 ToH (A, B, C, N)
if ( N==1 )
S D
Write (Move Disc N from AC);
else
{ S I D
ToH (A, C, B, N-1);
S D
Write (Move Disc N from AC);
S I D
ToH (B, A, C, N-1);
}
Algorithm
S I D
 ToH(source, intermediate, destination, no.of disc)

 ToH (S, I, D, N)
if ( N==1 )
Write (Move Disc N from SD);
else
{
ToH (S, D, I, N-1);
Write (Move Disc N from SD);
ToH (I, S, D, N-1);
}
 Solution of the TOH problem (N=2)
Initial 1
position 2
Needle A Needle B Needle C

Move-1 2 1
Needle A Needle B Needle C

Move-2 1 2
Needle A Needle B Needle C

1
Move-3 2
Needle A Needle B Needle C
Recursive solution of the TOH problem (N=2)
main( )
S I D S I D
TOH (A,B,C,2) TOH (A,C,B,1)
If(N==1) û If(N==1) ü
2 1
else Write (mv1,A"B) Needle A Needle B Needle C
TOH (A,C,B,1) else û move-1
Write (mv2,A"C)
TOH (B,A,C,1)
S I D
TOH (B,A,C,1)
If(N==1) ü
1
Write (mv1,B"C) 2
else û Needle B Needle C
move-3
1 2
Needle B Needle C
move-2
 N = 2 Initial Situation 1
2
Needle A Needle B Needle C

main( )
S I D S I D
TOH (A,B,C,2) TOH (A,C,B,1)
If(N==1) û If(N==1) ü
else Write (mv1,A"B)
else û 2 1
TOH (A,C,B,1) Needle A Needle B Needle C
Write (mv2,A"C) move-1
TOH (B,A,C,1)
S I D
TOH (B,A,C,1)
If(N==1) ü
Write (mv1,B"C) 1
1 2 2
Needle A Needle B Needle C else û Needle A Needle B Needle C
move-2 move-3
 N=3
1
2 1
3 2 3
A B C A B C
move-4

2
3 1 1 2 3
A B C A B C
move-1 move-5

2
3 2 1 1 3
A B C A B C
move-2 move-6
1
1 2
3 2 3
A B C A B C
move-3 move-7
 S I D S I D
N=3 TOH (A,C,B,2) TOH (A,B,C,1)
If(N==1) û If(N==1) ü
main( ) 2
else Write (mv1,A"C) 3 1

S I D TOH (A,B,C,1) else û A B C

move-1
TOH (A,B,C,3) Write (mv2,A"B) S I D
TOH (C,A,B,1) TOH (C,A,B,1)
If(N==1) û
If(N==1) ü
else
Write (mv1,C"B)
TOH (A,C,B,2) 1

Write (mv3,A"C) 3 2 1
else û A
3
B
2
C
A B C move-3
TOH (B,A,C,2) move-2
S I D S I D
TOH (B,A,C,2) TOH (B,C,A,1)
1 If(N==1) û If(N==1) ü
2 3
A B C else Write (mv1,B"A) 1 2 3
move-4 TOH (B,C,A,1) else û A B C
move-5
Write (mv2,B"C) S I D
TOH (A,B,C,1) TOH (A,B,C,1)
If(N==1) ü 1
2
2 Write (mv1,A"C) 3
1 3
A B C else û A B
move-7
C
move-6
Thank You