Scribd
Upload
164 views

Tower of Hanoi Algorithm

The document discusses the Tower of Hanoi algorithm. It explains that the Tower of Hanoi is a puzzle with three rods and disks of different sizes that can only be moved one at a time from one rod to another while following rules about disk size. It then explains how to solve the puzzle recursively by breaking it down into smaller subproblems until only one disk remains. Finally, it provides pseudocode and Java code to implement the recursive algorithm to solve the Tower of Hanoi puzzle.

Uploaded by

Weaam Raed
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
164 views

Tower of Hanoi Algorithm

The document discusses the Tower of Hanoi algorithm. It explains that the Tower of Hanoi is a puzzle with three rods and disks of different sizes that can only be moved one at a time from one rod to another while following rules about disk size. It then explains how to solve the puzzle recursively by breaking it down into smaller subproblems until only one disk remains. Finally, it provides pseudocode and Java code to implement the recursive algorithm to solve the Tower of Hanoi puzzle.

Uploaded by

Weaam Raed
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/ 5

Tower of Hanoi Algorithm

- What does Tower of Hanoi mean?


Tower of Hanoi is a mathematical puzzle where we have three rods
and n disks arranged in ascending order from top to bottom.
The objective of the puzzle is to move the entire stack from rod to
another with minimum number of moves r and obeying the following
simple rules:

 Only one disk can be moved at a time.


 Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.
 No disk may be placed on top of a smaller disk.

- Explanation of recursion definition in algorithm:

Using this link ( https://www.mathsisfun.com/games/towerofhanoi.html )

Let’s try to solve a puzzle – Tower of Hanoi using recursion.


Take an example with 2 disks  solution takes 3 steps.

What if we have 3 disks?  solution takes 7 steps.


 Recursively solve the problem of moving disk 1 and 2 from A to B as
example 1
 Move disk 3 from A to C
 Recursively solve the problem of moving disk 1and 2 from B to C

What if you have 4 disks?  solution takes 15 steps.


 Recursively solve the problem of moving disk 1,2, and 3 from A to B
 Move disk 4 from A to C
 Recursively solve the problem of moving disk 1,2 and 3 from B to C.
So, we find that for a given N of disks, the way to solve a problem in a minimum
number of steps is:

1. Move the top N−1 disks to an intermediate rod.


2. Move the bottom disk to the destination rod.
3. Finally, move the N−1 disks from the intermediate rod to the destination
rod.

Therefore, the recurrence relation for this puzzle would become:


H n = 2*H (n-1) +1

- Pseudocode:
Tower of Hanoi
Input: an integer n = number of disks, three chars {source,
inter, destination}.
Output: steps of solution (every move), number of moves.

START
Counter  0 \\num of moves
tower (n: disk, source, inter, destination)
IF n = 1, THEN
Counter  Counter + 1
Print “move disk from “ + source + “to ” + destination
ELSE
Counter  Counter + 1
tower (disk - 1, source, destination, inter)
Print “move disk from “+ source +”to “ + destination
tower (disk - 1, inter, source, destination)
END IF
END
Return (Counter)
- Java Code:
The following image is an example of the Hanoi of Tower and it is applied in the
previous Java code

You might also like