@@princessassmunch4354 Man’s gotta make his bread. At this point, only 20 people support him on Patreon and he has tens of thousands of viewers who get such amazing content for free.
@@princessassmunch4354 That sounds like a lot tbh. A portion of my premium membership fee goes towards this channel, making it easier to support this channel and guarantee an ad-free experience. I'm sure he'll tone down the number of ads once he has a decent number of subscribers.
A few years ago, I solved the towers of hanoi with a loop. I assumed, that there are always three rods. And I said, that an empty rod is a very large disc. I only needed one input: the number of discs. I had realized quite another pattern, for which it is important, whether the number of discs is odd or even. The pattern is, that every other move is the move of the smallest disc. If the number of discs is odd, it always moves start -> end -> other -> start. If the number of discs is even, it always moves start -> other -> end -> start. The other move is always the smaller of the two discs on top of the bigger disc. This solution might might have a few memory issues, but it works.
I am think you are not stupid, just imagine you can read and write it takes a lot, and you can differentiate between squares and triangles a lot of monkey cant do it
Thank you for taking the time and effort to make this video. The quality of the editing and animations in the video are excellent and remind me of 3Blue1Brown's videos. Great explanation and it really helped me to visualise and understand how this problem works!
the effort you put into explaining these complex concepts is unimaginable. I have never seen this kind of presentation for explaining an algorithm. Keep it up please.
Great video for introducing the puzzle! One piece of critique though, When you talked about the "recursive leap of faith" (the induction hypothesis) you took n-1 to mean the second to last domino. This can be a bit confusing. I think it's more explanatory if you just said: Pick any domino, and assume it will fall over. If it falls over, prove the next domino (+1) will ALSO fall over. Thus, the first domino falls because of the base case. The second domino falls down, because the first one falls. The third falls, because the second falls because the first, etc etc. That explanation is better at showing how a proof by Induction kind of "cascades" like dominoes, proving every case. Otherwise, it can seem a bit like assuming something random, just to come up with a result.
This video is soooo great! It took me awhile, but after repeating your video for 5 times, I finally understand this completely and was able to even work out examples with 5+ discs on my own. Thank you so much!!!
Simply no words to praise this person! I often feel lazy for leaving comments on youtube videos, but this time I must. Kindly make a playlist for explaining the theory of all the data structures and algorithms.
I had solved this problem on my own before watching the video. Btw, in my personal case I found the iterative solution harder to come up with than the recursive one. Since I had already solved this problem before watching the video, what blew mi mind was the little arithmetic "hack" to find the "other" rod: 6 - (start + end) LOL. Great stuff!
What is the reason for other = 6 - (start + end). There are 10 disks on the example? 14:02. If the first, second and third rod was labeled 1,2 and 3. Then the other rod is 6- (start+end). Is there a 4th rod? Edit: After som afterthought I think you possibly referring to the sum of tower numbers 1+2+3 = 6, but this wasn't explained deeply enough to be satisfying. So essentially this is a method of finding the auxiliary rod at any given time in the recursion.
We always have 3 rods: 1, 2 and 3. When start is 1, end is 2, then other is 6-(1+2) = 3. When start is 1, end is 3, then other is 6-(1+3) = 2. When start is 2, end is 3, then other is 6-(2+3) = 1, and so on. Thus, the formula makes sense.
@@quyenscc Thank you! Our teacher taught us by naming the rods 'from', 'to' and 'other' and passing them as string parameters 'A', 'B', 'C'. The lesson was on divide and conquer though, not recursion, maybe that's why.
Back in 1994, this was on of the first assignments in my "Algorithms and Analysis" course, the one and only course every single programmer needs to take. Then you learn some sorting algorithms, and bam, you 're a programmer. All the rest is just building more algorithms. Even learning programming languages are completely secondary. Most of the class got it wrong, but most had think on it for a few hours. And this was at a community college, so recursive algorithms are not that hard. Over the years, I've been surprised how easy they've become. It's the iterative, efficient approach that's harder!
Greatest video ever on towers of hanoi problem. Even though I have tried to understand this problem number of time I finally understood it here. Because I was trying to name the discs as well but now I realised it isn't necessary since we'll always be moving top disc on a certain rod. Absolutely amazing way of explaining!! Keep it up!!🎉
Thank you so much for this. No one has explained recursion as well as you did. I had a similar problem to this in one of my assignments: Find recursive function to solve a tower of hanoi for n discs if you want to move them from 1st peg to 3rd peg and you can only move discs to an adjacent peg. I was overwhelmed when I tried it on my own the first time but after watching your video I was able to figure out the solution for this modified version of the problem. Keep up the great work.
I have never been good in math, even simple math. I have an app called IMPULSE. One of the games is Tower of Hanoi. It started out relatively simple but I was taking so long to finish each level and was ending up at 2% of the number of moves and time used. So i searched out a video to help me understand how this game works. I never thought it was a mathematical problem. One of my issues is my ADHD & ASD brain. Trying to keep organized in my thinking is not easy. But now I hope to finish my next level in much fewer moves. I will never reach a faster time, but improving in fewer moves is now my biggest goal. Thank you for this video
Black magic I tell you! That was crazy how a simple rule can solve a seemingly complex problem. I would have spent hours trying to intuit some complex solution to this.
Thank you so much. I was using n,A,B,C initially which was bit difficult but after watching your video it make more sense now. i.e. n, source, temp, dest as n, A,B,C
Thank you so much for these awesome videos. I'm currently taking course MITx 6.00.1x over on edX and your videos are really helping me understand the concepts. Thank you again.
damn, this channel is so underrated. I came here after watching your 5 steps for solving recursive problems and I am blown away after seeing that whole thing took only 10 lines of code, that's amazing
Amazing!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I have been trying to solve this problem for a while now and I was so confused with other solutions on the internet (the code of the solutions) but yours is extremely intuitive and elegant. I am very new to recursion and you made this so understandable. THANKS! I hope you continue making such videos because you really really help the community!
This video just explained it in easy manner.. Using animations make things to understand easily...Carry on and keep on adding the videos of data structures and algorithms in your playlist ..😀 Eagerly waiting for next video !!! Happy Learning !!
Here's a small typo (speako) you might want to address. Thanks for such clear visualizations, you've been a great help. 15:05 "solving hanoi for n-1 disks where the start ROD is the middle and the end ROD is the last ROD"
Beautiful. You’re really talented at unraveling seemingly complex concepts very elegantly. After watching your videos, I can’t help but knowing the concepts matter-of-factly. And wonder to myself why I wasn’t able to get it earlier.
Thank you very much for this video. You have not only explained the problem easily but also introduced us to a framework to solve recursive problems. 👍
Excellent explanation. This recursive program definitely blew my mind when I first saw it two days ago. I hand-drew out the stack frames for a 3 disk problem. And even though it worked, I still couldn’t grasp HOW it was working-the abstract idea of n-1 recursively moving sequentially smaller stacks was the part the really got me. After watching this video a second time, it clicked. The crux of the program’s ability is in that assumption that n-1 will work. It’s pretty amazing stuff. Thank you!
The set of steps used for moving (n-1) tower of Hanoi from rod 1 to rod 2, if used in reverse order then the (n-1) tower of Hanoi returns to rod 1 from rod 2. In all cases all types of rings can be placed on the lowemost biggest ring as all other rings will be smaller than it and hence can be ignored while solving (n-1) tower of Hanoi. This thing was very beautiful 🤯🤯🤯
The thing is i subscribe to your channel in my first arrival to the channel after seeing this video I dont often do that to other channels Keep goodjob!
Wow, that's just magic. Thank you for the detailed, visualised and simplified explication. Thanks to you another man on earth understood this problem and by extension a bit about recursion xD. And you obtain a subscriber of course
More contents please! Would like to see some visual explaination on other problems in DSA. Maybe some hard problems on leetcode or google interview questions.
I was thinking about how to solve this before watching the video and I thought of a really nice and elegant way to think about it: You can easily move 2 elements from one side to the other by moving the top element out of the way, moving the bottom element to the destination and then putting the top one back on. This means that you can move two elements as if they were a single element as long as nothing smaller is below them. Since you can now move 2 elements as one you can effectively convert a 3 stack to a 2 stack by treating the top 2 elements as a single element. Now that the 3 stack can be moved as a 2 stack the above algorithm can be used to move it as if it were a one stack. This strategy can then be repeated indefinitely for any height of tower
Note: this can be implemented recursively by making a move stack function that moves a spesified number of elements from the top of a stack to another rod that executes the move 2 strategy but when moving the top ring calls itself with one less specified element unless only one element is being moved in which case it directly moves the element.
1:48 gotta put n - 1 ordered disks to the second collum. But in order to put the n - 1 ordered disks to the second collum most efficiently you gotta put the n - 2 ordered disks to the third collum -> which means : 1 -> 3, 1 -> 2, 3 -> 2, then solve the last disk 1 -> 3, 2 -> 1, 2 -> 3, 1 -> 3.
That was a great explanation 👏 I'd like to add a different perspective. Suppose we have 5 disks and label our rods as 'A', 'B', and 'C'. It's important to recognize that the largest disk, disk number 5, will ultimately need to be placed at the bottom of the target rod. To achieve this, how can we remove the other 4 disks from rod 'A'? We can approach this by temporarily moving the top 4 disks (disks 1 to 4) from rod 'A' to rod 'B'. This relocation allows us to move disk 5 directly from rod 'A' to rod 'C'. Once disk 5 is placed, we then need to move the 4 disks from rod 'B' to rod 'C', starting with the smaller disks. This requires a recursive process, where each step involves moving fewer disks than the previous one until only one disk remains to be moved. Here is some Java code that illustrates this process more clearly: public class Main { public static void moveDisk(int n, char originalRod, char auxRod, char targetRod) { if (n == 1) { System.out.println("Move disk 1 from " + originalRod + " to " + targetRod); return; } moveDisk(n - 1, originalRod, targetRod, auxRod); System.out.println("Move disk " + n + " from " + originalRod + " to " + targetRod); moveDisk(n - 1, auxRod, originalRod, targetRod); } public static void main(String[] args) { int diskNumbers = 4; moveDisk(diskNumbers, 'A', 'B', 'C'); } }
Thank you so much Sir. It gives such satisfaction about understanding these concepts so clearly. Often I end up facing problems while solving recursion and backtracking problems. Please do make videos on those topics. 💓
if you only need to count the moves then you can assume any other tower than the starting one is the end and it simplifies to: function h(n) { if (n == 1) { return 1; } else { return 2*h(n-1)+1; }; the 2*h(n-1)+1 comes from the recursive part - move n-1 to intermediate peg, move the largest to the destination, move n-1 on top of it
Its very weird too. If there's an odd number of discs the top disc moves left one (which would go to 3) and the 2nd disc goes to the right, and than the top disc goes left again. After this you simply move the smallest disc other than 1 and 2 to another space with a greater disc number (in this case 0 discs on a rod would be equivalent to the largest disc). This solves the puzzle with any odd number discs, and if you flip the order it solves for every even number. Theres some relationship between the number of rods and the number of times you move the top disc and the second disc, as three rods requires cycles of 3 moves of the top two to work, but cycles of 4 when there's 4 rods. Very strange.
When I was learning principles of programming, this was of course one of the assignments. The course I was doing taught it by directing us to the answer. The way they did it was to break the problem into smaller steps, explain each step without giving the answer and providing tests to see if our attempt were correct after each step. So for this problem they did this and I was getting the steps right after some thinking. And when I got to the very end, I had every piece working, and I just had to put everything together. I did it and it worked. I solved a giant hanoi tower... And the craziest thing was: I still don't understand how lol
I just love so much how simple the solution is: def hanoi(n, start, end): if n==1: print(f'{start} -> {end}') return hanoi(n-1, start, 6-start-end) print(f'{start} -> {end}') hanoi(n-1, 6-start-end, end) 3 lines are for the very simple base case and the other 3 lines are just so simple This is a problem that once gave me a hard time I feel as though this is one of the very few problems that are actually pretty hard to solve but you can easily understand the code
If you keep making videos like this, you'll become the best and most famous CS teacher on RUclips.
I agree. Never see someone like him. So passionate
The amount of ads on this video fucking disgusts me tho.
@@princessassmunch4354 Man’s gotta make his bread. At this point, only 20 people support him on Patreon and he has tens of thousands of viewers who get such amazing content for free.
@@lqv3223 He can't tone it down just
a little? I mean for God sakes man, fucking 6 ads on a 20 min video.
@@princessassmunch4354 That sounds like a lot tbh. A portion of my premium membership fee goes towards this channel, making it easier to support this channel and guarantee an ad-free experience. I'm sure he'll tone down the number of ads once he has a decent number of subscribers.
I am a simple person, I see recursion, I panic.
I can’t even belive that the video of this quality has so few views. Keep up the good work!
Now I realized that the steps for recursive problem solving is basically the same steps taken in induction proofs in mathematics.
That's why they're usually taught together in discrete math courses for computer science!
There is a generalized version of induction called "structural induction" which has uses in proving things about recursively defined objects
@@HuyTran-ny7mg yes I learnt that along with recursive functions in discrete math
I’m stunned 😮
Now I realized that I do not understand anything in either one or the other.😭
My jaw literally dropped when I saw that you had 32k subs, I was expecting over 500k!!! But now you're one sub closer!
Geez, SubCount Tripled in 1 month
A few years ago, I solved the towers of hanoi with a loop.
I assumed, that there are always three rods. And I said, that an empty rod is a very large disc.
I only needed one input: the number of discs. I had realized quite another pattern, for which it is important, whether the number of discs is odd or even.
The pattern is, that every other move is the move of the smallest disc. If the number of discs is odd, it always moves start -> end -> other -> start. If the number of discs is even, it always moves start -> other -> end -> start. The other move is always the smaller of the two discs on top of the bigger disc.
This solution might might have a few memory issues, but it works.
That is so interesting
that is how i solved it for my C lab problem. had to play it so many times to figure out that pattern
I feel so stupid.
I am
I am think you are not stupid, just imagine you can read and write it takes a lot, and you can differentiate between squares and triangles a lot of monkey cant do it
Thank you for taking the time and effort to make this video. The quality of the editing and animations in the video are excellent and remind me of 3Blue1Brown's videos. Great explanation and it really helped me to visualise and understand how this problem works!
Thanks for the awesome comment! Glad this content helped you with this problem!
Lol, I was thinking of 3blue1brown too.
@@Reducible was that intro a reference to his ted talk hahaha
the effort you put into explaining these complex concepts is unimaginable. I have never seen this kind of presentation for explaining an algorithm. Keep it up please.
I don't ever take the time to think of such hard problems. But your lessons gives me confidence. Thanks a lot!
The simplicity of the code is truly beautiful.
Great video for introducing the puzzle! One piece of critique though, When you talked about the "recursive leap of faith" (the induction hypothesis) you took n-1 to mean the second to last domino. This can be a bit confusing. I think it's more explanatory if you just said: Pick any domino, and assume it will fall over. If it falls over, prove the next domino (+1) will ALSO fall over. Thus, the first domino falls because of the base case. The second domino falls down, because the first one falls. The third falls, because the second falls because the first, etc etc. That explanation is better at showing how a proof by Induction kind of "cascades" like dominoes, proving every case. Otherwise, it can seem a bit like assuming something random, just to come up with a result.
Ah, that is a subtle and good point. Thanks for the feedback!
Yes that was a bit confusing
This video is soooo great! It took me awhile, but after repeating your video for 5 times, I finally understand this completely and was able to even work out examples with 5+ discs on my own. Thank you so much!!!
I was thinking about this problem a while back, today I got one of your videos recommended to me, and now I'm here! Astounding explanation!
Best explanation of TOH I've ever heard.
Mindblowing explanation and animation! That 'Dominos' concept :), I personally liked it!
Thank you, I had a lot of fun making that domino animation so glad you appreciated it!
Nobody could have explained it better..genius.The dominos concept is gold!
Simply no words to praise this person! I often feel lazy for leaving comments on youtube videos, but this time I must. Kindly make a playlist for explaining the theory of all the data structures and algorithms.
I had solved this problem on my own before watching the video. Btw, in my personal case I found the iterative solution harder to come up with than the recursive one. Since I had already solved this problem before watching the video, what blew mi mind was the little arithmetic "hack" to find the "other" rod: 6 - (start + end) LOL. Great stuff!
What is the reason for other = 6 - (start + end). There are 10 disks on the example? 14:02. If the first, second and third rod was labeled 1,2 and 3. Then the other rod is 6- (start+end). Is there a 4th rod? Edit: After som afterthought I think you possibly referring to the sum of tower numbers 1+2+3 = 6, but this wasn't explained deeply enough to be satisfying. So essentially this is a method of finding the auxiliary rod at any given time in the recursion.
Your comment helped here. Thanks mate 🤜🏼
We always have 3 rods: 1, 2 and 3. When start is 1, end is 2, then other is 6-(1+2) = 3. When start is 1, end is 3, then other is 6-(1+3) = 2. When start is 2, end is 3, then other is 6-(2+3) = 1, and so on. Thus, the formula makes sense.
It was quite clear I think
@@nikosrouskas2438 I think he though he had to add the number of disks in each rod
@@quyenscc Thank you! Our teacher taught us by naming the rods 'from', 'to' and 'other' and passing them as string parameters 'A', 'B', 'C'. The lesson was on divide and conquer though, not recursion, maybe that's why.
Back in 1994, this was on of the first assignments in my "Algorithms and Analysis" course, the one and only course every single programmer needs to take. Then you learn some sorting algorithms, and bam, you 're a programmer. All the rest is just building more algorithms. Even learning programming languages are completely secondary.
Most of the class got it wrong, but most had think on it for a few hours. And this was at a community college, so recursive algorithms are not that hard. Over the years, I've been surprised how easy they've become. It's the iterative, efficient approach that's harder!
Greatest video ever on towers of hanoi problem. Even though I have tried to understand this problem number of time I finally understood it here. Because I was trying to name the discs as well but now I realised it isn't necessary since we'll always be moving top disc on a certain rod. Absolutely amazing way of explaining!! Keep it up!!🎉
You are the 3blue1brown of computer science. Keep it up!
world's best video to show how tower of hanoi works recursively
Thank you so much for this. No one has explained recursion as well as you did. I had a similar problem to this in one of my assignments: Find recursive function to solve a tower of hanoi for n discs if you want to move them from 1st peg to 3rd peg and you can only move discs to an adjacent peg. I was overwhelmed when I tried it on my own the first time but after watching your video I was able to figure out the solution for this modified version of the problem. Keep up the great work.
I have never been good in math, even simple math. I have an app called IMPULSE. One of the games is Tower of Hanoi. It started out relatively simple but I was taking so long to finish each level and was ending up at 2% of the number of moves and time used.
So i searched out a video to help me understand how this game works.
I never thought it was a mathematical problem.
One of my issues is my ADHD & ASD brain.
Trying to keep organized in my thinking is not easy. But now I hope to finish my next level in much fewer moves. I will never reach a faster time, but improving in fewer moves is now my biggest goal.
Thank you for this video
Don't worry bro u can get more better ❤❤
Very detailed and simple explanation. Keep up the good work
It was my biggest challenge when I started my CS course. It's a wonderful presentation, what a great work!
Holy crap, that 3 step list gave me an "aha!" moment. Great video!
You amaze with awesome content. The explanation was some understandable, I can hardly forget it. Thanks.
This is the best explanation of tower of hanoi on RUclips.
So thanks a lot.
Black magic I tell you! That was crazy how a simple rule can solve a seemingly complex problem. I would have spent hours trying to intuit some complex solution to this.
Thank you so much. I was using n,A,B,C initially which was bit difficult but after watching your video it make more sense now.
i.e. n, source, temp, dest as n, A,B,C
Thank you so much for these awesome videos. I'm currently taking course MITx 6.00.1x over on edX and your videos are really helping me understand the concepts. Thank you again.
damn, this channel is so underrated. I came here after watching your 5 steps for solving recursive problems and I am blown away after seeing that whole thing took only 10 lines of code, that's amazing
This was so awesome man, i watched all of your videos and they are amazing. Big fan here!!!!!
Amazing!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I have been trying to solve this problem for a while now and I was so confused with other solutions on the internet (the code of the solutions) but yours is extremely intuitive and elegant. I am very new to recursion and you made this so understandable. THANKS! I hope you continue making such videos because you really really help the community!
Thank you so much! The animations are amazing to aid our understanding of this problem. :)
Thank you for the kind comment and I'm glad the animations were able to help with your understanding!
if there is oscar for teaching it should go to this video,great explaination.
The best explanation with the best visual animation. An extraordinary work.
Thank you very much and please keep doing it.
This is the video that explains the problem the best so far.
This video just explained it in easy manner..
Using animations make things to understand easily...Carry on and keep on adding the videos of data structures and algorithms in your playlist ..😀
Eagerly waiting for next video !!!
Happy Learning !!
best video ... literally background music .. soothes my mind
Video might be old but concept is like advance clear... 😊
Best explanation to leap of faith concept in recursion hands down (time trac: 11:00). Absolutely amazig. Subscribed
Underrated channel.
Bless you, man. The best explanation on RUclips.
Honestly great job dude
You have much respect from me
I havent seen anyone having such a great ability making something so complex , look so easy
Holy f*** the domino visual made it all click for me!
God bless for such a beautiful explanation and Saving me from the sleepless night of not understanding the solution 🙏
Here's a small typo (speako) you might want to address. Thanks for such clear visualizations, you've been a great help.
15:05 "solving hanoi for n-1 disks where the start ROD is the middle and the end ROD is the last ROD"
Thank you so much. This is by far the best explanation on youtube for this problem. Thoroughly understood the logic because of the amazing animation.
Beautiful. You’re really talented at unraveling seemingly complex concepts very elegantly. After watching your videos, I can’t help but knowing the concepts matter-of-factly. And wonder to myself why I wasn’t able to get it earlier.
criminally under-subbed
This is the best explanation I have come across till date!! and nothing can be better than this.. thank you
Thank you very much for this video. You have not only explained the problem easily but also introduced us to a framework to solve recursive problems. 👍
Thanks for the kind comment! Glad to hear that this content helped you!
Best explanation I have seen on RUclips, I appreciate your effort. Thanks for uploading this video :)
by the way i loved the background music . It really helps me focus on the concept
Great explanation and thanks to the ads I now have several passive income streams that will make me rich beyond my wildest dreams!
thank you so much man ❤️ please keep making videos like this 🙏the quality and simplicity you have is unmatched.
love it so much, you beat all those MIT lecturers
Your work brought a lot of insights into solving recursive tasks, thanks!
For added practice, try implementing this:
hanoi(n, start, aux, end)
It's a decent way to test your understanding of the problem.
Excellent explanation. This recursive program definitely blew my mind when I first saw it two days ago. I hand-drew out the stack frames for a 3 disk problem. And even though it worked, I still couldn’t grasp HOW it was working-the abstract idea of n-1 recursively moving sequentially smaller stacks was the part the really got me. After watching this video a second time, it clicked. The crux of the program’s ability is in that assumption that n-1 will work. It’s pretty amazing stuff. Thank you!
Sir can u pls explain me this.. struggling since 4 days..
How can I contact u..
Outstanding explanation..
The set of steps used for moving (n-1) tower of Hanoi from rod 1 to rod 2, if used in reverse order then the (n-1) tower of Hanoi returns to rod 1 from rod 2. In all cases all types of rings can be placed on the lowemost biggest ring as all other rings will be smaller than it and hence can be ignored while solving (n-1) tower of Hanoi. This thing was very beautiful 🤯🤯🤯
The thing is i subscribe to your channel in my first arrival to the channel after seeing this video
I dont often do that to other channels
Keep goodjob!
Great explanation, cleared the confusion to a great extent. Thanks
Such a beautifully visualised video that I was able to code it within minutes of seeing it. Thank you so much
Thanks so much! This video and your last video about recursion helped me understand the topic way better.
There was a smile on my face seeing the solution
🙂
Gives me 3b1b vibes and I like it.
What an insane work you did here. It's awesome. Thank you so much!
I got it now, thanks to your animation.
What a time to be alive 😃
Struggling CS student here. Really great video!
Wow, that's just magic.
Thank you for the detailed, visualised and simplified explication. Thanks to you another man on earth understood this problem and by extension a bit about recursion xD.
And you obtain a subscriber of course
More contents please! Would like to see some visual explaination on other problems in DSA. Maybe some hard problems on leetcode or google interview questions.
Great video. Only watched a couple of videos of tours but can tell your love for the subject.
I was thinking about how to solve this before watching the video and I thought of a really nice and elegant way to think about it:
You can easily move 2 elements from one side to the other by moving the top element out of the way, moving the bottom element to the destination and then putting the top one back on.
This means that you can move two elements as if they were a single element as long as nothing smaller is below them.
Since you can now move 2 elements as one you can effectively convert a 3 stack to a 2 stack by treating the top 2 elements as a single element.
Now that the 3 stack can be moved as a 2 stack the above algorithm can be used to move it as if it were a one stack.
This strategy can then be repeated indefinitely for any height of tower
Note: this can be implemented recursively by making a move stack function that moves a spesified number of elements from the top of a stack to another rod that executes the move 2 strategy but when moving the top ring calls itself with one less specified element unless only one element is being moved in which case it directly moves the element.
1:48 gotta put n - 1 ordered disks to the second collum.
But in order to put the n - 1 ordered disks to the second collum most efficiently you gotta put the n - 2 ordered disks
to the third collum -> which means : 1 -> 3, 1 -> 2, 3 -> 2, then solve the last disk 1 -> 3, 2 -> 1, 2 -> 3, 1 -> 3.
That was a great explanation 👏 I'd like to add a different perspective. Suppose we have 5 disks and label our rods as 'A', 'B', and 'C'. It's important to recognize that the largest disk, disk number 5, will ultimately need to be placed at the bottom of the target rod. To achieve this, how can we remove the other 4 disks from rod 'A'?
We can approach this by temporarily moving the top 4 disks (disks 1 to 4) from rod 'A' to rod 'B'. This relocation allows us to move disk 5 directly from rod 'A' to rod 'C'. Once disk 5 is placed, we then need to move the 4 disks from rod 'B' to rod 'C', starting with the smaller disks. This requires a recursive process, where each step involves moving fewer disks than the previous one until only one disk remains to be moved.
Here is some Java code that illustrates this process more clearly:
public class Main {
public static void moveDisk(int n, char originalRod, char auxRod, char targetRod) {
if (n == 1) {
System.out.println("Move disk 1 from " + originalRod + " to " + targetRod);
return;
}
moveDisk(n - 1, originalRod, targetRod, auxRod);
System.out.println("Move disk " + n + " from " + originalRod + " to " + targetRod);
moveDisk(n - 1, auxRod, originalRod, targetRod);
}
public static void main(String[] args) {
int diskNumbers = 4;
moveDisk(diskNumbers, 'A', 'B', 'C');
}
}
5:30 was the moment of epiphany for me, thanks.
Thank you so much Sir. It gives such satisfaction about understanding these concepts so clearly. Often I end up facing problems while solving recursion and backtracking problems. Please do make videos on those topics. 💓
if you only need to count the moves then you can assume any other tower than the starting one is the end and it simplifies to:
function h(n) {
if (n == 1) {
return 1;
} else {
return 2*h(n-1)+1;
};
the 2*h(n-1)+1 comes from the recursive part - move n-1 to intermediate peg, move the largest to the destination, move n-1 on top of it
This was a G.R.E.A.T explanation. Thank you so much!
it's a awesome video, explain this complicated problem easily. and help to solve other problems.
Wow, just the kind of visualization I wad looking for, for this problem. Thanks!
Glad it helped you out!
This one is Hanoi-ingly simple when you know how
He made it so simple. Thank you.
While looking at the steps for solving recursive problem , I remembered my "principle of mathematical induction" class back in school
Its very weird too. If there's an odd number of discs the top disc moves left one (which would go to 3) and the 2nd disc goes to the right, and than the top disc goes left again. After this you simply move the smallest disc other than 1 and 2 to another space with a greater disc number (in this case 0 discs on a rod would be equivalent to the largest disc). This solves the puzzle with any odd number discs, and if you flip the order it solves for every even number. Theres some relationship between the number of rods and the number of times you move the top disc and the second disc, as three rods requires cycles of 3 moves of the top two to work, but cycles of 4 when there's 4 rods. Very strange.
When I was learning principles of programming, this was of course one of the assignments. The course I was doing taught it by directing us to the answer. The way they did it was to break the problem into smaller steps, explain each step without giving the answer and providing tests to see if our attempt were correct after each step.
So for this problem they did this and I was getting the steps right after some thinking. And when I got to the very end, I had every piece working, and I just had to put everything together. I did it and it worked. I solved a giant hanoi tower... And the craziest thing was: I still don't understand how lol
Excellent explanation 🔥🔥🔥
Awesome ! Great Explanation
This is Awesome man! Subbed
Mind-blowing
Thanks a lot for the great explanation !
I just love so much how simple the solution is:
def hanoi(n, start, end):
if n==1:
print(f'{start} -> {end}')
return
hanoi(n-1, start, 6-start-end)
print(f'{start} -> {end}')
hanoi(n-1, 6-start-end, end)
3 lines are for the very simple base case and the other 3 lines are just so simple
This is a problem that once gave me a hard time
I feel as though this is one of the very few problems that are actually pretty hard to solve but you can easily understand the code
Great work. Thanks for such an amazing video.