Tower of hanoi
Problem :
The Towers of Hanoi is a classic puzzle with 3 pegs and multiple disks of different sizes.
The goal of the puzzle is to move all the disks from the first peg to the third peg according to the following rules :
- Only one disk can be moved at a time.
- You can only move the top disc in a stack.
- No disk may be placed on top of a smaller disk.
Logic:
- Move a tower of
height-1to thebuffer peg, using thedestination peg. - Move the remaining disk to the
destination peg. - Move the tower of
height-1from thebuffer pegto thedestination pegusing thesource peg.
To move
ndisks, the min number of required steps are2^n - 1. For example, to move 3 disks the min number of steps are(2^3 - 1) = 7.
Watch the following video to understand the mathametics behind it from MIT!
Solution :
Visualization :
References :
- To play the game use this URL - https://www.learneroo.com/modules/71/nodes/402