Understanding the Tower of Hanoi Puzzle and its Recursive Solution

undefined
 
Tower of Hanoi
 
 
Introduction
 
Tower of Hanoi is a very famous game.
In this game there are 3 pegs and N number of disks placed
one over the other in decreasing size. The objective of this
game is to move the disks one by one from the first peg to the
last peg. And there is only ONE condition, we can not place a
bigger disk on top of a smaller disk.
 
Notation followed
 
In order to solve we will use a general notation:
T(N, Beg, Aux, End)
T
      denotes our procedure
N
      denotes the number of disks
Beg  
 is the initial peg
Aux
   is the auxiliary peg
End
   is the final peg
 
Therefore for our example:
Objective is:
T(3,A,B,C)
 
Recursive Approach
 
Base Case:
T(1,Beg, Aux, End)   
: Move 
1
 disk from 
Beg
 to 
End
 peg.    
(Beg -> End)
 
For example:
T(1,A,B,C) 
: Move 1 disk from 
Beg
 (i.e. 
A
) to 
End
 (i.e. 
C
) peg.  
(A->C)
 
Try the solve Tower Hanoi Problem for
N=2
 
Solve for   
T(2,A,B,C) 
?
 
Steps to solve Tower of Hanoi Problem
for N=2
 
T(2,A,B,C)
 
{
 
   
T(1,A,C,B)         : Move a disk (A->B)
         T(1,A,B,C)         : Move a disk (A ->C)
 
   T(1,B,A,C)         : Move a disk (B->C)
 
}
 
Recursive Steps
 
 
T(N, Beg, Aux, End)
 
{
  
T(N-1, Beg, End, Aux)    
: Move top 
(N-1) disks 
from 
Beg
 to 
Aux
 peg.
  
T(1, Beg, Aux, End)
 
  : Move
 1 
disk from 
Beg
 to 
End
 peg.  
(Beg -> End)
  
T(N-1, Aux, Beg, End)    
: Move top 
(N-1) 
disks from 
Aux
 to 
End
 peg.
 
}
 
Result after 
T(N-1, Beg, End, Aux)                  T(1, Beg, Aux, End)                              T(N-1, Aux, Beg, End)
 
Solution for N=3:
 
 
T(3,A,B,C)
 
{
 
T(2,A,C,B) 
   
Move top 2 disks from A to B peg.
 
T(1,A,B,C)
   
Move 1 disk from A to C peg.     
(A->C)
 
T(2,B,A,C)
   
Move top 2 disks from B to C peg.
 
}
Result after: 
T(2,A,C,B)
                 
T(1,A,B,C)                              T(2,B,A,C)
 
Unfolding the recursion of Tower of
Hanoi for N=3       T(3,A,B,C)
 
Time Complexity
 
Calculate the number of Moves required for various values of N
 
For N=2,   Number of Moves = 3
For N=3,   Number of Moves = 7
For N=4,   Number of Moves = 15
For N=5,   Number of Moves =  ???
 
 
 
Time Complexity
 
In general for N disks, the number of moves needed = (2^N) – 1
 Hence time complexity is 
O(2^N)
 
References
 
https://www.dyclassroom.com/recursion-algorithm/tower-of-hanoi
Slide Note
Embed
Share

Tower of Hanoi is a classic game involving moving disks between three pegs, following specific rules. This article provides an introduction to the game, notations used, recursive approaches to solve it, and a detailed walkthrough for N=2 and N=3 scenarios. Explore the recursive steps, time complexity, and unfolding of the problem to grasp the strategy behind solving the Tower of Hanoi puzzle effectively.


Uploaded on Sep 07, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Tower of Hanoi

  2. Introduction Tower of Hanoi is a very famous game. In this game there are 3 pegs and N number of disks placed one over the other in decreasing size. The objective of this game is to move the disks one by one from the first peg to the last peg. And there is only ONE condition, we can not place a bigger disk on top of a smaller disk.

  3. Notation followed In order to solve we will use a general notation: T(N, Beg, Aux, End) T N Beg is the initial peg Aux is the auxiliary peg End is the final peg denotes our procedure denotes the number of disks Therefore for our example: Objective is: T(3,A,B,C)

  4. Recursive Approach Base Case: T(1,Beg, Aux, End) : Move 1 disk from Beg to End peg. (Beg -> End) For example: T(1,A,B,C) : Move 1 disk from Beg (i.e. A) to End (i.e. C) peg. (A->C)

  5. Try the solve Tower Hanoi Problem for N=2 Solve for T(2,A,B,C) ?

  6. Steps to solve Tower of Hanoi Problem for N=2 T(2,A,B,C) { T(1,A,C,B) : Move a disk (A->B) T(1,A,B,C) : Move a disk (A ->C) T(1,B,A,C) : Move a disk (B->C) }

  7. Recursive Steps T(N, Beg, Aux, End) { T(N-1, Beg, End, Aux) : Move top (N-1) disks from Beg to Aux peg. T(1, Beg, Aux, End) : Move 1 disk from Beg to End peg. (Beg -> End) T(N-1, Aux, Beg, End) : Move top (N-1) disks from Aux to End peg. } Result after T(N-1, Beg, End, Aux) T(1, Beg, Aux, End) T(N-1, Aux, Beg, End)

  8. Solution for N=3: T(3,A,B,C) { T(2,A,C,B) Move top 2 disks from A to B peg. T(1,A,B,C) Move 1 disk from A to C peg. (A->C) T(2,B,A,C) Move top 2 disks from B to C peg. } Result after: T(2,A,C,B) T(1,A,B,C) T(2,B,A,C)

  9. Unfolding the recursion of Tower of Hanoi for N=3 T(3,A,B,C)

  10. Time Complexity Calculate the number of Moves required for various values of N For N=2, Number of Moves = 3 For N=3, Number of Moves = 7 For N=4, Number of Moves = 15 For N=5, Number of Moves = ???

  11. Time Complexity In general for N disks, the number of moves needed = (2^N) 1 Hence time complexity is O(2^N)

  12. References https://www.dyclassroom.com/recursion-algorithm/tower-of-hanoi

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#