Towers of Hanoi: A Complete Recursive Visualization

I mean honestly if this doesn't blow your mind do you even have a soul the towers of Hanoi problem is a classic recursive problem that can cause endless amounts of frustration when I first encountered this problem it took me several days to come up with the solution and quite honestly I didn't feel like I understood the solution until after teaching it to many of my former students years later the setup of the problem is as follows you have three rods one of the rods has some number of discs of varying sizes placed on it with the largest discs at the bottom and the smallest discs at the top your goal is to move these discs one at a time to a particular destination rod in the same configuration as a start before you get ahead of yourself and declare this problem trivial there is one important catch at any point in the process of moving this you are not allowed to move a larger disk on top of a smaller disk this rule is what makes this problem significantly more challenging to solve in this video we will dive into the towers of Hanoi problem in three distinct phases first we'll approach it from the perspective of a puzzle where we'll try to come up with a strategy for various configurations then we'll transfer the strategy into a recursive program to solve this problem for any number of disks in this section I'll also show you some helpful tricks to solve challenging recursive problems like this one and lastly we'll deconstruct the recursion to understand what's really going on underneath the hood with some nifty animations that I'm pretty sure you won't want to miss so make sure you stick to the end of the video all right let's get started let's focus first on three this since the solutions to the one disc and to discern two interesting for analysis purposes I highly recommend pausing the video and taking a second on your own to see if you can find the set of moves to get these three disks to the rightmost rod our goal is to come up with a general strategy for solving this problem if you're like me your first go-to strategy and any type of puzzle is random guessing and honestly there's no shame in that random guessing is the oldest strategy in the books so if I'm looking at this problem the first thing I might try is to move smallest disk to the middle rod and then the next move is basically forced from there I would move the green disc to the rightmost rod since I can't move it to the second rod because that would violate the rules after that the next move that makes the most sense is to try and move the smallest disk to the rightmost rod and at this point after I finished completely destroying the order of this problem with three random moves I think it might be a good idea to evaluate what I've done so far well unfortunately it's not looking too good it looks like we are a little bit stuck because what we really want is the bottom disk below the disks that we currently have on the third rod what we just did by random guessing seems to be pretty counterproductive to that point so at this point in the problem I might decide okay I might just want to start over and reevaluate but from this random guessing experience we've learned one important fact we need to first think about moving the largest disk from the first rod to the destination rod and if we take this idea one step further before we can even think about doing that we're going to have to deal with the top two disks and we have to deal with them in a careful manner so we can eventually move the largest disk to the destination rod this means our only option is that we have to find some way to move the top two disks to the second rod okay so now that we split our problem into more reasonable subtasks let's solve them one by one to move the top two disks to rod two we first move the smallest this to Rod three after which we move the middle disc to rod two and finish up the subtasks by moving the smallest disk to rot two and now we are free to move the largest disk to Rod three all right so what's next well from here the solution is actually pretty clear we need to move the top two disks from the second rod to the third rod now and to achieve this we move the smallest disk from the second rod to the first draw to get another way we then move the middle disk from the second rod to third rod followed by the the final step of moving the smallest disk to the destination rod and there you go we've just solved towers of nine for three disks he was a quick recap of what we did we first found a way to move the top two disks a second rod allowing us to then move this largest disk to the destination rod and after this we finished off by moving the top two disks from the middle rod to the destination run okay so now let's go one step further and see if we can solve this for the N equals four case by utilizing a similar strategy to what we've just developed before I go through the steps to solve this take a second to pause the video and see if you can come up with the steps on your own applying the general strategy to this new problem we want to now move the top three disks from rod 1 to rod two how do we do this well one interesting thing about solving this problem is that it's basically like ignoring the largest disk even exists and solving a general three disk towers of Hanoi problem we're now our destination is the middle rod make sure you take a second to understand the mapping that we just did and looking at the simpler problem we know how to solve it now right we basically solved the version of it earlier to solve this sub problem we move the top two disks a third rod we achieve this by moving the top distance second rod the middle disk to the third rod and finished off by moving the top disk from the second rod to the third rod this now makes way for the largest disk moving into the desired position and now to finish off the sub problem we once again move the top two disks but this time from the third rod to the second rod this sub task breaks down into moving the top disk to the first rod followed by moving the second disk to the second rod and ending with moving the top disk from rod 1 to rod to notice the logic that we used here was essentially the same as what we did earlier and this is something that'll be immensely important going forward in a sense this is where the recursion of this problem really originates going back to the for this problem we now move the largest disk from the first rod to the destination rod and now following our earlier strategy we now move the top three disks from the second rod to the destination rod and the pattern once again shows up this is essentially the same three this problem we solved many times now we move the top two disks from the middle rod to the first rod and to do this we move the top disk for the second rod to the third rod we then move the second disk from rod number two to rod number one and we finish this sub task by moving the top disk to the first rod we then move the third disk from the second rod to the destination rod and our final sub task is to move the top two disks from rod 1 to rot 3 once again we know how to do this we move the first disc from rod 1 to rod to move the second disk to the destination rod and finish off the whole problem by moving our top disk to the destination rod and that's the sequence of steps for towers of Hanoi with for this I know that was a lot so let's do a quick overview of what we just did we first moved the top three disks from rod 1 to rod two this required a couple of intermediate steps where we first moved the top two disks from brought one to rod three next we move the third disk to the middle rod and then finish the sub task by moving the top two disks from the last rod to the middle rod we then move the largest disk to the destination rod and lastly we finished by moving the top three disks from the middle rod to the destination rod which had the same set of sub tasks we've encountered several times so now that we have a fairly good understanding of a strategy for this problem let's now dive into a formal problem statement we want to write a function Hanoi that takes three inputs and start and end and outputs a sequence of steps to move n disks from the start rod to the end rod here's a quick example of an input and output so that we understand how this problem statement works if we pass in N equals three start is equal to one and n is equal to three what that means is our start rod is in rod number one and we have three disks on that start rod our n rod is rod number three and that's where this need to reach for simplicity let's assume that the start and end will always be between one and three and that they will never be equal to each other let's also assume that n will always be a positive integer so we won't have to handle any weird edge cases for this particular input the sequence of steps that this function will output will look like the following we've already gone over how these steps are generated from my strategy but here's a quick overview of how the steps correspond to actual movements of disks the basic interpretation is that a pointing to B means that we're going to move the top disc from Brod a to rod B okay so how do we get started on solving this problem when I'm looking at any sort of challenging problem I try to find the easiest thing I can do to help me solve the problem personally I've noticed that there's definitely an intimidation factor in tough problems like this and knocking out something easy can help you get over that initial intimidation one of the easiest things we can do here is to find a helper function that simply prints a move in the appropriate format defining this function is fairly straightforward to do and looks like the following so now that we got that either way let's shift our focus over to the main task we need to find a way to programmatically generate a sequence of steps for n disks we've already seen many clues in our investigation that point to the fact that we'll have to solve this problem recursively but how in the world can we come up with something that works this is by no means an easy problem and before we get into that solution I want to take a quick aside to go over an incredibly important concept when solving recursive problems whenever you have faced with a challenging recursive problem there are three key steps that you should follow to make your life exponentially easier these three tips have helped me throughout my years of learning computer science and save me a lot of pain the first step when solving a general recursive function f of n is to design a solution that works for F called on the input one this is often referred to as your base case the second step is the one that's the hardest to accept but what we are going to do is we're going to just go out on a limb and assume that F called on the input n minus 1 will work the second step is often referred to as a recursive leap of faith once we've made this assumption we will then show how we can define F called on n in a working manner using the function calls to F on n minus 1 here is some intuition for why these 3 steps work think about solving this recursive problem F of n as trying to knock down n dominoes where you only get to knock down the first domino you want to show that the ant domina will eventually be knocked down how do you do this well you know that if you just have one Domino it's obviously going to work out because you can just knock it down this is an analogy to step one from here what you can do is just assume at some point the N minus 1 Domino will eventually fall this is the analogy to step 2 and now to guarantee the ant Domino will fall we have to put this download just close enough to the N minus 1 Domino so that when that domino falls the nth Domino what respectively fall this is the analogy to step 3 and once we do that all the dominoes fall I want to emphasize here that all three steps are equally necessary for this to work out if we don't get the base case right that means the first domino never falls if we don't make the assumption that F called on and minus 1 works that's similar to the situation where the N minus 1 Domino never actually falls in which case there's no way that the nth Domino is gonna fall and lastly if we don't properly define the relationship between F of N and F of n minus 1 that's basically like putting the nth Domino too far away from the N minus 1 Domino so in that case the n Domino also never falls it's by moving the Domino close enough to the N minus 1 Domino that the nth domino falls so let's now apply these three steps to solving towers of Noi starting with step one we want to show how we appropriately handle the base case for this problem when n is equal to one that's easy enough since if we only have one disk all we have to do is move that one disk from the start to the end in our problem statement this is equivalent to calling print move with the arguments start and end that takes care of step 1 now let's move to step 2 in the process of solving towers of Hanoi for any N what it means to assume the F of n minus 1 works is that we can just accept that any version of towers of Hanoi call an N minus 1 will work it's important to remember that this includes a variety of starting and ending positions and we're just going to assume that all of these subproblems work now with that assumption that any call to towers of Hanoi on n minus 1 works let's move to the third step where we need to show how we can solve and disk towers of Hanoi problems using the solutions to towers of Hanoi called on n minus 1 there's one minor issue though the first thing we need to take care of is we currently have a reference to the start and end rod but we somehow need to have a reference to the other rod in the process one quick and easy way to do this is by utilizing the rod numbers since the first second and third rods are labeled 1 2 & 3 respectively the other rod will always be 6 minus the sum of the start and end rods and now that we have the other rod we can now execute the first step of the strategy that we developed earlier we want to first move the top n minus one disks from the start to the other the neat thing about the framework that we've defined for solving this problem is that the first step is exactly equivalent to solving the following towers of Hanoi problem on n minus one disks by the second step of recursive problem solving we can assume this call works so we can use it as part of our solution this corresponds to the recursive call to annoy called on n minus 1 start and other once we've completed a step we can then proceed to moving the last disk from the start to the end this corresponds to a call to pray move with the arguments start and end and now the final step is to move the top n minus one disks from the middle rod to the destination rod this subproblem is essentially the same as solving Hanoi for n minus 1 disk but a start disk is the middle and the end disk is the last disk this means we can assume that the sub-problem works as per our framework and the corresponding recursive call is Hanoi with the arguments n minus 1 other and end and following these steps successfully solves towers of Hanoi for n disk and this does indeed end up being a valid recursive solution now before we move on I want you to take a second and look at the final logic and really take a moment to appreciate it I mean how crazy is it that such a seemingly tricky problem ends up having such a simple solution I remember when I first solved this problem my mind was absolutely blown away I mean honestly if this doesn't blow your mind do you even have a soul this is really an amazing example of the power and beauty of recursive problem solving and for completeness he is a fully developed solution to this problem in Python the nice thing about going through all this work is that the code basically writes itself now at this point some of you might be looking at the solution and think okay I understand how it works within the recursive leap of faith' framework but how does the actual recursion work fear not let's answer that question I think the best example to take a deep dive into is the one we started off with annoying with three disks where we want to move the three disks from the first rod to the third rod the first recursive call we'll call Hanoi on two disks with the start rod as Rod one and the end rod as rod two here's what that represents this recursive call forces us to go back into the function where we now get another recursive call to Hanoi this time on one disk where we want the single disk to move from one to three here's a visual example of what this call is trying to achieve and this recursive call will go back into the function where we actually hit up base case which then prints the move from rod 1 to rod 3 and this is a very first move in the towers of Hanoi problem visually what this represents is that all our recursive calls before had changed state because we now have officially made our first move after making a first move we have officially completed the recursive call to Hanoi on one disk which now means we have to complete the recursive call to Hanoi on two disks this means we now have to call print move on rods one to two which has the following effect this is the second move in this particular towers of our problem after completely in the second move we still have to finish computing the recursive call to Hanoi on two disks which now makes its final recursive call on a single disk from rod 3 to rod 2 which has the following visual representation this hits the base case once again where we now make the third move which is to move the disk from rod 3 to rod two here's the effect of that on the overall problem and this now completes our first original recursive call which was step one in our earlier strategy of moving the top two disks from the first rod to the second rod what's next is step two of that strategy where we move the last rod from rod one to the destination rod that's a simple print call which has the following effect that actually ends up being the fourth move in the sequence this now leads us to the final step which involves moving the top two disks from the second rod to the destination rod that kicks off the following recursive call this kicks off a similar sequence of events the second recursive call goes back into the function where we now make a recursive call with one disk moving from the second rod to the first rod this it's the base case where we now print this move which is where the fifth move in the sequence comes from here's the effect of that on the overall problem [Music] the sixth move then follows by now moving the disc from the middle rod to the destination rod here's the effect of that on the overall problem and finally the seventh and final step involves the final recursive call on one disk moving from the first rod to the third rod which once again hits the base case that actually prints out the last move [Music] and there you have it that's how the towers of paranoid recursion unravels it's really quite amazing how it all works out especially if it's your first time seeing it so I highly encourage working through some examples on your own to convince yourself that things do indeed work out as they are supposed to before I conclude this video here's a big-picture recap of how we went about solving towers of Hanoi we first took a step back didn't even think about the code recursion algorithms or anything and just trying to understand how we as someone trying to solve a puzzle might go about solving this problem this is something I really encourage doing when you encounter a tough problem don't be afraid to take a step back and take a look at things from a different perspective following this we developed a strategy and use a strategy to implement our occurr civ solution on the way here we learn about the recursive leap of faith and how it can help us simplify particularly challenging problems and lastly we took a step deeper into the problem to understand how this recursion works out [Music] thanks for watching me and as always I'd appreciate it if you hit the like button if you enjoyed it if you want to see more content like this be sure to hit the subscribe button and if you want to more directly support this channel be sure to check out the patreon page linked in the description below see you in the next video

Channel: Reducible

Views: 146,104

Rating: 4.9158487 out of 5

Keywords: Hanoi, Towers of Hanoi, Towers of Hanoi Visualized, Towers of Hanoi Recursion, Towers of Hanoi Explained, TOH, Recursive Problem Solving, Recursion, Towers of Hanoi Code

Id: rf6uf3jNjbo

Length: 21min 13sec (1273 seconds)

Published: Tue May 26 2020