5/7/2023 0 Comments The hanoi towersWe need to move our largest disk to the destination tower. What we do now is no different than what we started out doing earlier. With the decks cleared, we move our third disk over to the destination:Īt this point, we have only have two disks in play. Our first disk currently stands in the way, but we can move that over to our temporary tower: This leaves our third and largest disk almost ready to be moved to the destination tower. Next, let's move our second disk over to the empty spot in our temporary tower: If you start off with an odd number of disks, your smallest disk will move to the destination tower first. For now, let's just say that if you start off with an even number of disks, your smallest disk will move to the temporary tower first. Wait, why is our smallest disk at our destination as opposed to our temporary tower? There is a technical reason for that. This means we first move our smallest disk out of the way: The first thing we are going to do is move our largest disk to the destination. ![]() We will start off with all of our disks at the starting point: With three disks, the training wheels come off and we really see what the monks who inspired this puzzle were going against. We are going to throw another disk into the mix! Three DisksĪll right. To really see the challenging-ness, we'll look at one more example in great detail. Now, with two disks we can see a little bit more about what makes this puzzle challenging. The final step is to move our smaller disk from the temporary tower to the destination as well:Īt this point, we've successfully shifted all of the disks from our starting point to the destination while respecting the various conditions. This means our next move is to shift that disk over there: Once we've made this move, our larger disk has a direct path to the destination. We do that by first shifting our top-most disk to our temporary, second tower: This means, the first thing we need to do is clear a path for our larger disk to reach its destination. We want to shift these disks over to our destination, the third tower, while maintaining the same stacking order AND ensuring that a smaller disk is always placed on top off a larger disk at every move along the day. ![]() The goal of what we are trying to do is still the same. This time, let's start of with two disks: To see what is really going on, we need more disks. With just a single disk, the puzzle isn't very challenging at all. We can move our single disk directly to the destination without doing anything extra. Because there are no other disks to worry about, we can win in just one single move: The easiest way to play the game is to use a single disk: To fix that, let's walk through a handful of examples and see how a typical game with these conditions is played. These conditions probably don't make a whole lot of sense. You can use any tower other than the one you started from as your destination, but we'll use Tower #3. Victory is achieved when all of the starting disks are arranged in their same starting order on a destination tower.You can only place a smaller disk on top of a larger disk.At each move, you take the disk from the top of any of the stacks and place it on another tower.This seems pretty straightforward, but there are a few conditions that make things frustratingly complex: At the end, the stack of disks are shifted over to the last pillar: You have a series of disks and three pillars:Īt the beginning, all of the disks are stacked on top of each other and start off in the first pillar. The objective of this puzzle is pretty simple. Besides being a really cool puzzle, it has a lot of practical (and historical!) significance as we learn about recursion.īefore we get to the programming side of things, let's first get a good idea of what the monks were trying to do. ![]() The Towers of Hanoi, Recursion, and the End of the Worldīy kirupa | filed under Data Structures and AlgorithmsĪs puzzles go, nobody really did it better than the monks who came up with the one we are going to learn about, the Towers of Hanoi.
0 Comments
Leave a Reply. |