THE TOWERS OF HANOI
THE CYBERWAVE TUTORIAL 32
THE VOICE OF THE TUTOR |THE CYBERWAVE TUTORIAL 32-TOH 0778201864
FOREWORD- Im very excited to coach you through the
challenging concept of the towers of Hanoi. You may
remember this from one of those games we used to play
as kids (lol)
ENJOY!
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
2022 ZIMSEC COMPUTER SCIENCE PAPER 2
LETS GO BACK TO SOME BASICS
The tower of Hanoi is just a math puzzle which consists of 3 towers (pegs) . On these
towers there are rings inserted as in the question above. These rings are of different
sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger
one. There are other variations of the puzzle where the number of disks increase, but
the tower count remains the same.
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
INSTRUCTIONS/RULES OF THE GAME
The mission is to move all the disks to some another tower without violating the
sequence of arrangement. A few rules to be followed for Tower of Hanoi are −
Only one disk can be moved among the towers at any given time.
Only the top disk can be removed.
No large disk can sit over a small disk.
LETS TRY TO SOLVE A SIMPLE TOWER WITH 3 DISKS
SMALL USEFUL TIP
S
MEDIUM
In bubble sort AUX IS TEMP
LARGE
DESTINATION AUX
SOURCE
Consider the towers above. Please note that the puzzle can be solved with 2n -1 moves.
This means that the above example with 3 disks can be solve with 2 3-1 =7moves.
STEP 1- MOVE OFF THE SMALL DISK TO THE DEST TOWER
WHY?-we want to free the
largest disk
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
STEP 2 –MOVE THE MEDIUM DISK TO AUX
#REMEMBER
NEVER PUT A LARGE DISK ON A BIGGER ONE
STEP 3- MOVE THE SMALL DISK TO AUX SINCE ITS < MEDIUM
STEP 4- NOW MOVE THE LARGE DISK TO DESTINATION
STEP 5 – MOVE THE SMALL DISK BACK TO SOURCE
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
STEP 6-MOVE MEDIUM DISK TO DESTINATION
STEP 7 –FINALLY MOVE SMALL DISK TO DEST
CONGRATS
NOW THE ALGORITHIM!
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of disks, say → 1 or 2. We mark three towers with name,
source, destination and aux (only to help moving the disks). If we have only one disk,
then it can easily be moved from source to destination peg.
IF WE HAVE 2 DISKS
First, we move the smaller (top) disk to aux peg.
Then, we move the larger (bottom) disk to destination peg.
And finally, we move the smaller disk from aux to destination peg.
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
A SMART PERSON CAN ALREADY SEE WHATS GOING ON HERE
STEP 1- move the medium disk to aux peg.
STEP 2- we move the large disk to destination peg.
STEP 3-(DO IT YOURSELF LOL)
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
So now, we are in a position to design an algorithm for Tower of Hanoi with more than
two disks. We divide the stack of disks in two parts. The largest disk (n th disk) is in one
part and all other (n-1) disks are in the second part.
Our ultimate aim is to move disk n from source to destination and then put all other
(n-1) disks onto it. We can imagine to apply the same in a recursive way for all given
set of disks.
WHAT ARE THE KEY STEPS TO FOLLOW HERE
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest
THE ALGORITHIM RECURSIVE
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
GLORY BE TO GOD!!!
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
0716057680-THE CYBERWAVE
THE TOWERS OF HANOI | THE CYBERWAVE TUTORIAL 32
