Let's look at one solution to the Tower of Hanoi problem. When I introduce a problem I randomly move cubes around with the goal being trying to move cubes to the right as much as possible. The first move I made, moved the yellow cube on top, down to the beginning of stack of one. I'm going to note the move here as zero move to one. The next thing I did was I moved the purple cube that was here to stack two, this is the move zero to two. The final thing I did was move the yellow cube from stack one to stack two, I'm going to denote this as one to two. After I've moved the small subset over to stack two, I started working on next cube, the orange cube. The orange cube could move from stack zero to stack one, and we begin moving everything else on top of the orange cube. The first thing that needs to be done is the yellow cube needs to move to stack zero, then the purple cube can move to stack one, and then the yellow cube can move on top of stack one from stack zero. Only now can we move the big cube from the first position all the way over to the position in stack two. This is our final position for that blue cube, so we're in good shape. Then, we can go ahead and move the yellow cube over with the idea that we want to move the purple cube out of the way. But at this point, we can start to see that we're seeing a pattern of moves. The first thing we're going to do is we're always going to move something in spot zero to spot one. Then, we're going to move anything in spot zero to spot two, and then from spot one to spot two. So, we see zero one, zero two, one two, zero one, zero two, one two, zero one, zero two, one two. The only difference is, we have an arrow at a certain place. So, let's go back to this fourth move. Here we just moved a cube from the orange cube, from stack zero, and moved it to stack one. So, zero to one. The next thing we're going to do is we're going to move stack zero to stack two. So, we know this is zero to two. But that's not what we did. We actually did two to zero. Because if in fact if we did zero to two, zero to two would have required us to move this blue cube and put it on top of the yellow cube. So, this is not a legal move. In fact here, we can't move zero to two, the only option we can do is to go from two to zero. What we're doing here is we found a strategy of repetitions inside the move order. Where our rule is we're always going to go zero one, zero two, one two, making the legal move at each case. So, what we expect is that for the next set of moves, we're going to go zero one, and the zero one is going to be in whatever direction results in legal move. Can we move anything for stack zero to stack one? We cannot. Can we move something from stack one to stack zero? We can. So, we know the arrow must run left. Next thing, we know that we need to go from zero to two. Looking at, can I move the purple cube to on top the yellow cube? The answer is no. Can I move the yellow cube on top of the purple cube? The answer is yes. So, we know that it's going to be two is placed on to zero. The very last thing we know one to two, here the orange cube, can we move one one to two? Yes. So, we know that arrow must go right. We can repeat this process but let's actually have a program complete this process, and see if we solve the game by using this pattern. In the games class solve function, I have a loop that's going to loop until the last stack has a size of four. While the last stack doesn't have a size of four, I went to continually follow our pattern. I want to make a legal move between stack zero and stack one. I want to make a legal move between stack zero and stack two, then I want to make a legal move between one and two. I don't actually have much intuition on why this works, and we'll look at a solution that's much more intuitive as our second solution. But we noticed this pattern, and we want to just test whether or not this patterns actually going to help us solve this problem. The last thing I need to do is I need to write a function that calculates whether or not a move is legal. So, if I need to do a movement between one and two, I can either go from one to two, or from two to one. In this case, I cannot put the orange on top the purple, so I have to put the purple on top of the orange. So, I know the only legal move here is to go from two and move it to one. I've define a new function inside of game.CPP called legal move. This legal move takes in two indices, these indices are the index of the stack that we want to look at. Let's look at the " if" statement. So, if the stack at index one.peek top, so if I look at the top cube, and I just take a peek at it, and then I get the length of that cube, so I'm going to look at the length of this cube, this cubes links might be three. If that cube is less than a cube that is at index two, so maybe this has a length of two, so if three is less than two, then I'm going to move index one to on top of index two. So, luckily the statement is false, three is not less than two. So, what that means I'm going move index two on top of index one, so I'm going to move index two's cube on genecs one's cube. So, here after this program runs, we expect a cube to sit on top of a cube. There's only one legal move. So, we're going to continually make these legal moves as much as we can, following the pattern zero one, zero two, one two. Our program is going to decide which of those two moves are legal, and continually run until we find, we've reached a solution. I'm took off one part at the beginning of legal move, and I wanted just to show you that code real quick. So, what we see here is before we even look at the legal moves, we want to do a little bit of analysis to make sure that we're including the fact that we may be able to peek on top of each stack. So, this point, we said we're going to peek on top of it, and see what the top cube is. The top cube doesn't exist, we're going to get an error because we can't look at a cube that doesn't exist. So, here on line 44, I check to see if the stack at index one is empty, and if it is, then I know the legal move has to be two to one. Otherwise, I'd check if this stack on index one is greater than zero, and the stack in index two is empty. If that's the case then the only legal move is one to two. Only if I find that both stacks are non-zero, do I go ahead and follow my logic earlier of looking at the top of both stacks and comparing. So, the entire function has the logic to check whether or not any of the stacks are empty, and if one of the stack are empty, we know that the other move has to be valid. If both stack is not empty, we can actually then compare the top cube. The very last thing you may have seen is we made use of a move function. This function removes the top cube, and places the top cube into the variable cube, and then the line 40 goes ahead and pushes that cube onto the stack index two. So, we are taking the cube off a stack of index one, and putting it on index two. And that move function is simply going to look at those two indices and do the move without any checks because we've already checked what order we need to move them into by how we're calling the move function earlier. So, let's see how this entire program works, and let's see if this program actually generates a solution. So, let's go over the console. Here in the console moving into CPP tower solution. I'm going to run make and running dot slash main, ./main to run our program. So, what we see is we see a whole bunch of output. We know we see a whole bunch of output because after every single move, you'll notice in the source code that we print out what the state of the game was. So, here the beginning, the initial game state was stack zero has four, three, two and one. The other stacks are empty. Then we go our movement zero to one. So, we moved the one that one on stack zero, two index one. Our second move out of our strategy is to go from zero to zero two, and then one two. We see this repeats itself again and again and again. In the final game state is amazing. We got the stack four, three, two, one that initially in stack of zero moved over to stack of two. So, one of the beautiful things about computer science is the fact that this is not the only correct answer. In fact this correct answer was something that only came to me as I was working through the problem. It didn't really intuitively come to me, and that's in this solution isn't the solution that it would approach first. I think this is a solution that's simplest to code. But in next video, I want to talk about the solution that I find more beautiful, and allows you to see another way to solve the exact same problem, and both solutions are going to get the right answer. So I'll see you there.