Tower of hanoi algorithm

Tower of hanoi algorithm

1. 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 r and obeying the following minimum number of moves
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.

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

3. - Java Code:

5. The following image is an example of the Hanoi of Tower and it is applied in the
previous Java code