I am software developer (who also has a love for math) and it never once occurred to me that counting was a recursive action. I am continuously amazed at how elegant and simple your videos are and how effective they are at showing complex ideas in an approachable way. Thanks for all your hard work!
@@vairavanrenganathan4752 I don't want to put words in his mouth but I believe that he sort of means self-similar. By that, I mean that you can break it down into scaled down problems that are similar in procedure to solve.
You might be interested in the Church encoding of numbers in Lambda Calculus which is a mathematical analog to functional / recursive programming (as Turing machines are to imperative languages)
I simply love your videos! I'm a mathematics student, so I'm used to the joy of understanding, but that doesn't make it any less exciting! And your animations are a wonderful, powerful and beautiful help in this delightful process! I may be repeating myself but nonetheless: Thank you! Keep up the great work! :)
Same here :) I'm a computer science student, and I love how you visually explain problems, it makes everything a lot easier to understand. I would have had a much harder time understanding this in a textbook, especially the concepts you explained in part 2. I hope that sometime in the future, we will integrate visual material like this into out science lectures
I saw this puzzle 50 years ago in high school. My classmates were struggling with it. I just sat down and did it without hesitation. It has always been obvious to me. I earned a Masters Degree in Computer Science. It seemed to me trivially obvious that this puzzle was binary counting. 3Blue1Brown explains this beautifully.
I've used Desmos for a little over a year now, and I'm sad that my math classes never use it. I mainly just use it for my game development and for math-fun. It's the best math-function graphing tool I've ever used.
Your videos captured my attention so well in your calculus lectures, that I finally dispelled the notion that I was not a math person, and simply needed to try harder. Finally going back to school, and no longer avoiding math intensive fields! Seriously though, this video is so cool, my girlfriend generally isn’t interested in this kind of stuff, but she loved this as well. Thank you, for working hard to put this stuff out.
I never thought about it, I just found it so simple once I found the pattern, but I never could've imagined it'd be hiding something more complex and so beautiful
I've never even taken a CS class but this is so fascinating! I love seeing videos appreciating the thrilling cohesiveness which seems to appear in every area of mathematics. Absolutely adore these videos, thanks for putting them out there!
another great perspective that I just realized...count up how many times each disc /has/ to move, starting from the bottom. disc n has to move just once, disc n-1 has to move twice (once to get off of disc n and once to get back on again), disc n-2 has to move four times, etc
A simpler rule (only needing to count in base ten (or not at all when you got into the rythm) I noticed when trying this out: - On an odd numbered move: Move the 0-piece once to the right (or left, works both ways as long as you dont switch direction) - On an even numbered move: Move the largest piece you can move (which is never the 0-piece) to the only legal place Which is, of course the same as counting in binary, but a little simpler to put to use imo :)
So nice ! I taught the Hanoi towers when I was teaching algorithmics, because it was the simplest example I could think of with exponential complexity, but I never knew this trick with binary counting ! There is an error in the transcript at 7:55 : the number of steps required is 2^n - 1, not 2^(n-1).
I really loved math when i was studying it at school and you give me so much unsuspected insight into topics i thought i knew very well. Thank you so much. After each of your videos i feel that i learned something new.
Marvelous again. When I was younger, my grandpa taught me a slightly different version: A larger disk not only cannot stop over a smaller one, but it cannot pass over it at all. This essentially makes the game longer, which I suspect was the goal of my grandpa. I kind of remember talking about it with a friend a couple years ago, and I think we came to the conclusion it was very much like classic Hanoi, but with base 3 instead of base 2. Maybe I should take out a pencil and check that again.. EDIT: Shame on me, I should have binged the series like a true 3Blue1Brown fan before posting this.. Keep up the good work!
Holy! This is absolutely amazing. I solved this puzzle for/with a student of mine and came to these conclusions, but the binary counting perspective is simply mesmerizing. Thank you for this video!
Once in year 7 or 8 I was in maths and at the end of the class the teacher asked the class how we could improve our understanding of the content covered in class that day. Some students suggested things like calculating the cost and change (if paid in cash) of grocery expenditure. Another said "counting" and the teacher laughed, and said "counting what?", the student said "anything", the teacher laughed again but louder and with the rest of the class before saying "No [name], I don't think counting is going to help". Looks like counting is pretty useful right about now.
Man, I really appreciate your videos. I must say that I a computer scientist of sorts (Information Systems actually) so binarry is no problem for me and that I loved Tower of Hanoi since I first saw it. So normally to solve the puzzle, I just look if the the ammount of disks, check if it's odd or even to tell the direction of cycle I'll do with the smaller disk, left or right repectvly. Then I just know that I must start moving the smaller according to the cycle, after that, do an obrigatory move, moving smaller, obrigatory move, and so on. Even though I know exactly the logic of how to do it in the most efficient way, I never saw any connection of the puzzle and the rhythm of bynary counting as you showed. I was simply amazed. Thank you, keep doing this amazing work for us.
Wouldn't it make more sense for the binary numbers at 6:05 and 11:20 to be coloured exactly the opposite way they are, i.e. leftmost digit bright blue and rightmost digit dark blue? That way the colour of the digit that flips corresponds to the same colour of disk that's actually moved.
Ooh, good catch! What's funny is that I did it right for the ternary counting in the next video. Ah well, silly mistakes have a pernicious way of sneaking into all my videos, you know?
@@3blue1brown It's the silly mistakes that do not affect the content of the video that much that remind the rest of us that we are in fact listening to an incredibly talented youtuber telling us the wonders of (probably) his favorite subject.
Oh man, I know desmos was a sponsor of this video, but I gotta say, I'm a computer engineering university student, and I use the graphing app from them all the time. I do some very complicated mathematics most of the time, and it's really helpful to be able to put a complicated function in and add some parameters as sliders to see how it affects the shape of the graph. I actually just used it the other day and noticed they added integrals, and I was super excited to see that. On a more related note, this video was excellent. I took an algorithms class in which we studied towers of hanoi solving methods. However, my professor didn't really show the connection between the recursive algorithm and counting in binary. Really insightful stuff.
As someone who's in the middle of a computer networking course, I really like the way you explained binary. While I already know how it works (thanks IPv4!), your explanation is really good, and if I have to ever explain binary to someone else I'll probably have to borrow from this.
I always noticed the recursive property of that problem but could never really mathematically formulate what it was. It's satisfying to get the answer by such a beautiful piece of math. Thank you and keep up the really good and wonderful work.
There's something you overlooked at least in this video and that is quite beautiful. The even-numbered disks either move one space to the right or two spaces to the left, and the odd-numbered ones do the opposite: move one space to the left or two spaces to the right. It's determined by the binary number that each disk adds but modulo 3.
Your channel is absolutely gold dude. Keep up the good work. It's so refreshing to see university level mathematics displayed so entertainingly and so clearly. Thank you.
Neat video. You manage to communicate it in a way that's comprehensive, yet doesn't get boring when you reiterate things. That's impressive! There's one thing I think you fail to mention, and that is that the self similar structure isn't particular to binary numbers, so all the arguments of rolling over and recursion work just as well for other bases. What makes binary appropriate is that smallest "subproblem" of moving a single disk is modelled by a bit, as it can be either moved or unmoved.
Oh the memories! The very first program I wrote for my Assembly Language class project was the solution for the Hanoi puzzle on a Dec PDP11-45 back in 1975.
Wow, this video was really cool! It's awesome how something so seemingly mysterious and strange seems obvious once you get the right perspective on it. Can't wait for the next video!
Dude! Theoretically every recursive program can be represented by a procedural program and this video made me realize the procedural version, which is really cool! 1) rename disks beginning with 1 instead of zero 2) each disk moves exactly as follows: excluding the peg that the disk is currently on, count the remaining pegs left to right the number times equal to the number of the disk 3) Here's the really cool part: move disk n where n is the position of the binary digit flipped to a one while counting in binary up to 2^(x-1) - 1 where x is the number of disks. That sounds horrible, but if I had a towers of hanoi I could show you the algorithm works by counting on my fingers it's so easy.
This is one of your best videos! It really appeals to my sense of pattern :) One small note: I think the plurals of "two", "four" and "eight" are "twos", "fours" and "eights". No apostrophes are needed. Maybe this confusion arises because apostrophes are often used with digits to reduce ambiguity, e.g. "10's", "100's"; this isn't the case for numbers spelt as words.
Either is correct here but they carry different nuances. Pedantry alert! Twos is the plural of two, so that there are three twos in six, as you correctly say. But two's indicates ownership or belonging. Think of when we say my girlfriend's implying my girlfriend's place. (Note that's different from my girlfriends which would suggest polyamory). So the two's implies the place where the twos are listed, the eight's the place where the eights live, and so on.
@@trueriver1950 You are logically quite correct but - forgive me - idiomatically wrong. Just because you can imagine using "two's" to stand in for "two's place" doesn't mean that it's common usage. As far as I know, the construction you describe applies to people's homes, but not digit positions. Of course, it could be that everyone's been doing it like that for decades and I simply hadn't realised... in which case, my apologies. True story: my dad was a primary school teacher a long time ago, and sometimes one of his pupils would say something like "I'm going up my Nan's." His reply was usually something like "would you like to borrow a ladder?" He was such a joker!
I have a physical model of this that I solved myself, and when he started explaining binary this way, I got chills! This is absolutely beautiful, especially because I am familiar with it, but never thought of it with binary! I also really like the serpinski map of the entire game, which is a clear map of how to get between any point in the game. This is amazing, and made my day. Thank you.
“You move it where you’re forced to move it” at 6:45 can be described as “move the piece mod(X/2)+1 to the right”, where X is the piece number (if the smallest piece is 0 as shown)
Thank you. This was absolutely amazing to watch and blew my mind. I had never even considered thinking about the problem like this and I know I'm going to look at other problems and see if this pattern can be applied there as well.
Fun trivia: According to legend, when the full 64 disc puzzle is solved, the world will end. Assuming 1 move per second, it would take 2^64-1 = 1.84*10^19 seconds or 585 billion years, which is incidentally the time it takes until the last star in the universe burns out.
tower of hanoi puzzle is pretty neat. i had to write a recursive method in java that would "solve" the puzzle recursively for any amount of discs. the craziest thing was how much time it took for the compiler when you added a crazy amount of disks like 20 or 50.
Hi @3Blue1Brown I want to share a slightly different interpretation. The process of solving the Tower of Hanoi reminds me classical beginner's programming problem of swapping two variables content. You perfectly know that we need a third variable to swap the content of two of them, this is because we have the constrain that we can't send the information from one place to the other at the same time and without loosing one of the two (I call it quantum swapping :). That's exactly the analogous case in the Hanoi game "you can't put a bigger square on top of a smaller one" this constrain recast the game in a "swapping game", where the sticks works as variables. You are forced to use another stick and therefore follow the binary pattern. Can we apply the XOR trick by achieving a quantum swapping also in the Hanoi game? :) Thanks for your amazing work, a MS CS student.
Or vice versa. I remember in one of the jump-start CD games, you had to solve this a lot. Except, the location of the final stack mattered. So if you had an odd number of boxes, the first box would move to the location of the final stack. If even total, to the stack you aren't supposed to end up on.
Interesting video! I tried a little experiment. In the unrestricted case If there are 3 stones stacked on top of each other labeled 0, 1, and 2, then the next column position of the rock represented by a trit change can be calculated by 3^label modulo columns. I tried this with 4 columns and it works out, but for 3 or 5 columns, the direction of the move toggles left and right.
I remember when I programmed this for the first time, it was one of my first times programming as well. They never explained us anything about the problem, I got to understand that it was recursive (although I didn't know that term formally), but didn't understand it completely, so I looked up for the flow diagram and implemented it. They didn't believe that I solved it, they were right, although an explanation like this could've helped me.
Here is a nice argument about towers of Hanoi, that I think it's pretty trivial but i never see people talking about it: At any valid position in towers of hanoi you have at most 3 valid moves: moving disk 0 on any of the other two pegs and (if at least one of the two other pegs are populated) moving the smallest disk in other pegs. In the ideal solution you never move the same disk twice in a row (because you could just move it once in the right position in the first place), so for odd numbered moves you move disk 0, for even numbered moves you move whatever else is available, in the only available place. The disk you have to move is always forced by this simple argument of "not doing useless moving around": counting in binary, or thinking about recursion does not give useful information to solve the problem (but helps to figure out the total number of moves, see below), because the only choice we have to make is "where do I have to put disk 0 now?" The only "solution" part of the video is thus "always move disk 0 to the right". Or always to the left, depending on where you want to end up in: the total number of moves you have to do is 2^number of disks - 1 (which can easily be deduced from both binary and recursive description above), and the first and last moves are thus moves of disk 0. With a simple modulus 3 operation you realize which peg you end up in: with an odd number of disks your last move will be toward the same peg as your first move, with an even number of disk you will end on the other peg instead. Indeed all disk will move in a rotating fashion in the final solution, in alternating directions: if you move disk 0 to the right disk 1 will move to the left, disk 2 again to the right and so on. This will give you a hint on where the biggest disk, which is moved only once, will end up accordingly to the direction you choose for disk 0. If your goal is to print the sequence of moves without having the actual puzzle then counting in binary will indeed help. But then you need an argument to figure out in which disk the peg is from the binary number: I'll add one here. Since the direction disk moves is easily predictable, you only have to count how many time each disk has been moved: in the binary representation this happens every time you flip its digit to 1, that is you can toss away the least significant digit and divide the number you obtain by two, approximating by excess. Example: if your count is 010011001 and you want to know how many time disk 4 has been moved, you can throw away 4 least significant digits (you don't care where disks smaller than it are) and get 01001, which is 9. This mean up until now you moved disk 4 and bigger 9 times, of which the odd moves disk 4 was moved, even moves you moved a bigger disk (you don't care which one now). Disk 4 has thus been moved 5 times, and thus it did almost one full rotation. As disk 4 is even it moves in the same direction of disk 0, hence if you move disk 0 to the right disk 4 is currently in the C peg, if you move it to the left it is in the B peg.
I didn't make the connection to binary numbers, and I don't even think I really followed or remember it, but, whenever you told me to pause at the beginning of the video, I did determine the recursive way of thinking about it from the bottom of the stack up, and a back and forth pattern of which book to put where, which can be extrapolated to any number of books and I think is the most efficient way to do it.
Actually, it's hard for me to compare my solution to your solution to see if their the same, because I thought of it in an extremely different way. Also, I had no real reason to think my way was the most efficient, though I still think it probably is. For one thing, I didn't think about the three "pegs" having an order at all. (Well, I thought of them as the starting "peg", the goal "peg", and the other "peg", but which is which alternates for each substack at different points in the problem.) I think the you describe and say is related to counting in binary is probably easier to think about, though. My method involves repeatedly stopping and doing a sort of eeny-meeny-miny-moe from the bottem to the top of stacks.
Actually I'm not sure if thinking about binary numbers is easier for me as a human, because the number is something separate I have to keep in my head, and it's not easy to interpret the positions or the books (I'm stacking books on three surfaces, as you suggested) as binary numbers. My method used the current position of the books themselves to determine which book should go where next.
I suspect the number of maximally efficient ways to do it increases with each extra book, probably increasing by two each time, and that I've selected a slightly different maximally efficient method than you have.
I think you could have highlighted the fact that you are moving the piece one right, and if you can't move it one right, two right. Moving straight left in the animation, in the case of skipping over from the middle position or the rightmost position, had me confused for a while. This mechanic also neatly explains why the piece moving can never move back onto the piece that was "trying to get rid of it", which was what I didn't originally understand. Great video though! Thanks!
It's a way to express algorithm from 6:15 in a way, such that a kid without knowledge of binary system will solve Hanoi (and will be happy and would love math in the future). 1. Move the smallest disk to the right (A, B, C are set in cycle A -> B -> C -> A -> ...); 2. Make legal move which not use the smallest disk.
I really like the parallels between this and Gray code, a binary system in which each consecutive number only differs by one bit. The bit that is flipped each time is the same disc that would be moved in towers of hanoi! That is actually how I found this, coming from gray code. Funny how it is the other way around, rather than looking at a puzzle and finding binary, I looked at binary and found a puzzle!
you're in contact with desmos! ask them to integrate the triangle thing for log, pow, root in their graphing calculator! that would be a huge step for getting more people to using it (hopefully) - btw i love these videos thank you so much for all of this. i have learned so so so much from you and i really appreciate the way you explain things
Back (many years ago) when I was learning early coding, the Towers-of-Hanoi puzzle was the way I was taught recursion. You solve for N by solving for (N-1) and then adding one move, and then solving (N-1) again. And so on...
My favorite method is to imagine not a line, but a circle. Keep one hand on the smallest disk. Move it one space clockwise. Then, with your other hand, make the only other legal move possible between the other 2 pegs. Then with your first hand, move the smallest one clockwose again. Continue this pattern until complete. Its especially fun to picture the whole setup on a lazy susan. You could keep your hands almost still in the same spot. The peg with the smallest disk will always be rotated towards whichever hand is holding it (say right), and then the other two pegs will always be equally close yo your left hand. In fact, in this way, another patter emerges because the only other legal move your left hand will be applying will alternate up-down-up-down.
A funny thing is that what you described as the recursive algotithm to solve Hanoi's tower puzzle, is also the iterative algorithm. Here is the algorithm: 1) move disc 0 the pole it hasn't been for the longest amount of moves. 2)Move the only other disc that can move. 3)go to one until you solve it. Both algorithms describe the same proccess but come from a different way of thinking. I have written down a proof for why they are the same and why its the only optimal algorithm ( 2^n -1 moves required for n discs)
A minor point: The usual term is _tens place_ , not "ten's place." The apostrophe implies possession, as if the digit there is taking the place of ten. However, the usual term is plural instead, meaning that the number in that place represents the number of tens. So 35 has 3 in the tens place and 5 in the units place because it is three tens and five units.
Practicing binary counting on your hands will help internalize the binary counting rhythm (and give you much more information density than the usual finger counting methods)
I came across this pattern frequently (no pun intended) while creating a computer in Minecraft. When laying down wire for 2^(n+1) addresses, the 1's place in the address looks like a sine wave of frequency f, the 2's place has a frequency of f/2, and the 2^n's place has a frequency of 2^-n*f. I never thought to apply it to the Towers of Hanoi, though. It also shows up in the rules of cellular automata. Minecraft is technically a cellular automata, but the address pattern wasn't dependent on that fact.
If I wasn’t busy with anything I’d watch all of your videos non stop, well I do that now anyway but I get a headache because I’m trying to juggle it with things I’m doing already.
The problem with "move it over once" is that the way I learned the rules of the puzzle is that you had to go from _leftmost_ peg to _rightmost_. So if you started with an odd number of rings, you would need to move it over twice (or once the opposite way). The way I always solved it was: odd numbered tower/subtower -> move next disc to destination you want the whole tower/subtower to be at even number -> move next disc to non-destination This pattern works throughout the whole puzzle, and I assume it's basically the same as the binary thing, but harder to keep track of. I used to obsessively do this puzzle with playing cards (i didnt have pegs and rings), and i went up to 13 one time (took 2-3 hours I think?). Every new card would take about twice as long, I guess because 2^n (oh hey, binary!!)
If you picture the pegs in a circle instead of a line you could say that when the number of circles is even you do the first move clockwise and if it's odd you do it anti clockwise (or the opposite, depending on how you set up the circle). Basically the direction of the first move would be (-1)^n, where n is the number of discs (and then you decide which one between +1 and -1 is clockwise)
@@kwarsha you can do that thing in a circle in opposite direction too. Like start the disc 0 to move in anti clockwise and disc 1 to clockwise. Will end up at the right solution. Circular things work in both directions. It seems In that case the kind of thumb rule (-1)^n will not work. Agree?
I didn’t find the Hanoi puzzle very challenging because most of the time there is only 1 possible move that isn’t retracing your steps. In some situations where there are two moves that don’t retrace steps (the most their can be) it is still easy to see which move will get you toward your goal, as long as you ask yourself the question “ will this accomplish my goal?”.
There are only 2 possible moves for the configurations where all rings sit on one tower, and 3 possible moves for every other configuration. If you assume that we are always starting or finishing with all rings on one tower, its safe to say that there are always two unique, non retrogressive moves. Therefore every state you arrive upon has an choice, and since there is only one fastest method, every state you arrive upon has a right and wrong answer.
In computer science class the towers of Hanoi problem was used as an introduction to recursive programming. Interesting to see a different way to look at it.
From what I see, this is not only related to binary counting, but another similar thing called Gray codes! Gray codes are very similar to binary numbers, except they have the special property that adding one only requires you to change one bit. Which is kind of analogous to the fact that you can only move one disk at a time. Its pretty interesting and I recommend looking into it!!
Ohh, This reminded me of 2 years ago, there was a competition to see who could solve the tower the fastest in my uni. I didnt join, but I did end up making up a solution to the puzzle, which I can't remember well, but it goes along like this: Always mov the smalles number that wasnt moved in the previous round; Never place odd numbers on top of odd numbers, or even numbers on top of odd numbers; Well, thats all I can remember for now, I will see if I can find my papers that I drew on. Now back to the video.
For all the people who are confused of the trick explained in the video, This is what it means... say i have 2 disks lets count in binary 01 -> move disk 0 to the nearest peg to the right. 10 -> move disk 1 to the nearest peg to the right. 11 -> move disk 0 to the nearest peg to the right. ok you get it now? heres the pattern remember to ignore when a digit turns to 0, but to not ignore when a digit turns to 1 so when i have 1s place, (disk 0) goes to the nearest peg to the right. dont worry about the size for this disk since its the smallest disk. when i have 2s place, (disk 1) goes to the nearest peg to the right UNLESS there is no smaller disk occupying the peg of choice. when i have 4s place, (disk 2) goes to the nearest peg to the right UNLESS, again, there is no smaller disk occupying the peg of choice. if you have a disk and its on the rightmost peg and you transfer it to the right just go to the leftmost peg and check if the peg is being occupied by a smaller disk. how about 4 disks. 01 - 11 -> use disk 2 formation 100 -> disk 2 goes to the nearest peg to the right. 101 - 111 -> repeat instructions i told you earlier :) 1000 -> disk 3 goes to the nearest peg to the right. 1000 - 1111 -> repeat instructions i told you earlier :) again order another smiley again :) so yeah if you master that you can become an absolute OP and solve a 20 ring tower of hanoi : ) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
When I started doing python I made a script to solve the Hanoi towers, but I didn't know what recursion was so I analyzed different cases and found a really weird relationship between numbers and letters. I thought about recursivity as you mention it here, but I solved it completely different for n disks with the most efficient moves. I could show you the code, but it is very messy and I, to this day, still not understand how the math I did really works xDD
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
How is this the first time I hear that _bit_ is short for _binary digit_...
Mind blown.
Yeah I needed a moment after that,
Raphael Schmidpeter same tho
TheGerogero ikr, i counted up to 790 in binary without understanding what bit meant.
TheGerogero same
Does that mean a digit in the ternary system is...
A tit?
I am software developer (who also has a love for math) and it never once occurred to me that counting was a recursive action. I am continuously amazed at how elegant and simple your videos are and how effective they are at showing complex ideas in an approachable way. Thanks for all your hard work!
@@vairavanrenganathan4752 I don't want to put words in his mouth but I believe that he sort of means self-similar. By that, I mean that you can break it down into scaled down problems that are similar in procedure to solve.
same
Any cycle can be represented as a recursive action. Any recursive action can be represented as a cycle.
You might be interested in the Church encoding of numbers in Lambda Calculus which is a mathematical analog to functional / recursive programming (as Turing machines are to imperative languages)
eəėëėəe
I simply love your videos! I'm a mathematics student, so I'm used to the joy of understanding, but that doesn't make it any less exciting! And your animations are a wonderful, powerful and beautiful help in this delightful process!
I may be repeating myself but nonetheless: Thank you! Keep up the great work! :)
Always nice to hear from an enthusiastic math student, and thanks for the kind words. Keep loving math.
Same here :) I'm a computer science student, and I love how you visually explain problems, it makes everything a lot easier to understand. I would have had a much harder time understanding this in a textbook, especially the concepts you explained in part 2. I hope that sometime in the future, we will integrate visual material like this into out science lectures
I saw this puzzle 50 years ago in high school. My classmates were struggling with it. I just sat down and did it without hesitation. It has always been obvious to me. I earned a Masters Degree in Computer Science. It seemed to me trivially obvious that this puzzle was binary counting. 3Blue1Brown explains this beautifully.
Good for you. You're such a smart boy.
I've used Desmos for a little over a year now, and I'm sad that my math classes never use it. I mainly just use it for my game development and for math-fun. It's the best math-function graphing tool I've ever used.
Your videos captured my attention so well in your calculus lectures, that I finally dispelled the notion that I was not a math person, and simply needed to try harder. Finally going back to school, and no longer avoiding math intensive fields! Seriously though, this video is so cool, my girlfriend generally isn’t interested in this kind of stuff, but she loved this as well. Thank you, for working hard to put this stuff out.
"Counting is self-similar" -- fantastic and thought provoking!
I never thought about it, I just found it so simple once I found the pattern, but I never could've imagined it'd be hiding something more complex and so beautiful
Wow, just solved a programming task for the Towers of Hanoi, and remembered that this video existed. Thanks for saving the day _and_ blowing my mind.
I've never even taken a CS class but this is so fascinating! I love seeing videos appreciating the thrilling cohesiveness which seems to appear in every area of mathematics. Absolutely adore these videos, thanks for putting them out there!
This one was incredible! the math was really cool and the animations were insane!
and you're supported by the best graphing calculator ever!!!
+
You probably meant "you ARE the best graphing calculator ever".
I always felt like counting in binary when solving towers of Hanoi! That's amazing now that I understand why.
another great perspective that I just realized...count up how many times each disc /has/ to move, starting from the bottom. disc n has to move just once, disc n-1 has to move twice (once to get off of disc n and once to get back on again), disc n-2 has to move four times, etc
I really like your use of the Computer Modern typeface!
A simpler rule (only needing to count in base ten (or not at all when you got into the rythm) I noticed when trying this out:
- On an odd numbered move: Move the 0-piece once to the right (or left, works both ways as long as you dont switch direction)
- On an even numbered move: Move the largest piece you can move (which is never the 0-piece) to the only legal place
Which is, of course the same as counting in binary, but a little simpler to put to use imo :)
So nice ! I taught the Hanoi towers when I was teaching algorithmics, because it was the simplest example I could think of with exponential complexity, but I never knew this trick with binary counting !
There is an error in the transcript at 7:55 : the number of steps required is 2^n - 1, not 2^(n-1).
I really loved math when i was studying it at school and you give me so much unsuspected insight into topics i thought i knew very well. Thank you so much. After each of your videos i feel that i learned something new.
Marvelous again.
When I was younger, my grandpa taught me a slightly different version: A larger disk not only cannot stop over a smaller one, but it cannot pass over it at all. This essentially makes the game longer, which I suspect was the goal of my grandpa.
I kind of remember talking about it with a friend a couple years ago, and I think we came to the conclusion it was very much like classic Hanoi, but with base 3 instead of base 2. Maybe I should take out a pencil and check that again..
EDIT: Shame on me, I should have binged the series like a true 3Blue1Brown fan before posting this.. Keep up the good work!
Holy! This is absolutely amazing. I solved this puzzle for/with a student of mine and came to these conclusions, but the binary counting perspective is simply mesmerizing. Thank you for this video!
Once in year 7 or 8 I was in maths and at the end of the class the teacher asked the class how we could improve our understanding of the content covered in class that day. Some students suggested things like calculating the cost and change (if paid in cash) of grocery expenditure. Another said "counting" and the teacher laughed, and said "counting what?", the student said "anything", the teacher laughed again but louder and with the rest of the class before saying "No [name], I don't think counting is going to help".
Looks like counting is pretty useful right about now.
Could be s specific question
R
Cool profile pic
Man, I really appreciate your videos. I must say that I a computer scientist of sorts (Information Systems actually) so binarry is no problem for me and that I loved Tower of Hanoi since I first saw it.
So normally to solve the puzzle, I just look if the the ammount of disks, check if it's odd or even to tell the direction of cycle I'll do with the smaller disk, left or right repectvly. Then I just know that I must start moving the smaller according to the cycle, after that, do an obrigatory move, moving smaller, obrigatory move, and so on.
Even though I know exactly the logic of how to do it in the most efficient way, I never saw any connection of the puzzle and the rhythm of bynary counting as you showed. I was simply amazed.
Thank you, keep doing this amazing work for us.
Honestly, these two videos are my favourites of yours. I’ve rewatched them so many times. SO COOL.
Wouldn't it make more sense for the binary numbers at 6:05 and 11:20 to be coloured exactly the opposite way they are, i.e. leftmost digit bright blue and rightmost digit dark blue? That way the colour of the digit that flips corresponds to the same colour of disk that's actually moved.
Ooh, good catch! What's funny is that I did it right for the ternary counting in the next video. Ah well, silly mistakes have a pernicious way of sneaking into all my videos, you know?
@@3blue1brown So modest!🙇🏻♀️
@@3blue1brown It's the silly mistakes that do not affect the content of the video that much that remind the rest of us that we are in fact listening to an incredibly talented youtuber telling us the wonders of (probably) his favorite subject.
@@efulmer8675 Are you implying Cyanogenoid is not in fact listening? Of course they are.
@@msfundio No, I'm not suggesting that at all.
Oh man, I know desmos was a sponsor of this video, but I gotta say, I'm a computer engineering university student, and I use the graphing app from them all the time. I do some very complicated mathematics most of the time, and it's really helpful to be able to put a complicated function in and add some parameters as sliders to see how it affects the shape of the graph. I actually just used it the other day and noticed they added integrals, and I was super excited to see that.
On a more related note, this video was excellent. I took an algorithms class in which we studied towers of hanoi solving methods. However, my professor didn't really show the connection between the recursive algorithm and counting in binary. Really insightful stuff.
Love all your videos. Easy to follow the lectures and the graphics surely make an awesome impact on understanding. Thanks :)
Your videos are all first rate. This one, however, is masterful. It should be the first result presented when one searches for the Hanoi problem.
As someone who's in the middle of a computer networking course, I really like the way you explained binary. While I already know how it works (thanks IPv4!), your explanation is really good, and if I have to ever explain binary to someone else I'll probably have to borrow from this.
I always noticed the recursive property of that problem but could never really mathematically formulate what it was. It's satisfying to get the answer by such a beautiful piece of math. Thank you and keep up the really good and wonderful work.
There's something you overlooked at least in this video and that is quite beautiful. The even-numbered disks either move one space to the right or two spaces to the left, and the odd-numbered ones do the opposite: move one space to the left or two spaces to the right. It's determined by the binary number that each disk adds but modulo 3.
Your channel is absolutely gold dude. Keep up the good work. It's so refreshing to see university level mathematics displayed so entertainingly and so clearly. Thank you.
Neat video. You manage to communicate it in a way that's comprehensive, yet doesn't get boring when you reiterate things. That's impressive! There's one thing I think you fail to mention, and that is that the self similar structure isn't particular to binary numbers, so all the arguments of rolling over and recursion work just as well for other bases. What makes binary appropriate is that smallest "subproblem" of moving a single disk is modelled by a bit, as it can be either moved or unmoved.
Oh the memories!
The very first program I wrote for my Assembly Language class project was the solution for the Hanoi puzzle on a Dec PDP11-45 back in 1975.
Thanks. Great video. I was blown away when you showed the relationship between hanoi towers and binary counting. Way to go!
Wow, this video was really cool! It's awesome how something so seemingly mysterious and strange seems obvious once you get the right perspective on it. Can't wait for the next video!
Your videos helped me out so much when I was learning neural networks, and they're saving my life again :) Thanks!
Dude! Theoretically every recursive program can be represented by a procedural program and this video made me realize the procedural version, which is really cool!
1) rename disks beginning with 1 instead of zero 2) each disk moves exactly as follows: excluding the peg that the disk is currently on, count the remaining pegs left to right the number times equal to the number of the disk 3) Here's the really cool part: move disk n where n is the position of the binary digit flipped to a one while counting in binary up to 2^(x-1) - 1 where x is the number of disks.
That sounds horrible, but if I had a towers of hanoi I could show you the algorithm works by counting on my fingers it's so easy.
Super great video 3Blue1Brown! That connection to recursion is so cool!
On Desmos: it's awesome. I probably use it every day. It's awesome!
This is one of your best videos! It really appeals to my sense of pattern :) One small note: I think the plurals of "two", "four" and "eight" are "twos", "fours" and "eights". No apostrophes are needed. Maybe this confusion arises because apostrophes are often used with digits to reduce ambiguity, e.g. "10's", "100's"; this isn't the case for numbers spelt as words.
+
Either is correct here but they carry different nuances.
Pedantry alert!
Twos is the plural of two, so that there are three twos in six, as you correctly say.
But two's indicates ownership or belonging. Think of when we say my girlfriend's implying my girlfriend's place.
(Note that's different from my girlfriends which would suggest polyamory).
So the two's implies the place where the twos are listed, the eight's the place where the eights live, and so on.
@@trueriver1950 You are logically quite correct but - forgive me - idiomatically wrong. Just because you can imagine using "two's" to stand in for "two's place" doesn't mean that it's common usage. As far as I know, the construction you describe applies to people's homes, but not digit positions. Of course, it could be that everyone's been doing it like that for decades and I simply hadn't realised... in which case, my apologies.
True story: my dad was a primary school teacher a long time ago, and sometimes one of his pupils would say something like "I'm going up my Nan's." His reply was usually something like "would you like to borrow a ladder?" He was such a joker!
... numbers spelled as words ... "spelt" is a grain.
@@wiregold8930 It's a perfectly correct British spelling.
In a Numberphile video about this, I learned that disks with like parity are never consecutive on the same peg.
Your visuals keep getting better! Nice!
well done. I like to think of periodic boundaries where even number disks go one way and odds go the other.
I think you have the best music taste for any UA-cam channel.
Wow. This is already awesome !
And now : let's check part 2. :)
I have a physical model of this that I solved myself, and when he started explaining binary this way, I got chills! This is absolutely beautiful, especially because I am familiar with it, but never thought of it with binary! I also really like the serpinski map of the entire game, which is a clear map of how to get between any point in the game. This is amazing, and made my day. Thank you.
“You move it where you’re forced to move it” at 6:45 can be described as “move the piece mod(X/2)+1 to the right”, where X is the piece number (if the smallest piece is 0 as shown)
Thank you. This was absolutely amazing to watch and blew my mind. I had never even considered thinking about the problem like this and I know I'm going to look at other problems and see if this pattern can be applied there as well.
Fun trivia: According to legend, when the full 64 disc puzzle is solved, the world will end. Assuming 1 move per second, it would take 2^64-1 = 1.84*10^19 seconds or 585 billion years, which is incidentally the time it takes until the last star in the universe burns out.
Program it and it'll be done very soon.
1 move per second is way too slow (for a computer).
True... True
A red dwarf's lifespan is EASILY into the trillions of years. So your anti-science fact is false.
@@shreeganesh441 use delay(1000)
tower of hanoi puzzle is pretty neat. i had to write a recursive method in java that would "solve" the puzzle recursively for any amount of discs. the craziest thing was how much time it took for the compiler when you added a crazy amount of disks like 20 or 50.
Hi @3Blue1Brown I want to share a slightly different interpretation. The process of solving the Tower of Hanoi reminds me classical beginner's programming problem of swapping two variables content. You perfectly know that we need a third variable to swap the content of two of them, this is because we have the constrain that we can't send the information from one place to the other at the same time and without loosing one of the two (I call it quantum swapping :). That's exactly the analogous case in the Hanoi game "you can't put a bigger square on top of a smaller one" this constrain recast the game in a "swapping game", where the sticks works as variables. You are forced to use another stick and therefore follow the binary pattern. Can we apply the XOR trick by achieving a quantum swapping also in the Hanoi game? :) Thanks for your amazing work, a MS CS student.
Lol you can swap the values in python
yes, tower of hanoi is like copying a stack to a new place in memory with the order of sequence remaing intact all the time.
Your channel is lovely. a fantastic corner of UA-cam.
Everyone admires your brilliance when you can break everything down into fundamental components.
_everyone_ ?
Tell that to the kid that used to shove me into the lockers.... 😢
/s 😋
You missed the fact that odd numbers are always moved left and even numbers are always moved right.
nice catch!
Or vice versa. I remember in one of the jump-start CD games, you had to solve this a lot. Except, the location of the final stack mattered. So if you had an odd number of boxes, the first box would move to the location of the final stack. If even total, to the stack you aren't supposed to end up on.
two steps forward, and one step back!
Thanky fer ifnooh (why do i write like this)
James Maxa It’s text in a window; you have time to look at it and correct stuff before submitting it!
Great video you explained everything so well I could feel why counting in binary works in a way others haven’t been able to do.
It's awesome. In the end of your last videos i just smile. Really great, keep it up.:)
Interesting video! I tried a little experiment. In the unrestricted case If there are 3 stones stacked on top of each other labeled 0, 1, and 2, then the next column position of the rock represented by a trit change can be calculated by 3^label modulo columns. I tried this with 4 columns and it works out, but for 3 or 5 columns, the direction of the move toggles left and right.
Really good video!! Never thought of solving the towers of Hanoi with Binary. Love it!
This is EXACTLY why I'm not teaching anymore. I couldn't explain it better. Thank you.
Binary digits? I'd have called them bidgits.
"Not lazy enough. Let's shorten it down to bits." --- Computer Scientists.
bigits just didnt have the same ring to it
SquareWaveHeaven bigots*
@@jadondavid8272 no
I’ve heard of another thing: mijits
I remember when I programmed this for the first time, it was one of my first times programming as well. They never explained us anything about the problem, I got to understand that it was recursive (although I didn't know that term formally), but didn't understand it completely, so I looked up for the flow diagram and implemented it.
They didn't believe that I solved it, they were right, although an explanation like this could've helped me.
Here is a nice argument about towers of Hanoi, that I think it's pretty trivial but i never see people talking about it:
At any valid position in towers of hanoi you have at most 3 valid moves: moving disk 0 on any of the other two pegs and (if at least one of the two other pegs are populated) moving the smallest disk in other pegs. In the ideal solution you never move the same disk twice in a row (because you could just move it once in the right position in the first place), so for odd numbered moves you move disk 0, for even numbered moves you move whatever else is available, in the only available place. The disk you have to move is always forced by this simple argument of "not doing useless moving around": counting in binary, or thinking about recursion does not give useful information to solve the problem (but helps to figure out the total number of moves, see below), because the only choice we have to make is "where do I have to put disk 0 now?"
The only "solution" part of the video is thus "always move disk 0 to the right". Or always to the left, depending on where you want to end up in: the total number of moves you have to do is 2^number of disks - 1 (which can easily be deduced from both binary and recursive description above), and the first and last moves are thus moves of disk 0. With a simple modulus 3 operation you realize which peg you end up in: with an odd number of disks your last move will be toward the same peg as your first move, with an even number of disk you will end on the other peg instead. Indeed all disk will move in a rotating fashion in the final solution, in alternating directions: if you move disk 0 to the right disk 1 will move to the left, disk 2 again to the right and so on. This will give you a hint on where the biggest disk, which is moved only once, will end up accordingly to the direction you choose for disk 0.
If your goal is to print the sequence of moves without having the actual puzzle then counting in binary will indeed help. But then you need an argument to figure out in which disk the peg is from the binary number: I'll add one here. Since the direction disk moves is easily predictable, you only have to count how many time each disk has been moved: in the binary representation this happens every time you flip its digit to 1, that is you can toss away the least significant digit and divide the number you obtain by two, approximating by excess. Example: if your count is 010011001 and you want to know how many time disk 4 has been moved, you can throw away 4 least significant digits (you don't care where disks smaller than it are) and get 01001, which is 9. This mean up until now you moved disk 4 and bigger 9 times, of which the odd moves disk 4 was moved, even moves you moved a bigger disk (you don't care which one now). Disk 4 has thus been moved 5 times, and thus it did almost one full rotation. As disk 4 is even it moves in the same direction of disk 0, hence if you move disk 0 to the right disk 4 is currently in the C peg, if you move it to the left it is in the B peg.
I didn't make the connection to binary numbers, and I don't even think I really followed or remember it, but, whenever you told me to pause at the beginning of the video, I did determine the recursive way of thinking about it from the bottom of the stack up, and a back and forth pattern of which book to put where, which can be extrapolated to any number of books and I think is the most efficient way to do it.
Actually, it's hard for me to compare my solution to your solution to see if their the same, because I thought of it in an extremely different way. Also, I had no real reason to think my way was the most efficient, though I still think it probably is. For one thing, I didn't think about the three "pegs" having an order at all. (Well, I thought of them as the starting "peg", the goal "peg", and the other "peg", but which is which alternates for each substack at different points in the problem.) I think the you describe and say is related to counting in binary is probably easier to think about, though. My method involves repeatedly stopping and doing a sort of eeny-meeny-miny-moe from the bottem to the top of stacks.
I'm not actually sure if I came up with a single solution at all.
Actually I'm not sure if thinking about binary numbers is easier for me as a human, because the number is something separate I have to keep in my head, and it's not easy to interpret the positions or the books (I'm stacking books on three surfaces, as you suggested) as binary numbers. My method used the current position of the books themselves to determine which book should go where next.
I suspect the number of maximally efficient ways to do it increases with each extra book, probably increasing by two each time, and that I've selected a slightly different maximally efficient method than you have.
This is the first video where I knew everything prior to watching it. Defiantly a different feeling when watching.
I think you could have highlighted the fact that you are moving the piece one right, and if you can't move it one right, two right. Moving straight left in the animation, in the case of skipping over from the middle position or the rightmost position, had me confused for a while. This mechanic also neatly explains why the piece moving can never move back onto the piece that was "trying to get rid of it", which was what I didn't originally understand.
Great video though! Thanks!
It's a way to express algorithm from 6:15 in a way, such that a kid without knowledge of binary system will solve Hanoi (and will be happy and would love math in the future).
1. Move the smallest disk to the right (A, B, C are set in cycle A -> B -> C -> A -> ...);
2. Make legal move which not use the smallest disk.
as someone who is still in highschool and looks forward to studying CS in uni, this is a really nice video and helped me a lot :D
Very cool! Great explanation!
This makes me so happy, math like this just is awesome.
I really like the parallels between this and Gray code, a binary system in which each consecutive number only differs by one bit. The bit that is flipped each time is the same disc that would be moved in towers of hanoi! That is actually how I found this, coming from gray code. Funny how it is the other way around, rather than looking at a puzzle and finding binary, I looked at binary and found a puzzle!
you're in contact with desmos! ask them to integrate the triangle thing for log, pow, root in their graphing calculator! that would be a huge step for getting more people to using it (hopefully) - btw i love these videos thank you so much for all of this. i have learned so so so much from you and i really appreciate the way you explain things
Back (many years ago) when I was learning early coding, the Towers-of-Hanoi puzzle was the way I was taught recursion. You solve for N by solving for (N-1) and then adding one move, and then solving (N-1) again. And so on...
I have been struggling with finding the best strategy for this game and you revealed it!!! :O
0:25
nah, you win in the category of "best educator" :)
Love the smooth animation.
This is a whole new way to look at numbers
My favorite method is to imagine not a line, but a circle. Keep one hand on the smallest disk. Move it one space clockwise. Then, with your other hand, make the only other legal move possible between the other 2 pegs. Then with your first hand, move the smallest one clockwose again. Continue this pattern until complete.
Its especially fun to picture the whole setup on a lazy susan. You could keep your hands almost still in the same spot. The peg with the smallest disk will always be rotated towards whichever hand is holding it (say right), and then the other two pegs will always be equally close yo your left hand.
In fact, in this way, another patter emerges because the only other legal move your left hand will be applying will alternate up-down-up-down.
A funny thing is that what you described as the recursive algotithm to solve Hanoi's tower puzzle, is also the iterative algorithm. Here is the algorithm: 1) move disc 0 the pole it hasn't been for the longest amount of moves. 2)Move the only other disc that can move. 3)go to one until you solve it. Both algorithms describe the same proccess but come from a different way of thinking. I have written down a proof for why they are the same and why its the only optimal algorithm ( 2^n -1 moves required for n discs)
A minor point: The usual term is _tens place_ , not "ten's place." The apostrophe implies possession, as if the digit there is taking the place of ten. However, the usual term is plural instead, meaning that the number in that place represents the number of tens. So 35 has 3 in the tens place and 5 in the units place because it is three tens and five units.
Practicing binary counting on your hands will help internalize the binary counting rhythm (and give you much more information density than the usual finger counting methods)
HOW COULDN'T I THINK OF THIS??? SO CLEVER!
I'm going to try it with my child, love the way to correlate to binary with hanoi towers, and the recursive approach
And you just became my favorite youtuber
Brilliant content thank you so much and please continue
I came across this pattern frequently (no pun intended) while creating a computer in Minecraft. When laying down wire for 2^(n+1) addresses, the 1's place in the address looks like a sine wave of frequency f, the 2's place has a frequency of f/2, and the 2^n's place has a frequency of 2^-n*f. I never thought to apply it to the Towers of Hanoi, though. It also shows up in the rules of cellular automata. Minecraft is technically a cellular automata, but the address pattern wasn't dependent on that fact.
If I wasn’t busy with anything I’d watch all of your videos non stop, well I do that now anyway but I get a headache because I’m trying to juggle it with things I’m doing already.
I had to slow down that procedure part at 6:18 just to understand how it works. And it's mind blowing!
The problem with "move it over once" is that the way I learned the rules of the puzzle is that you had to go from _leftmost_ peg to _rightmost_. So if you started with an odd number of rings, you would need to move it over twice (or once the opposite way). The way I always solved it was:
odd numbered tower/subtower -> move next disc to destination you want the whole tower/subtower to be at
even number -> move next disc to non-destination
This pattern works throughout the whole puzzle, and I assume it's basically the same as the binary thing, but harder to keep track of. I used to obsessively do this puzzle with playing cards (i didnt have pegs and rings), and i went up to 13 one time (took 2-3 hours I think?). Every new card would take about twice as long, I guess because 2^n (oh hey, binary!!)
If you picture the pegs in a circle instead of a line you could say that when the number of circles is even you do the first move clockwise and if it's odd you do it anti clockwise (or the opposite, depending on how you set up the circle). Basically the direction of the first move would be (-1)^n, where n is the number of discs (and then you decide which one between +1 and -1 is clockwise)
@@kwarsha you can do that thing in a circle in opposite direction too. Like start the disc 0 to move in anti clockwise and disc 1 to clockwise. Will end up at the right solution. Circular things work in both directions. It seems In that case the kind of thumb rule (-1)^n will not work. Agree?
While watching the video, I just realized, that that would make a beautiful, yet simple, proof using complete induction.
I didn’t find the Hanoi puzzle very challenging because most of the time there is only 1 possible move that isn’t retracing your steps. In some situations where there are two moves that don’t retrace steps (the most their can be) it is still easy to see which move will get you toward your goal, as long as you ask yourself the question “ will this accomplish my goal?”.
There are only 2 possible moves for the configurations where all rings sit on one tower, and 3 possible moves for every other configuration. If you assume that we are always starting or finishing with all rings on one tower, its safe to say that there are always two unique, non retrogressive moves. Therefore every state you arrive upon has an choice, and since there is only one fastest method, every state you arrive upon has a right and wrong answer.
In computer science class the towers of Hanoi problem was used as an introduction to recursive programming. Interesting to see a different way to look at it.
Once you see disk 3 sending you a kiss, you cannot unsee it
Wow, this is amazing and fascinating! 👍🏼😀
From what I see, this is not only related to binary counting, but another similar thing called Gray codes! Gray codes are very similar to binary numbers, except they have the special property that adding one only requires you to change one bit. Which is kind of analogous to the fact that you can only move one disk at a time. Its pretty interesting and I recommend looking into it!!
Awesome, You have to make a lot of these videos !
you forgot to link to your patreon. I'm the new guy there btw [double handed- mid jump freeze frame high five]
Ohh, This reminded me of 2 years ago, there was a competition to see who could solve the tower the fastest in my uni. I didnt join, but I did end up making up a solution to the puzzle, which I can't remember well, but it goes along like this:
Always mov the smalles number that wasnt moved in the previous round;
Never place odd numbers on top of odd numbers, or even numbers on top of odd numbers;
Well, thats all I can remember for now, I will see if I can find my papers that I drew on. Now back to the video.
This is mind blowing, Next time you get towers of hanoi in an interview make sure to implement this 😅
amazing video, thank you for visualizing everything
For all the people who are confused of the trick explained in the video,
This is what it means...
say i have 2 disks
lets count in binary
01 -> move disk 0 to the nearest peg to the right.
10 -> move disk 1 to the nearest peg to the right.
11 -> move disk 0 to the nearest peg to the right.
ok you get it now? heres the pattern
remember to ignore when a digit turns to 0, but to not ignore when a digit turns to 1
so when i have 1s place, (disk 0) goes to the nearest peg to the right. dont worry about the size for this disk since its the smallest disk.
when i have 2s place, (disk 1) goes to the nearest peg to the right UNLESS there is no smaller disk occupying the peg of choice.
when i have 4s place, (disk 2) goes to the nearest peg to the right UNLESS, again, there is no smaller disk occupying the peg of choice.
if you have a disk and its on the rightmost peg and you transfer it to the right just go to the leftmost peg and check if the peg is being occupied by a smaller disk.
how about 4 disks.
01 - 11 -> use disk 2 formation
100 -> disk 2 goes to the nearest peg to the right.
101 - 111 -> repeat instructions i told you earlier :)
1000 -> disk 3 goes to the nearest peg to the right.
1000 - 1111 -> repeat instructions i told you earlier :) again order another smiley again :)
so yeah if you master that you can become an absolute OP and solve a 20 ring tower of hanoi : )
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
When I started doing python I made a script to solve the Hanoi towers, but I didn't know what recursion was so I analyzed different cases and found a really weird relationship between numbers and letters. I thought about recursivity as you mention it here, but I solved it completely different for n disks with the most efficient moves. I could show you the code, but it is very messy and I, to this day, still not understand how the math I did really works xDD
Keith is brilliant!