When I think of the Tower Of Hanoi problem, I don't think about a series of moves made, but I think of a master plan on what I want to do, and then I divide that master plan into several sub plans that helps me achieve the goal I'm looking for. What I mean by this is if I look at the Tower Of Hanoi problem and I see the three stacks, I know my goal is to move the entire tower from stack zero to stack two. In doing that, I know the only way to move this big block is to first move the three blocks on top of it here to a spare stack, and then move the big final block to the target destination. I'm going to use that logic and actually draw out the two different pieces of my plan. So, here the first piece is to move the entire top part of the stack to stack one, and move that bottom element to stack two, and I need to do stack one first or step one first, and then I can do step two once I have the sub tower moved off from on top of the tower. There's a third step that eventually once I get the base moved over, I need to move over the sub tower from where it was in stack one to stack two. So, at each step, I'm going to take off everything but the bottom layer, move it to a spare spot, then move the bottom layer. So, what we know is we need to accomplish step one before we can do step two. We have to remove that entire sub tower that's on top of the bottom cube to our spare spot. Let's think about how we might plan that. To do that I can just ignore everything to do with step two, because we know we need to accomplish step one first, and we know that whatever is hidden down here is going to be larger than everything above it. So, we can without any concern put our smaller blocks on top of anything that might be underneath and hidden in this gray area. So, my job here is now to move a tower of height three over to this middle stack. Well, this looks like another version of the same problem. I need to take these two cubes and move it to my spare stack over here, so I can move this one cube over to my middle stack. That's exactly why my plan is here, and then as a third step, move it back together. So, let's again just plan on how we might do this first part of moving the stack of two. Ignoring everything in the bottom two layers now, we know everything those bottom two layers is larger than what we're seeing above, so we can look at this problem as only solving moving a stack of two things, while moving a stack of two things should be relatively simple. I move the top layer to the spare spot, I move the purple cube all the way to its intended destination, and for completion sake, why don't we even just, that bottom layer again? Here I just need to move one cube one space. This problem I know how to do, this is a simple move operation. So, since I know how to make this move operation, I can just do it, there's nothing on top, there's nothing constraining me. Now, I finally made my first movie. I did a whole bunch of planning, but at this point I've made my move, and now I can start unwinding our tower. So, remember our original plan was now to move the purple block to its intended target destination only once we remove what's on top of it. We've removed what's on top of it, we can make that movement, and the move made zero to two. The very last thing was that third step that we need to move our sub tower on top of our tower to make it the final destination, and that third step we can go ahead and accomplish by simply making a single move, something we know how to do, and now we have our third move. So, now we've accomplished the goal of moving this tower of two from its initial location to a location that is in a spot that we can start to move our next cube that we've hidden down here. Revealing the next layer, we now have the orange cube that we simply need to move over to the center stack. Because there's nothing on top of it, we can do a simple move, and here we now have the orange cube that's in the correct location. Remember the next step though is to go ahead and move this sub tower on top the orange cube so then we can move the blue cube from stack zero all the way over to stack two which we can't do right now because stack two is occupied. What this means is we can't just move this directly, this is series of two cubes, this is a tower in itself. But we can repeat this process again in saying that, "Okay, a tower of two cubes, everything down here is larger, we don't care about where it's located at, we just know it's larger, and we can divide that problem up, we can completely wind it, unroll it, reroll it, and we do this process recursively, and to many moves later, we finally get the final solution that we move the entire tower over just as we originally planned." So, I think this as extremely intuitive solution. The idea that we're going to slowly ignore part of the tower making only small moves that we know exactly how to do, and by following a pattern we can eventually get it there, we can eventually get a solution. But let's look at this more mathematically, let's analyze exactly what's being planned. So, instead of looking at the moves that we actually made, let's keep track of the moves we've actually plant. So, our plan is to move the source stack. So, I'm going to label a stack as a source and the target. The goal here is I want to move everything from the source to the target. To move a stack of four blocks from the source to target required three steps. The first step was to remove everything but the zeroth block for so blocks one, two and three, to the spare tile. So, we want to move this tower to spare tile, the second thing was to move that bottom block from the source to the target, and then the third step was we have all of these blocks here on the spare, and we need to move those spare blocks onto the target. The combination of these three steps makes it so that we can move the entire tower from the source to the target. Of course each of these steps themselves may require a number of sub-steps. Following the logic we described earlier, we can ignore that very bottom layer, and now just focus on this sub tower of three blocks. Notice that here in this sub tower three blocks, our target for these three blocks is different than the target for all four blocks. So, we wanted to put the three blocks into the middle stack so that the bottom tile can move to the first stack. So, what happens at each time we add a blinder on top of our stacks, we're swapping the target and the spare. Which stack we call the target, and which stack we call spare is entirely dependent on what round or what height we're on. We know that the process of converting the stack of three from a source to the target involves three different subsets. Moving this tower of two over this spare, moving this last element to target, and then moving this tower of two back on top of that target. We see these steps outlined here, and of course, those steps then require a tower of two to move, and the tower of two can move through three individual steps. This process goes on and on, and on, but we have a pattern to do it. This pattern repeats the exact same thing every time we go through these steps. What is that pattern? Well, if we look at the very first iteration of that pattern, the moves that we planned, we plan to move all the blocks so, zero to three to the target. In doing that, we need to move blocks one, two, three. So, everything from the start plus one to the spare, we need to move the starting location to the target, and then we need to move whatever we move from the source over to the target. So, we take out these numbers, and put in variables. We can say that the move to move a source from the start block to an end block, to the target requires going from this one past the start to the end. So, this is corresponding from moving from zero to three, we need to move from zero plus one or one to three, to the spare. Then, we need to move zero to the target, and then we need to move that one to three to the target. So, what we have is we have code that describes algorithm, that we intuited on how we might solve this problem. This is all we need to know, is we just simply need to plan a move from start to end, and each movement that does that is going to require three sub moves that's going to help us make that move. So, here's the game move function, and this function is going to take in a lot of parameters, because we're going to need a lot of information to run our algorithm. As we discussed, we need a start point and an end point. So, starting point initially will be zero, the ending point will initially be three, and as we move up and down the tower, those start and end points are going to change depending on how R sub calls are made. We also need to know what are three stacks are called. So, we're going to store a reference to our source, a reference to our target stack, and a reference to our spare stack. Then, I've included a sixth variable called depth. This is just going to keep track of how deep we are in the recursion, how many steps underneath the top step have we made. So, on line 50, we see out the planning a depth at a certain depth, incrementing depth along the way. So, we're planning a move at a certain depth, and the move is going to be equal to whatever move we're about to plan, we output a bunch of stuff that you're going to see on the console. On line 52, the one thing I do want to check before just going into our move pattern is to see if we're moving only one cube. We can see if we're only moving one cube by seeing if the start, and the end are the same. So, if we're moving one to one, that means we're only moving cube one, because our start and our end is the exact same value. So, for a starter under the exact same value, if that's the only cube in the range that we want to move, then we can just move the cube directly. So, move cube is simply going to move a cube from a source to the target. Then, we'll print out the state of the game. Otherwise, we want to follow our pattern we developed. Remember, the pattern we develop says start plus one to end, and we're going to move the source, we're going to swap target, and spare. So, notice we say source, target, spare here at the top, and the bottom we say source, spare, target, swapping the spare and the target, and we go ahead and send depth forward. Second step, so this correspond to step one, step two was we move from start to start, so we remove only these initial element. So, the element zero from source to target to spare. Then, our very last call, call three says we're going to take start plus one to end, and the source of this is actually a spare. So, remember, we put in line one, we put all of this cubes that were on our source onto the spare. So, in step three, we need take all the cubes in the spare, and move it to the target using the source, the original spot that these cubes came from as our new spare node. So, let see this program actually work, and explore how this program looks when it runs. Going into CPP tower solution two, going to run make, we run.slash main, and we see the program runs, and runs, and runs. But at the very end, we see the final game state is four, three, two, one. That's awesome. So, the initial game state here is four, three, two, one. Then, we see there's several planning moves. We plan to move zero through three from a stack in a certain memory address to another stack in another memory address. So, from stack seven, zero, to stack a, zero, using 88 as a spare. We go deeper, and we say we want to plan to move one to three from the source stack the 70 stack to the spare stack through 88. So, notice this swap back and forth, just as we expected. Then, two to three, and three to three. Here now at the planning depth of three, we're removing the element at height three to another element height three, we see that only here do we make our first move. We've planned four moves, and only then do we make our move moving this element that was on the zero stack to the middle stack. So, one is now in the middle stack. You can see this process goes on and on with lots of planning moves at certain points, moves when it gets down to the point where we have just a single element in its range, and then here at the final game state, we find that we do successfully move that through. I built this Tower of Hanoi solution to be pretty general. So, I hope you play around with it, and see how this program works together. You can add more cubes, and more stacks. As long as you make sure the program knows about exactly what you've added by making sure that you added it to the appropriate data structure, you can then run this program and see exactly how this works when you have more cubes, more stacks or any of the above. Play around with it, and then I'll see you in the next video.