Understanding the Tower of Hanoi Puzzle and its Recursive Solution

Slide Note

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.

mcdonagh_k Follow

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

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 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)

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 = ???