Tower of Hanoi
The Tower of Hanoi (also known as The Problem of Benares Temple, Tower of Brahma, Lucas’ Tower, or simply pyramid puzzle) is a mathematical game or puzzle made up of three rods and a number of discs of various sizes that can slide onto any rod.
An number of discs (made of wood) is stacked on one of the rods, which will determine the complexity of the solution;
The discs are placed on one rod in decreasing size order, with the smallest at the top, to approximate a conical shape. The goal of the puzzle is to get the full stack to another rod while following the instructions below:
- At any given time, only one disc can be transferred.
- Each move entails removing the top disc from one of the stacks and placing it on top of another stack or an empty rod.
- A larger disc cannot be placed on top of a smaller one.
Components:
- Three rods
- Set of discs with different sizes
Working Principle:
The Hanoi Tower is an excellent example of a Recursive problem.
Let’s see how to solve it.
n = 1
If we have just 1 disc that’s very easy as you just move it once and it’s over.
n = 2
If you have 2 discs, then you need to move the top one to rod 2, then the bottom one to rod 3 and only then move the small one from rod 2 to rod 3. That takes 3 moves in total.
n = 3
If you apply the same logic as before you’ll notice that for you to move the bottom disc to rod 2 you first have to move the other two to rod 3, move the 3rd disc to rod 2 and then move both the discs in rod 3 to rod 2 repeating the process for n= 2, meaning you had to move the 2 pieces twice repeating the exact same procedure.
The puzzle may be solved in 7 steps with 3 discs.
n = 4
Again by repeating the logic, you’ll find that for 4 pieces you have to repeat every step necessary for step 3 twice. This means that for every disc you add you have to double all the necessary steps.
The puzzle may be solved in 15 steps with 4 discs.
For n discs:
2n-1 is the smallest number of moves required to solve a Tower of Hanoi puzzle, with n being the total number of discs.
Instructions:
- Start with 5 discs in rod 1 correctly placed from the largest to the smallest so that the largest is at the bottom and the smallest at the top.
- Move one piece at a time to another rod making sure you never place a larger disc on top of a smaller one.
- Move all discs from rod 1 to rod 2.
- How many moves did you take?
- What’s the minimum number of moves necessary to solve the puzzle with 5 discs?
Links:
Towers of Hanoi (article) | Algorithms | Khan Academy