There must be millions of people who have heard of the Tower of Hanoi puzzle and the simple algorithm that generates the simplest solution. But what happens when you are playing the game not with three pegs, as in the original puzzle, but with 4, 5, 6 etc. pegs? Hardly anybody seems to know that there are also really really beautiful solutions which are believed to be optimal but whose optimality has only been proved for four pegs. Even less people know that you can boil down all these optimal solutions into simple no-brainer recipes that allow you to effortless execute these solutions from scratch. Clearly a job for the Mathologer. Enjoy :)
Hello Mathologer - there is a nice (possibly related, to an extent) puzzle that asks how many different unique ways a spider can put on his shoes and socks, given that each foot must receive a sock followed by a shoe. Can you solve it? (I did, and it’s a nice solution!).
You should get yourself a :CueCat as a technological mascot to go with your website. The best part is that it's cat-shaped. It might even still work, if you can find a computer with a PS/2 keyboard port to use it with.
13:27 In 1,023 moves, moving the smallest disc every other move means we're moving it 512 times, which is 2 (mod 3). So we need to move it counter-clockwise (A -> C -> B -> A) to make sure it ends at B. In general, 2^(n-1) is 1 (mod 3) if n is odd and 2 (mod 3) if n is even, so we should move the smallest disc clockwise if n is odd and counter-clockwise if n is even.
As the idea of clockwise vs counterclockwise isn't clear if the three pegs are in a straight line, I think it's easier to remember (a) if n is odd, first move the small disk to the peg that will hold the ending stack (b) if n is even, first move the small disk to the peg that will not hold the ending stack. Then build the smaller towers by alternating between the two pegs until you can move the largest disk to the peg that will hold the ending stack. This essentially reduces the puzzle to solving the tower with n-1 disks. Keep going like this until you are done.
@@zanti4132 In that case, instead of clockwise vs. counter-clockwise it's left and right. And here we hark back to the old video games where if you moved off the right side of the screen, you reappeared on the left side of the screen.
@@zanti4132 I personally would find it easier to remember: 1. Odd and even n need a different starting move to end up in the right spot. 2. You check where you end up for the smallest odd stack (1 --> which is only one move). 3. If you have an odd n, it's the same move as in 2, if even n, it's the "opposite" move to 2. 4. After that you just continue moving the small piece in the same "direction" (clockwise / counterclockwise or left/right). Thats an easy way to convince yourself that you have the right direction
If the tower has an odd number of discs, first move the smallest to the place you want the tower to end up. If even, move to the space you don't want the tower to end. Then just consistently follow the direction you moved the smaller disc to (clockwise/counterclockwise if arranged as a triangle, to the left/right with wraparound if arranged in a line).
@@nonachyourbusiness1164 Well in Australia we seem to have COVID pretty much under control with no new cases out in the open for a month. This means that life is pretty much back to normal, except it isn't. My uni tries to be as much as possible back to face-to-face. Sounds good but is incredibly messy with the government still requiring social distancing which results in all venues only being at half or less capacity. and also things changing all the time in a seismic way as soon as there is the slightest indication that the virus has managed to escape again from hotel quarantine :(
After checking a feel cases, I think that to get the tower from A to B, you start by moving the smallest disc to: • C, if there are 2n discs; • B, if there are 2n+1 discs.
If you pay attention, you may notice that odd-numbered discs always move one way, while even numbered discs move the other way. Since moving the entire tower involves moving the largest disc once, you want it to move in the right direction. If it has the same parity as the smallest disc, you move them in the same direction; if it's the other parity, they move in opposite directions.
@@blackmephistopheles2273 You can also work it out by feel as the OP suggests. There are only two possibilities, and they should depend only on the parity of the number of disks, because they depend only on the parity of some permutation in the computation. It all comes down to one choice, and it's deterministic, so either left first means left at the end or left first means right at the end. So you actually only need to check a single case. When there is n=1 disk, you move it onto the target peg. So if there are n=2k+1 disks, make your first move toward the target peg, and if n=2k, toward the other peg.
When you don't have the corners but you have the pegs, I would phrase it as "if it's an even number, move the smallest disc to your final destination, if it's an odd number, move it to the peg that you don't want the tower to end up on".
Did you wonder if the words "cheeses", "stools", and "moves" were chosen for (juvenile) humor? Perhaps by asking I've revealed too much about my own sense of humor.
I remember watching 3B1B's video on Hanoi and feeling such awe, that a seemingly simple puzzle could weave recursion and binary counting together. I never thought anything could replicate that awe again! But damn you! Thank you soo much for making me experience that awe again, and this time much muchh more! I just can't wait to get on my computer and try to animate all the animations that you showed today (and perhaps even a generalised version for small n using Frame-Stewart algorithm?). But seriously lot's of love and respect man for making me fall in love with Maths over and over again!
In 1983 I got a Commodore 64 for my 8th birthday. My dad got some 5-1/4" floppy disks full of public domain BASIC games and one of them was Tower of Hanoi. That was the last time I heard of Tower of Hanoi. 🙂
Pretty sure that was about the same time that I got my Commodore 64. I still remember animating the basic algorithm on this computer. Ah yes, the good old days :)
@@Mathologer Back when animating anything was impressive! I read the Programmer's Reference Guide and was making sprites with a bunch of POKE statements and moving them around the screen. I thought I was going to get hired by Atari as soon as I got the word out! But anything was more advanced than those public domain games. I think they came out of user groups where people just mailed floppies around. I remember a reactor simulator called Nuke 64 which I wanted to like but it was ridiculously simple. But there was a Monopoly game called MONOPOLE-64 that I played a lot. There was some good-looking stuff that only used text mode graphics.
@@Mathologer Did the same with the 80286 PCs that the school had bought for the first ever Grundkurs Informatik (using the recursive algorithm, learned about the circle patterns only later in university).
The Tower of Hanoi was the first non-trivial recursion problem I came in contact with, as an example in an introductory textbook of CS in my freshman year at university. I was instantly hooked! :-) None of that boring factorial stuff; now, this was a *real*, powerful algorithm!
@@Nikolas_Davis That's awesome. I don't know if I ever even saw the word recursion in school. I never had any interesting classes. In 1989 I begged my parents for a Turbo Pascal (With Objects! LOL!) compiler for my 14th birthday because I saw it in a store. Then in 1991 I got into a computer camp that had an application with several questions but only one that involved writing code. All you needed to do was find numbers that were both prime numbers and part of the Fibonacci series. I thought it was so easy I needed to make my answer clever to stand out (only 14 kids got into the camp at Ohio Supercomputer Center) so I made a super-small recursive function (not that I knew it was called recursion) that found Fibonacci numbers up to a limit then checked if they were prime as it fell back out. When I got to the camp I asked how they graded it and they said I was the only kid who even got it right LOL. But I got to play with a Cray Y-MP that summer! I hated school so much I kept dropping out because I'd do all my CS work in the first week of class then I'd just have classes I couldn't pay attention in. But one time I kept going until I got an internship before I dropped out. 🙂
I have seen a lot of comments before saying that they needed the video before, but I didn't expect this one to be one of those. This was the topic of my research paper for my gifted class last year, specifically the smallest amount of moves to win a k-poled Hanoi Tower, and I plan to carry on this year. I haven't finished the video, but thank you for this wonderful video anyway. Cheers from Korea! Edit: Never thought about 4-peg Hanoi Towers with the concept of superdisks. Thanks again.
I think he was a rogue time lord himself. Not only that but both the doctor and the toy maker had probably time travelled to 2021 and seen the Mathologer video...
I used to solve towers of hanoi on fights because I had no internet. Solving the 10-peg version with 1023 moves must've been one of the proudest moments in my life :D Edit: huh, I didn't know the "smallest disk" trick explained at 12:18. I just tried to follow the recursive algorithm in my head. Way to trivialize my life's achievment, Mathologer! /s
For n disks, the shorthand trick I remember is that odd heights start by moving the small disk to the destination peg and even starts by moving it to the intermediate peg.
31:05 I believe I read, was mentioned in one of my Logic classes, or ???: For every Provable True Theorem, there are an infinite number of True Unprovable theorems. "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy.".
The trick I always used for the tower of Hanoi is based on odd or even quantity of discs. If you have an odd number of discs then the first move will be to the target tower. If you have an even number, then your first move will be to the other empty tower.
Bioware put this in KotOR, and I had to memorize this thankfully simple recipe because I did multiple playthroughs. Years later, they put it in Mass Effect 1 and I still remembered it. And years later I saw this video and still remembered it. Stuff you do repeatedly as a kid really sticks with you, huh?
As others have shared, I also really enjoy Mathologer's take on these great topics even if other math channels I follow like 3B1B cover them! Every minute spent on this production by the team was worth its weight in gold (or cheese disks) I always get this sense like it's Christmas morning when I see a new video from you guys, thanks for pumping up my weekend!
13:50 if n is odd: clockwise if n is even: counter-clockwise or another way to phrase it: if n is odd: first move is to the target position if n is even: first move is to the OTHER position
This kind of single move algorithms often show up in computer science and an often overlooked follow up question is if their were "multithreading" where if two subsequent movements occurred to and from different pegs they could be done simultaneously as 1 move. Obviously this would only apply to larger n but I would be curious if the solutions for that were actually superior given how ordered the solutions seem to be already.
I love that question. It makes me think of context switching as well. Could any process (aka intelligent but forgetful prisoner) wake up, inspect the current state of the board, and make the next correct move? My instinct is "yes" but I'm not sure.
I figured out best solution for tower of hanoi when i was 6... My dad gave to me tower of hanoi puzzle with 8 peaces and so that i don't bother him said that i should find best solution and left me like that, and then was very surprised that 3 hours later i came to him and said "255", he already even forgot that he gave me the puzzle, but back in those days i figured out the recursive solution to tower of hanoi which impressed my father quite a bit... I was always good with recursive algorithms...
•Always loving your videos. 🥰🥰🥰 Love from India 🇮🇳🇮🇳🇮🇳. •By the way, if you plug in 3 for n, you get 《946/243》(=3.893) •Please make videos on ☆☆☆ Unsolved problems in Mathematics ☆☆☆.
2nd problem is 3^n because there are n discs, each of which has 3 'choices' of pegs - same as the number of vertices on the sierpinski triangle 3rd problem can be done by comparing coefficients of 12/59 and 18sqrt(17)/1003, upon which irrational parts drop out - not sure I want to do this.. -btw, thanks Mathologer!
For the second problem, recursion is T(n) = 3T(n-1) +2 as largest disc moves twice and the n-1 disc pile has to be moved from one extreme to another thrice. Solving the recursion gives the promised beautiful answer - 3^n-1
#1: Nine disks need forty-one (41) moves. My solution is the "minimum of (two times a smaller number of disks plus the minimum of the remaining disk moves) method. #2: An observation: if d (# of disks) < p (# of pegs), then you ALWAYS only need 2*d-1 moves. Basically, having more pegs than disks means you can move every disk to its own peg, including the base disk (to the designated ending peg), then move all of the other disks back on to the next bigger disk, which you should have already moved to that ending peg: (d - 1) + 1 + (d - 1) = 2d - 1. #3: Likewise, if d = p, then m = 2d + 1, since you will have to move whichever disk is on the ending peg (or move another disk, if the ending peg is the only one available to the biggest disk), move the biggie, move the disk you had to move beforehand, and then move all the other disks onto the biggie: (d - 1) + 1(clear off the ending peg) + 1(biggie) + 1(split the double stack up with the starting peg) + (d - 1) = 2d + 1.
Easily one of the best channels on all of youtube. Thank you once again for a very interesting, entertaining, learnful, and inspiring video, professor Burkard! 🙌
I think, because of how common the Tower puzzle is, and how little I've thought about it before, this is one of the most beautiful videos you've done. Despite many years of studying more complex topics, making "simple" problems elegant often gives me the greatest appreciation of mathematics. Thank you as always!
Decided to implement in python before watching. An interesting point I came across was that when recursing, the midpoint and destination swap for subtower move (so the biggest disc can move to the destination unimpeded). As the algorithm recurses down to the base case of 1 (not 0), there are n-1 such midpoint/destination swaps for a tower of size n. Hence, for towers with an odd number of discs, there are an even number of mid/dst swaps, which all cancel out -> first move should be the first disc on to the intended overall destination. Vice versa for even number of discs.
For those who don't know: the reason you only saw a still and heard an audio is that only photos from the TV broadcast and a duplicate audio of the telecast are what BBC have in the archives of the first three episodes. Addendum: there was a proposed sequel to "The Celestial Toymaker" called "Nightmare Fair". Rumour had it that an early draft of the script included the Doctor solving the minimal path problem discussed here for the Trilogic game.
While I never faced it, I was considering the programming interview question: "Solve the Tower of Hanoi puzzle using a recursive function." Here's my problem with this interview question: It doesn't actually *need* a recursive function. I'm of the opinion that if you can craft more supportable code, however less "elegant," it is, you will be doing right by your client. Here's how I would structure it (using English rules for pseudocode): Assume N disks (Labeled Disk 1 through Disk N) Assume 3 rods (Labeled 1, 2, and 3) Assume all disks are first placed on Rod 1. All moves follow the rules (The only disk that can ever be moved to either rod is Disk 1. All other exposed disks can only move to the rod not occupied by Disk 1.) Rule 0: (One time move) If N is even, move Disk 1 to Rod 2; Else, move Disk 1 to Rod 3. LOOP ((N^2)-2)/2 times: Step 1: Move the smallest disk that is not Disk 1. Step 2: If Disk 1 is not on Disk 2, move Disk 1 to Disk 2; Else, If the two non-1 disks are both even or both odd Move Disk 1 to cover the larger disk Else, Move Disk 1 to cover the even disk That's it. One single one-time move, and a loop that bounces back and forth between a non-decisive move, and a 3-option decision move. I believe this approach would be easier to read and maintain by someone who came along later. "Elegance" is great if it saves time, and is clear and easy to maintain. But it doesn't have client value in and of itself.
I've paused on 5:04, because my answer is YES. I'm definitely sure, that I will do this exactly in 1023 moves. Course I read a lot about Hanoi puzzle, couple of time programmed it and taught other people to program it on the lectures as exercises on recursion, but only last year I bought my own physical version (with 8 discs), what leads me to so brave assertion. Only after couple of times "physical/manual" solution I really grocked key principles needed to solve this in circumstance similar to Dr. Who's. First one is really mentioned recursion but in not very computer form rather intention: you want to move subtower on n-1 discs on auxiliary peg to be able to move the disc just under subtower (n-th) to destination peg. Second and this is very important for us human to not solve recursion every time: if your subtower (including full tower) consists of odd number of discs you very first move should be on destination (for current subtower move) peg, if your subtower consists of even number of discs you very first move should be on auxiliary peg. Having this principles you will be able to move Hanoi tower as a calming exercise/solitaire as I do. Now I will continue to watch your video to find what is Mathlogger solution.
13:27 The doctor has to move the tip counter-clockwise because B in that picture corresponds to the lower right corner of the triangle we had looked at before. In general, if you have a tower with n disks, you have to move the tip clockwise for odd n and counter-clockwise for even n for the tower to end up at B (according to this picture). Moving a tower with an even number of disks to B means that you first move a tower with one less disk and thus an odd number of disks to C and since a single-disk tower can be moved with one move only, the tip of a tower with an odd number of disks moves initially to the place where the whole tower will eventually end up. Therefore, if the tower has an even number of disks, the tip has to move to a different place than the final location.
14:00 For odd number of disks, move clockwise; for even, move counter-clockwise. Easy to see. if one disk (or odd), move directly to ending peg; otherwise, not.
for the record, T. Bousch also has a strong contender in the "best title for a math paper, ever" category : Le Poisson n'a pas d'arête (Annales de l'Institut Henri Poincaré, 1999)
30:07 Minimum number of moves for 9 disk and 4 pegs (I think): 41 (^.^). You explained how to divide the disks into 3 superdisks for 8 disks but not for 9. So, just for fun, I tried every possible division in a very inefficient c++ code. I found that you can solve optimally in 41 moves if you divide the disks into 3 superdisks of 2, 3 and 4 disks (from top to down); also dividing them into 4 superdisks of 1, 1, 3 and 4; 1, 2, 2 and 4; AND 1, 2, 3 and 3. I didn't check if these divisions provide different solutions (Challenge for anybody?), but my guess is that, at least, the 3 and 4 superdisk divisions are different optimal solutions. Calculation (hopefully) explained: Assume that you got to solve for 8 disks and 4 pegs, and you divide the 8 disks into 3 superdisks of 1, 3 and 4 disks (from top to down, like Mathologer did). Also note that f(n)=2^n-1 is the optimal number of moves to solve n disks and 3 pegs. Then, (hopefully) it's easy to see that the number of moves, following the Mathologer path, is equal to f(1)+f(3)+f(1)+f(4)+f(1)+f(3)+f(1)=4f(1)+2f(3)+f(4)=2^2 f(1)+2^1 f(3)+2^0 f(4). Note that the arguments of the f's add up to the 8 disks and also note the decreasing powers of 2. (hopefully) it's easy to see that, for n disks, 4 pegs and m superdisks of a1, a2, ..., am disks, such that a1+a2+...+am=n, the resulting number of moves is equal to 2^(m-1)f(a1)+2^(m-2)f(a2)+...+2^0 f(am). For the code, I simply apply this formula to every possible division of the 9 disks into superdisks. I cycle through the possible divisions in a very inefficient and lazy way: I go though all possible lists of between 1 and 9 elements with all possible values between 1 and 9, checking if the accumulation of the elements add up to 9. Seeing the formula, it's easy to see that it's not worth it to check superdisk divisions that are not in decreasing amounts of disks, but whatever. Here's the code for anyone interested: #include #include #include //accumulate algorithm using namespace std; int pow(int b,int e){//b to the power of e with e being a non negative integer int ans=1; for(int i=0;i
13:55 Answer is pretty simple. If N is odd, you move it clockwise to end on B, and counterclockwise to end on C If N is even, you move it clockwise to end on C, qnd counterclockwise to end on B. It has to do with where disc 2 and disc 3 land, and proving that its to do with odd-even parity, and that it holds for all N
This was so cool that I couldn't stop thinking about it. 30:14 "For my programmer friends..." I wrote a demo you can see at jcalz.github.io/hanoi-demo/ that (I think) implements and animates the Frame-Stewart algorithm. Last time I posted this I think it got sent to the spam graveyard, so hopefully his one will stick.
Awesome work! I immediately put in 5 pegs with 100 disks, and surprisingly it didn’t break lol (I set it to a speed of 0.01s so that I could see the whole thing in under a minute)
I also just tried 100 disks with 101 pegs (which is the minimal number of pegs required to minimize disk movement - it only requires 199 moves, which is 2 moves for every disk except the largest one) Much faster than 5 pegs! But obviously not very interesting lol
In the Hanoi puzzle with 3 pegs and n discs, number the discs from 1 to n from the top. Then in the optimal solution an even numbered disc is never placed upon another even disc, nor an odd numbered disc upon another odd disc, but always odd upon even, or vice versa, or onto an empty peg.
I suddenly have an urge to program an animation for something like 35 discs moving using 6 pegs, just so I can sit back and watch 35 discs moving using 6 pegs. This is the reason I like math - it can be very beautiful sometimes... ------------ Update: (I'm going to keep updating this as I discover new things until I'm done with my programming, at which point I'll post the program here) While trying to make this whole thing more algorithmic, I discovered another way to find the next move of a Tower of Hanoi puzzle of 3 pegs given ONLY the state of the puzzle (so none of that "every second move, move the smallest disc" stuff allowed): Say your state is ABBAC (as in disc 5 is on A, disc 4 is on B, disc 3 is on B, disc 2 is on A, and disc 1 is on C) and your ultimate goal is to move disk 5 to peg C. Now, change each of these letters to a number in the following way: for odd-numbered discs, change A --> 0, B --> 2, and C --> 1 (mod 3) as our goal will now be to move disc 5 from 0 to 1. For even numbered discs, change A --> 0, B --> 1, and C --> 2 (basically swap the roles of B and C). This changes ABBAC to 01201. Now follow the following procedure: M5 (the number of times we moved disc 5, mod 3) equals 0, since it started on peg 0 and ended on peg 0 (no change). Q5 is defined as "whether or not we moved disk 5", and can be 0 or 1. With the largest disc, this is easy; Q5 = M5 = 0. Now define M4 as the number of times we moved disc 4 (mod 3 - from now on we're working in mod 3), which is going to be 1 (the second digit in 01201 - this is actually the reason I defined this convoluted procedure of converting letters to numbers, so that we could easily see this correlation). At this point, let's quickly talk about something else. Notice that the order in which we move each of the discs (seen in the animations of 3-peg Hanoi in the video) is an ABACABADABA pattern (or rather, a 121312141213121 pattern). We will use this to our advantage; let's say we chop the string of moves 1213121412131215121312141213121 - which is the solution for 5-disc 3-peg Hanoi - somewhere in the middle, like here: 121312141213121512131 / 2141213121 Note that the number of 4s before the split is always going to be the number of 5s, and possibly one more. Similarly, M3 (going with the notation used earlier) is always M4 + M5 + [either 0 or 1]; M2 = M3 + M4 + M5 + [either 0 or 1], etc. Redefine Q_n to be this [either 0 or 1] value for disc n - note that this doesn't change the value of Q5 - and continue working as follows: M4 = 1 = M5 + Q4 = 0 + Q4 ∴ Q4 = 1 M3 = 2 = M5 + M4 + Q3 = 0 + 1 + Q3 ∴ Q3 = 1 M2 = 0 = M5 + M4 + M3 + Q2 = 0 + 1 + 2 + Q2 ∴ Q2 = 0 (remember, mod 3...) M1 = 1 = M5 + M4 + M3 + M2 + Q1 = 0 + 1 + 2 + 0 + Q1 ∴ Q1 = 1 Remember, these Mn values are coming from the string of numbers we found earlier (01201). Now organize these Q values from smallest to largest disc: 10110 Pick the first 0 you find (left to right), which in this case is Q2, which corresponds to disc 2. Move the disc you chose from A-->C-->B if odd (since this is the direction in which we want disc 5 to move), and move the disc from A-->B-->C if even. This means the next move of the puzzle is to move disc 2 from A to B. ...and that's it! Whew, quite long, don't you think? I'm still surprised it's even possible, so I'm not going to complain though... Time to implement this into my code!
It's often used to teach recursion. And last semester our professor used Fibonacci sequence and towers of Hanoi as two examples to show different programming languages. Including postscript, which was quite fascinating
I've been recently working on Tower of Hanoi animations for my channel and in the process discovered some of the stuff mentioned in the video, for example the algorithm to solve Tower of Hanoi without recursion by moving the smallest disk every second turn. I also proved why it works. Answer to challenge questions: Direction to move the smallest disk is: if (n is even) then Right else Left That's because to move (N)-tower in some direction, you first have to move (N-1)-tower in the opposite direction, so the direction to move the smallest disk changes every time and it starts with Left for N=1 disk The number of turns is (as mentioned in the video) equal to the number of reachable states, which is = 3^n, because: there are 'n' disks, each disk can be placed in one of 3 towers, so there are 3^n valid states. Each valid state is reachable with a standard recursive algorithm, so there are 3^n reachable states. Another interesting puzzle for you: given a number of disks (N) and a number of turns (T), how do you quickly find the state of all disks in the optimal solution of N disks after making T turns? I had to solve this puzzle while making my Tower of Hanoi animations, so I can instantly preview my animation at any moment in time (instead of re-playing it from the start), which becomes increasingly important with several-hour animations. Check out my channel for these animations: I've already published the shorter ones and longer once, including 10-hour 16-disk solution animation, coming soon:)
I've played enough (3 peg) Hanoi puzzles in various video games that moving the tower in the minimum moves is easy... I sometimes end up second guessing myself on the 'direction' the tip of the tower has to go... Although seeing the pattern play out, I now get that you only have to determine which direction the base has to move, and then the direction the top piece moves is based on if there are an odd number of pieces (same direction as the bottom), or even (opposite direction of the bottom).
So happy to see the video for this month. Wish they were more times then once a month, but am sure it takes a long time to make these, and happy that you make them
Yes, sadly my uni job keeps me insanely busy these days. That and family leaves hardly any time for Mathologer. Anyway, I'll keep trying to put one out every month.... :)
18:16 (shortest solution with extra adjacent-peg rule): it is obvious that we have to visit all the nodes in the graph, and a path traversing x nodes exactly once requires x-1 arcs. So, the question boils down to evaluate the number of nodes in such a graph, that is essentially composed by all the possible valid configurations of disks on pegs. With 1 disk we have 3 valid configurations (the smallest triangle), with 2 disks we have 9 valid configurations (the 2nd-smallest triangle), with 3 disks we have 27 valid configurations (...), etc. Note that when we assign a "set" of disks to a peg, their placement is uniquely determined (since it must comply the no-big-over-small rule) by the total ordering of disk sizes. Then, the total number of configurations is the number of ways to assign n disks to 3 pegs; that is the question "with n available digits, how many numbers can I build that are 3-digits long" and the answer is 3^n. Having 2^n nodes in the graph, having to traverse all of them exactly once, the shortest "adjacent-peg" solution is of length 3^n-1 with 3 pegs; more generally with p pegs the shortest "adjacent-peg" solution is of length p^n-1 by the same reasoning.
I'm currently finding tower of Hanoi a good muse problem for getting my flat in order! (Long overdue tidying) So extra specially well pleased I watched this recently! (I'm picking things up off one surface, and putting them down on another temporarily.. Tower of Hanoi, I've learned (through this video) teaches that it's much less work with more permanent (rather than temporary - eg a table top or 2, rather than balancing pins on the tops of empty beer bottles while waiting to see if enough needless etc will emerge from the mess quantity to warrant a "sewing stuff box"...
I feel like this must have some application in cpu register allocation or cache hierarchies. Especially interesting in light of the idea of grouping disks into super disks etc.
To me, it is amazing that the state transition graph is (1) connected and (2) planar. The connectedness I can make sense of. But I can think of no obvious explanation for its being planar.
Trying to get from A to B, I think if N is odd, you move the smallest disk clockwise, otherwise, move it counterclockwise. As far as the other disks, I think each move is forced by where the smallest one is.
I had the Tower of Hanoi on my graphing calculator way back in middle school, and used to 'speedrun' 10 disc solutions when I was bored in math class, so I can actually say with relatively high confidence I could still pull it off without a mistake. There's a nice rhythm to it once you get the hang of it, almost meditative. Interestingly, because it was presented as a straight line of pegs instead of a triangle of them, I never stumbled on the clockwise/counterclockwise solution to figuring out where the top disc goes, another example of how how you frame a problem affects how you solve it. Instead, my method was to think in terms of a start peg, a storage peg, a goal peg, and partial pyramids. Move the top part of the pyramid to one peg (the target peg if the pyramid has odd number of discs, the storage peg if it has an even number), move the top disc of the bottom part of the pyramid to the other peg, move the top part of the pyramid on top of it, and now you have a bigger top part and a smaller top part. Repeat until there's just one disc on the start peg, move it to the other peg, and then you have a new whole pyramid, and you recurse back to the start, just with the start and the storage peg switched places, and a pyramid one disc shorter.
18:20 The number of moves is just the number of possible states (3^n) minus 1, since the algorithm visits each state exactly once; and since the initial state requires 0 moves to reach from the initial state. The number of pegs is always 3; so, the number of moves, for n discs, is: (3^n)-1. Tada! 😎
1st question: which way should the smallest disc go first? (there are too many details here, just to be clear) There are 6 moves in 1 complete cycle of the smallest disc, as there are 3 pegs. At 1, 2 (mod 6) the smallest disc is on the first peg you go to. At 3, 4 (mod 6), the smallest disc is on the 2nd peg. At 5, 0 (mod 6), it returns to the starting peg. Because 2*2 = 1 (mod 3), 2^n = 1 (mod 3) if n is even and 2^n=2 (mod 3) if n is odd. (induction from 2^1=2) => 2^n-1 = 0 (mod 3) if n is even, 2^n-1 = 1 (mod 3) if n is odd. As 2^n-1 is odd, 2^n-1=3 (mod 6) if n is even, 2^n-1=1 (mod 6) if n is odd. So if n is odd, make your first move to the target peg but if n is even, make your first move to the other peg.
The classical algorithm is a recursive one and pretty simple. However, there also is a non-recursive solution. Figuring that one out (+ implementing it) makes for a fun afternoon
Hi, I post my answer before reading the other comments (about where to move the first disc): - if you have only one disc, you move it to the destination peg, - if you have two discs, you move the small one to the third peg, not the destination one, - so the rule is : if the number of discs is odd, you move the first disc to the destination peg, if it is even, you move it to the other peg About the rule for moving the other discs afterwards (moving the small one clock-wise, every even step, and for the odd steps : do the only move you can), I found it when I was 18, just observing what happens when you apply the recursive algorithm. I successed doing the recursive algorithm up to 4 discs, but very difficult with 5, and impossible for me with more. You don't know where you are any more. Thank you for this video. See you.
Tower of Hanoi is a super popular interview question, so much so that I bet interviewers have to tweak the question so it's new to interviewees. I imagine asking about more pegs is a frequent extension. Now I feel prepared. Great vid
I just recently found a code golf where the challenge was to quine that output a unique program every iteration, without repeat, for however many iterations. I immediately thought of Gray code, and have been absorbed. This is great!
Variations of Tower of Hanoi with more than one stack of disks are described in U.S. pat. no. 7,566,057. The simplest Multistack T of H (2X4) involves four pegs on the corners of a square with two different colored stacks arranged diagonally to each other. The object is to reverse the positions of the two stacks. The restriction is that each stack can only be moved among its starting and ending pegs and one of the pegs on the other diagonal. Also covered by the patent are a 2X5 variant of the Reve's version of T of H. Both the 2X4 and the 2X5 are the first iterations of their respective series. P.S.: the last puzzles mentioned are in a puzzle museum on one of the U of Indiana campuses.
For the direction of the smallest disk for n disks, check the parity of n. If n is odd, start by moving the disk onto the peg where you want the final disk. If n is even, start by moving it to the other peg. Then continue the small disk movement in the same circular direction. In the Doctor-Toymaker setup, that means that an even n moving to peg B requires moving the smallest disk counterclockwise, while an odd n requires moving the disk clockwise.
I distinctly remember seeing this on our steam driven television the first time round... by then I’d graduated from watching from behind the sofa (for safety reasons...), it had a big impact on me ... I made a version of the game at school and started a craze for playing it that lasted two whole weeks! Nerd heaven.....
Yea I think I could figure it out if I was in the Doctor's shoes, I figured it out when I was, Idk, early in my teens? And it's also mindlessly easy to execute *if* you get the first move right, everything else just falls into place. The Doctor is far smarter than me, and more experienced than I was or even am now
But as always with your videos even if it's a topic I find myself familiar with you manage to surprise with the depth it can be taken to and the adjacent fields we can otherwise analyse it through. One of the channels I get the happiest about seeing longer videolengths
For the second problem, recursion is T(n) = 3T(n-1) +2 as largest disc moves twice and the n-1 disc pile has to be moved from one extreme to another thrice. Solving the recursion gives the promised beautiful answer - 3^n-1
The Tower of Hanoi puzzle is probably my favorite puzzle is math. I remember in highschool I tried trying to find an algoritm for the shortest solution for 3 pegs... but I ended up essentially using brute force, by writing out the solution for up to 5 disks and circling patterns until I found an algorithm that I thought worked. Took me ~8 hours to notice that numbers of disks with the same parity all had the same moves at the beginning. Also that the first half is always followed by a move from the starting tower to the target tower followed by the first half of moves backwards with the to and from towers swapped and the starting tower and the target towers swapped. Later I was able to come up with the reasoning for this, which led to the recursive algorithm. Being that in order to solve for n disks, you must solve for n-1 disks, but with the target and extra tower swapped so that the last disk is able to be moved to the target tower. Then you just have to undo what you just did, but with the starting tower and the target tower swapped. I then programmed this algorithm in Java and made it animate the solution. Probably my favorite programming/math project to date. My first attempt at this took me ~80 hours, but it was my first time designing/programming a GUI. Though my second attempt only took me ~20 hours. I'm probably not going to watch the entire video because I want to try finding the solution for the n-peg hanoi puzzle myself, hopefully without the brute force this time.
My solutions: If I want it to be in position B, then I will have to move the tip to C. Therefore the answer is counterclockwise. Using the minimal number of steps, you have to move the tip to C if you want it on B and if you want it on C, then you will have to move the tip to B. The formular was (2^n)-1 for n layers and (2^n+1)-1 for n+1 layers.
4:58. Yes I would be happy to, though when I saw this when originally transmitted I was only 11 and it was beyond me then. Another BBC programme, Blue Peter, ran a competition in parallel with the initial transmission of this story inviting people to submit solutions and I remember that the winners of the coveted Blue Peter badge submitted their solution on a l-o-n-g strip of paper from a bus ticket roll. Years later i independently discovered the recursive algorithm. I was at Uni when I first was shown the iterative algorithm in a computer class to demonstrate that recursion is generally time and data hungry. The take away was to only use recursion if we didn't know any iterative way. And it was only because I pestered the lecturer that I was shown the validity proof. That's because I know the iterative solution. That's one that is harder to explain why it's valid but easier to do in practice. Incidentally it is a lot less machine cycles if you track the program on a computer for each algorith. If you get the first move right the rest is automatically correct.
I remember finding formula for the smallest number of moves required for n disks and an algorithm to solve it, when I were 12 years old. Those were great times.
Sure, the problem is to find the time. Since COVID my job at uni really got insane and I just don't have enough time to really go for a complex project like this :(
Searching a sorted list only takes log_2 N steps. Yet, maintaining a sorted list can be costly in terms of space/time whilst adding and removing values. Using the concepts of the Tower of Hanoi puzzle, multiple sorted lists can be maintained while amortizing the cost of merging the list over a large time scale and using little additional space. (If one doesn't care about space then a double-linked list has constant time insert/removal.)
I've just seen this video (16/10/2022). It occurred to me that we can trivially fill in the table (at 33:33) by well over 50% for any number of pegs and disks. So the left two columns are always 1 and 3 moves. And the top row (P=3) is always 2^N - 1. Now looking at the middle downward left to right diagonal (where P = N + 1) we have, for any N, the minimum moves M is always just 2N - 1. This is also true for all P > N + 1. Similarly, if we reduce P by one so P = N then we always need an extra two moves giving M = 2N + 1 for P = N. So I reckon that's a lot of useful minima for any P >= N and for P=3. Well over 50% complete with a set of constraints and boundaries for any N and P. Of course, we could probably fill in the rest of the table by reductive induction from P = N +1. (For this stage we'll need to maintain P > N/2).
"If you're ever captured by an evil toymaker, you'll be ready"
And they say math has no real-world applications.
Underrated comment :)
Very cool!
I much prefer an evil toymaker to the "motorcycle mathematicians" my sarcastic (as I was told) Calc II teacher used to love throwing us.
:D :D :D
@@Shadow-xb2ce ?
That's it, I'm stealing that. I'm no longer a Software Engineer, I'm an Algorithmologist.
Let's hope this word catches on :)
@@Mathologer It already caught on with me 🙂.
40 minutes of Professor Polster + links to 400 hours of reading = 1 helluva education
Every single time, thank you for all you're doing, Mathologer!
Enjoy :)
Hear!
I know right? I LOVE the references in the description of Mathologer videos
I guess it is a BYOW (bring your own wine) party
Don't let other UA-camrs doing the same topics stop you. Please! I like to see different takes on the same topic from my favorite UA-camrs.
There must be millions of people who have heard of the Tower of Hanoi puzzle and the simple algorithm that generates the simplest solution. But what happens when you are playing the game not with three pegs, as in the original puzzle, but with 4, 5, 6 etc. pegs? Hardly anybody seems to know that there are also really really beautiful solutions which are believed to be optimal but whose optimality has only been proved for four pegs. Even less people know that you can boil down all these optimal solutions into simple no-brainer recipes that allow you to effortless execute these solutions from scratch. Clearly a job for the Mathologer. Enjoy :)
Hello Mathologer - there is a nice (possibly related, to an extent) puzzle that asks how many different unique ways a spider can put on his shoes and socks, given that each foot must receive a sock followed by a shoe. Can you solve it? (I did, and it’s a nice solution!).
You should get yourself a :CueCat as a technological mascot to go with your website. The best part is that it's cat-shaped. It might even still work, if you can find a computer with a PS/2 keyboard port to use it with.
Is it just me or is it very easy to read this paragraph in Mathologer's voice? :)
@@superman00001 Ah, that's a nice one. Had not heard of this one before :)
@@ChefSalad :CueCat never heard of that one before. Of course it would be great to have cat shaped remote control :)
17:40 "This recipe also solves another Hanoish puzzle." I think the correct adjective is "Hannoying".
:)
Hanoisy
So Hanoid! Saigonna say that. Halong ago you see this? Gotta be quicker next Thai.
Hahaha
Best comment of the day! 💕🐝
13:27 In 1,023 moves, moving the smallest disc every other move means we're moving it 512 times, which is 2 (mod 3). So we need to move it counter-clockwise (A -> C -> B -> A) to make sure it ends at B.
In general, 2^(n-1) is 1 (mod 3) if n is odd and 2 (mod 3) if n is even, so we should move the smallest disc clockwise if n is odd and counter-clockwise if n is even.
As the idea of clockwise vs counterclockwise isn't clear if the three pegs are in a straight line, I think it's easier to remember (a) if n is odd, first move the small disk to the peg that will hold the ending stack (b) if n is even, first move the small disk to the peg that will not hold the ending stack. Then build the smaller towers by alternating between the two pegs until you can move the largest disk to the peg that will hold the ending stack. This essentially reduces the puzzle to solving the tower with n-1 disks. Keep going like this until you are done.
I thought about it with the recursion: upper ten to B requires upper nine to C, which requires upper eight to B, 7 to C, 6 B, 5 C,...
@@zanti4132 In that case, instead of clockwise vs. counter-clockwise it's left and right. And here we hark back to the old video games where if you moved off the right side of the screen, you reappeared on the left side of the screen.
@@zanti4132 I personally would find it easier to remember:
1. Odd and even n need a different starting move to end up in the right spot.
2. You check where you end up for the smallest odd stack (1 --> which is only one move).
3. If you have an odd n, it's the same move as in 2, if even n, it's the "opposite" move to 2.
4. After that you just continue moving the small piece in the same "direction" (clockwise / counterclockwise or left/right).
Thats an easy way to convince yourself that you have the right direction
@@DerKiesch I agree about that being the easiest way to remember this 👍🏻.
23:33 there’s another lovely pattern that’s easy to miss in this table; look at the antidiagonals. See anything familiar?
If the tower has an odd number of discs, first move the smallest to the place you want the tower to end up. If even, move to the space you don't want the tower to end. Then just consistently follow the direction you moved the smaller disc to (clockwise/counterclockwise if arranged as a triangle, to the left/right with wraparound if arranged in a line).
So happy to see a new video. I was really upset when you didn't upload in February.
Yes, sadly insanely busy at uni at the moment. COVID is still messing things up in a big way for us and so hardly any time for Mathologer :(
@@Mathologer 😢
@@Mathologer How is it affecting you guys? My uni is completely remote now and emphasis has been put on self-study
@@nonachyourbusiness1164 Well in Australia we seem to have COVID pretty much under control with no new cases out in the open for a month. This means that life is pretty much back to normal, except it isn't. My uni tries to be as much as possible back to face-to-face. Sounds good but is incredibly messy with the government still requiring social distancing which results in all venues only being at half or less capacity. and also things changing all the time in a seismic way as soon as there is the slightest indication that the virus has managed to escape again from hotel quarantine :(
After checking a feel cases, I think that to get the tower from A to B, you start by moving the smallest disc to:
• C, if there are 2n discs;
• B, if there are 2n+1 discs.
Ooooooo, nice thought, I'll have to verify. Well played mate.
You can see that this has to be the case, due to how you move the first (0+1) disk.
If you pay attention, you may notice that odd-numbered discs always move one way, while even numbered discs move the other way. Since moving the entire tower involves moving the largest disc once, you want it to move in the right direction. If it has the same parity as the smallest disc, you move them in the same direction; if it's the other parity, they move in opposite directions.
@@blackmephistopheles2273 You can also work it out by feel as the OP suggests. There are only two possibilities, and they should depend only on the parity of the number of disks, because they depend only on the parity of some permutation in the computation. It all comes down to one choice, and it's deterministic, so either left first means left at the end or left first means right at the end.
So you actually only need to check a single case. When there is n=1 disk, you move it onto the target peg. So if there are n=2k+1 disks, make your first move toward the target peg, and if n=2k, toward the other peg.
When you don't have the corners but you have the pegs, I would phrase it as "if it's an even number, move the smallest disc to your final destination, if it's an odd number, move it to the peg that you don't want the tower to end up on".
The best thing about Reve's puzzle; "We're going to have some cheese."
But don't do it with camembert on a hot day. You'll end up with one super puddle of cheese.
Did you wonder if the words "cheeses", "stools", and "moves" were chosen for (juvenile) humor? Perhaps by asking I've revealed too much about my own sense of humor.
I remember watching 3B1B's video on Hanoi and feeling such awe, that a seemingly simple puzzle could weave recursion and binary counting together. I never thought anything could replicate that awe again!
But damn you! Thank you soo much for making me experience that awe again, and this time much muchh more! I just can't wait to get on my computer and try to animate all the animations that you showed today (and perhaps even a generalised version for small n using Frame-Stewart algorithm?).
But seriously lot's of love and respect man for making me fall in love with Maths over and over again!
That's great. Cannot wait for the first animations to pop up :)
Well, binary counting is recursive just by itself already.
Don't cuss on a Great Professor who's probably much older than you
These are some of your most visually satisfying animations to date, which is really saying something!
Increbile, the amount of astractions one's mind can demarcate around a given subject. Just wow, maths is beautiful
I checked your channel three times this week, I was expecting this, LET'S GOOOOO
Yes, sadly insanely busy at work and hardly any time for Mathologer :)
In 1983 I got a Commodore 64 for my 8th birthday. My dad got some 5-1/4" floppy disks full of public domain BASIC games and one of them was Tower of Hanoi. That was the last time I heard of Tower of Hanoi. 🙂
Pretty sure that was about the same time that I got my Commodore 64. I still remember animating the basic algorithm on this computer. Ah yes, the good old days :)
@@Mathologer Back when animating anything was impressive! I read the Programmer's Reference Guide and was making sprites with a bunch of POKE statements and moving them around the screen. I thought I was going to get hired by Atari as soon as I got the word out! But anything was more advanced than those public domain games. I think they came out of user groups where people just mailed floppies around. I remember a reactor simulator called Nuke 64 which I wanted to like but it was ridiculously simple. But there was a Monopoly game called MONOPOLE-64 that I played a lot. There was some good-looking stuff that only used text mode graphics.
@@Mathologer Did the same with the 80286 PCs that the school had bought for the first ever Grundkurs Informatik (using the recursive algorithm, learned about the circle patterns only later in university).
The Tower of Hanoi was the first non-trivial recursion problem I came in contact with, as an example in an introductory textbook of CS in my freshman year at university. I was instantly hooked! :-) None of that boring factorial stuff; now, this was a *real*, powerful algorithm!
@@Nikolas_Davis That's awesome. I don't know if I ever even saw the word recursion in school. I never had any interesting classes. In 1989 I begged my parents for a Turbo Pascal (With Objects! LOL!) compiler for my 14th birthday because I saw it in a store. Then in 1991 I got into a computer camp that had an application with several questions but only one that involved writing code. All you needed to do was find numbers that were both prime numbers and part of the Fibonacci series. I thought it was so easy I needed to make my answer clever to stand out (only 14 kids got into the camp at Ohio Supercomputer Center) so I made a super-small recursive function (not that I knew it was called recursion) that found Fibonacci numbers up to a limit then checked if they were prime as it fell back out. When I got to the camp I asked how they graded it and they said I was the only kid who even got it right LOL. But I got to play with a Cray Y-MP that summer! I hated school so much I kept dropping out because I'd do all my CS work in the first week of class then I'd just have classes I couldn't pay attention in. But one time I kept going until I got an internship before I dropped out. 🙂
I have seen a lot of comments before saying that they needed the video before, but I didn't expect this one to be one of those. This was the topic of my research paper for my gifted class last year, specifically the smallest amount of moves to win a k-poled Hanoi Tower, and I plan to carry on this year. I haven't finished the video, but thank you for this wonderful video anyway. Cheers from Korea!
Edit: Never thought about 4-peg Hanoi Towers with the concept of superdisks. Thanks again.
Well, have fun with your research paper :)
The toy maker himself wouldn't expect this video to come out one day during that time
I think he was a rogue time lord himself. Not only that but both the doctor and the toy maker had probably time travelled to 2021 and seen the Mathologer video...
I used to solve towers of hanoi on fights because I had no internet. Solving the 10-peg version with 1023 moves must've been one of the proudest moments in my life :D
Edit: huh, I didn't know the "smallest disk" trick explained at 12:18. I just tried to follow the recursive algorithm in my head. Way to trivialize my life's achievment, Mathologer! /s
:)
For n disks, the shorthand trick I remember is that odd heights start by moving the small disk to the destination peg and even starts by moving it to the intermediate peg.
31:05 I believe I read, was mentioned in one of my Logic classes, or ???: For every Provable True Theorem, there are an infinite number of True Unprovable theorems. "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy.".
The trick I always used for the tower of Hanoi is based on odd or even quantity of discs.
If you have an odd number of discs then the first move will be to the target tower.
If you have an even number, then your first move will be to the other empty tower.
Bioware put this in KotOR, and I had to memorize this thankfully simple recipe because I did multiple playthroughs. Years later, they put it in Mass Effect 1 and I still remembered it. And years later I saw this video and still remembered it.
Stuff you do repeatedly as a kid really sticks with you, huh?
As others have shared, I also really enjoy Mathologer's take on these great topics even if other math channels I follow like 3B1B cover them! Every minute spent on this production by the team was worth its weight in gold (or cheese disks)
I always get this sense like it's Christmas morning when I see a new video from you guys, thanks for pumping up my weekend!
:)
13:50
if n is odd: clockwise
if n is even: counter-clockwise
or another way to phrase it:
if n is odd: first move is to the target position
if n is even: first move is to the OTHER position
Sir can I say, despite the time, your videos are ABSOLUTELY AMAZING! KEEP UP THE GOOD WORK! :)
This kind of single move algorithms often show up in computer science and an often overlooked follow up question is if their were "multithreading" where if two subsequent movements occurred to and from different pegs they could be done simultaneously as 1 move. Obviously this would only apply to larger n but I would be curious if the solutions for that were actually superior given how ordered the solutions seem to be already.
I love that question. It makes me think of context switching as well. Could any process (aka intelligent but forgetful prisoner) wake up, inspect the current state of the board, and make the next correct move? My instinct is "yes" but I'm not sure.
@@heaslyben probably. Of course it depends on the actual problem, but one could use a hamming code approach for that. Aka coding a failsafe
I figured out best solution for tower of hanoi when i was 6... My dad gave to me tower of hanoi puzzle with 8 peaces and so that i don't bother him said that i should find best solution and left me like that, and then was very surprised that 3 hours later i came to him and said "255", he already even forgot that he gave me the puzzle, but back in those days i figured out the recursive solution to tower of hanoi which impressed my father quite a bit... I was always good with recursive algorithms...
Cool :)
The iterative algorithm is harder to spot, and would have impressed him even more
(I won't give it here, as several other commented already have)
•Always loving your videos. 🥰🥰🥰
Love from India 🇮🇳🇮🇳🇮🇳.
•By the way, if you plug in 3 for n, you get 《946/243》(=3.893)
•Please make videos on ☆☆☆ Unsolved problems in Mathematics ☆☆☆.
Oh, what could be nicer than a weekend with a mathologer video :)
2nd problem is 3^n because there are n discs, each of which has 3 'choices' of pegs - same as the number of vertices on the sierpinski triangle
3rd problem can be done by comparing coefficients of 12/59 and 18sqrt(17)/1003, upon which irrational parts drop out - not sure I want to do this..
-btw, thanks Mathologer!
3^n-1 actually (for the path length)
@@HansMaurer. That's it :)
For the second problem, recursion is T(n) = 3T(n-1) +2 as largest disc moves twice and the n-1 disc pile has to be moved from one extreme to another thrice. Solving the recursion gives the promised beautiful answer - 3^n-1
less one, because the initial position does not count as a move
#1: Nine disks need forty-one (41) moves. My solution is the "minimum of (two times a smaller number of disks plus the minimum of the remaining disk moves) method.
#2: An observation: if d (# of disks) < p (# of pegs), then you ALWAYS only need 2*d-1 moves. Basically, having more pegs than disks means you can move every disk to its own peg, including the base disk (to the designated ending peg), then move all of the other disks back on to the next bigger disk, which you should have already moved to that ending peg: (d - 1) + 1 + (d - 1) = 2d - 1.
#3: Likewise, if d = p, then m = 2d + 1, since you will have to move whichever disk is on the ending peg (or move another disk, if the ending peg is the only one available to the biggest disk), move the biggie, move the disk you had to move beforehand, and then move all the other disks onto the biggie: (d - 1) + 1(clear off the ending peg) + 1(biggie) + 1(split the double stack up with the starting peg) + (d - 1) = 2d + 1.
Easily one of the best channels on all of youtube. Thank you once again for a very interesting, entertaining, learnful, and inspiring video, professor Burkard! 🙌
I think, because of how common the Tower puzzle is, and how little I've thought about it before, this is one of the most beautiful videos you've done. Despite many years of studying more complex topics, making "simple" problems elegant often gives me the greatest appreciation of mathematics. Thank you as always!
Decided to implement in python before watching. An interesting point I came across was that when recursing, the midpoint and destination swap for subtower move (so the biggest disc can move to the destination unimpeded). As the algorithm recurses down to the base case of 1 (not 0), there are n-1 such midpoint/destination swaps for a tower of size n.
Hence, for towers with an odd number of discs, there are an even number of mid/dst swaps, which all cancel out -> first move should be the first disc on to the intended overall destination.
Vice versa for even number of discs.
For those who don't know: the reason you only saw a still and heard an audio is that only photos from the TV broadcast and a duplicate audio of the telecast are what BBC have in the archives of the first three episodes.
Addendum: there was a proposed sequel to "The Celestial Toymaker" called "Nightmare Fair". Rumour had it that an early draft of the script included the Doctor solving the minimal path problem discussed here for the Trilogic game.
Had not heard about this before :)
Let's gooooooooooooooooooooooooo! :D
Guten Abend Jens :)
Papa Flammy ist hier!
Yaaaaaaaaaaaayyyyyyyyyy
Hello papa
@@Mathologer Ich hoffe du hattest ein schönes Wochenende bis dato :3
While I never faced it, I was considering the programming interview question: "Solve the Tower of Hanoi puzzle using a recursive function."
Here's my problem with this interview question: It doesn't actually *need* a recursive function. I'm of the opinion that if you can craft more supportable code, however less "elegant," it is, you will be doing right by your client.
Here's how I would structure it (using English rules for pseudocode):
Assume N disks (Labeled Disk 1 through Disk N)
Assume 3 rods (Labeled 1, 2, and 3)
Assume all disks are first placed on Rod 1.
All moves follow the rules (The only disk that can ever be moved to either rod is Disk 1. All other exposed disks can only move to the rod not occupied by Disk 1.)
Rule 0: (One time move)
If N is even, move Disk 1 to Rod 2;
Else, move Disk 1 to Rod 3.
LOOP ((N^2)-2)/2 times:
Step 1:
Move the smallest disk that is not Disk 1.
Step 2:
If Disk 1 is not on Disk 2, move Disk 1 to Disk 2;
Else,
If the two non-1 disks are both even or both odd
Move Disk 1 to cover the larger disk
Else,
Move Disk 1 to cover the even disk
That's it. One single one-time move, and a loop that bounces back and forth between a non-decisive move, and a 3-option decision move. I believe this approach would be easier to read and maintain by someone who came along later.
"Elegance" is great if it saves time, and is clear and easy to maintain. But it doesn't have client value in and of itself.
I've paused on 5:04, because my answer is YES. I'm definitely sure, that I will do this exactly in 1023 moves. Course I read a lot about Hanoi puzzle, couple of time programmed it and taught other people to program it on the lectures as exercises on recursion, but only last year I bought my own physical version (with 8 discs), what leads me to so brave assertion. Only after couple of times "physical/manual" solution I really grocked key principles needed to solve this in circumstance similar to Dr. Who's. First one is really mentioned recursion but in not very computer form rather intention: you want to move subtower on n-1 discs on auxiliary peg to be able to move the disc just under subtower (n-th) to destination peg. Second and this is very important for us human to not solve recursion every time: if your subtower (including full tower) consists of odd number of discs you very first move should be on destination (for current subtower move) peg, if your subtower consists of even number of discs you very first move should be on auxiliary peg. Having this principles you will be able to move Hanoi tower as a calming exercise/solitaire as I do. Now I will continue to watch your video to find what is Mathlogger solution.
12:36 And it seems (of course the solution is the same) your algorithm especially in human perception differs from my. Interesting.
Yes mathologer video when i'm bored is the best of the best
It is indeed!
13:27
The doctor has to move the tip counter-clockwise because B in that picture corresponds to the lower right corner of the triangle we had looked at before.
In general, if you have a tower with n disks, you have to move the tip clockwise for odd n and counter-clockwise for even n for the tower to end up at B (according to this picture).
Moving a tower with an even number of disks to B means that you first move a tower with one less disk and thus an odd number of disks to C and since a single-disk tower can be moved with one move only, the tip of a tower with an odd number of disks moves initially to the place where the whole tower will eventually end up.
Therefore, if the tower has an even number of disks, the tip has to move to a different place than the final location.
14:00 For odd number of disks, move clockwise; for even, move counter-clockwise. Easy to see. if one disk (or odd), move directly to ending peg; otherwise, not.
0:56 that puzzle becomes really hard really quick if allow to input not only number disks but sticks as well.
for the record, T. Bousch also has a strong contender in the "best title for a math paper, ever" category : Le Poisson n'a pas d'arête (Annales de l'Institut Henri Poincaré, 1999)
Translate?
@@NoNameAtAll2 google translate tells me this:the Fish has no bones
Every one of your videos is so amazing, Professor Burkard. Best on the internets
Me every time a Mathologer video comes out: *visible excitement*
Once time again a Wonderful Video from Mathologer !!!
Thank you.
The Toymaker is Hanoi'ing me again.
30:07 Minimum number of moves for 9 disk and 4 pegs (I think): 41 (^.^). You explained how to divide the disks into 3 superdisks for 8 disks but not for 9. So, just for fun, I tried every possible division in a very inefficient c++ code. I found that you can solve optimally in 41 moves if you divide the disks into 3 superdisks of 2, 3 and 4 disks (from top to down); also dividing them into 4 superdisks of 1, 1, 3 and 4; 1, 2, 2 and 4; AND 1, 2, 3 and 3. I didn't check if these divisions provide different solutions (Challenge for anybody?), but my guess is that, at least, the 3 and 4 superdisk divisions are different optimal solutions.
Calculation (hopefully) explained: Assume that you got to solve for 8 disks and 4 pegs, and you divide the 8 disks into 3 superdisks of 1, 3 and 4 disks (from top to down, like Mathologer did). Also note that f(n)=2^n-1 is the optimal number of moves to solve n disks and 3 pegs. Then, (hopefully) it's easy to see that the number of moves, following the Mathologer path, is equal to f(1)+f(3)+f(1)+f(4)+f(1)+f(3)+f(1)=4f(1)+2f(3)+f(4)=2^2 f(1)+2^1 f(3)+2^0 f(4). Note that the arguments of the f's add up to the 8 disks and also note the decreasing powers of 2. (hopefully) it's easy to see that, for n disks, 4 pegs and m superdisks of a1, a2, ..., am disks, such that a1+a2+...+am=n, the resulting number of moves is equal to 2^(m-1)f(a1)+2^(m-2)f(a2)+...+2^0 f(am). For the code, I simply apply this formula to every possible division of the 9 disks into superdisks. I cycle through the possible divisions in a very inefficient and lazy way: I go though all possible lists of between 1 and 9 elements with all possible values between 1 and 9, checking if the accumulation of the elements add up to 9. Seeing the formula, it's easy to see that it's not worth it to check superdisk divisions that are not in decreasing amounts of disks, but whatever.
Here's the code for anyone interested:
#include
#include
#include //accumulate algorithm
using namespace std;
int pow(int b,int e){//b to the power of e with e being a non negative integer
int ans=1;
for(int i=0;i
13:55 Answer is pretty simple.
If N is odd, you move it clockwise to end on B, and counterclockwise to end on C
If N is even, you move it clockwise to end on C, qnd counterclockwise to end on B.
It has to do with where disc 2 and disc 3 land, and proving that its to do with odd-even parity, and that it holds for all N
This was so cool that I couldn't stop thinking about it. 30:14 "For my programmer friends..." I wrote a demo you can see at jcalz.github.io/hanoi-demo/ that (I think) implements and animates the Frame-Stewart algorithm. Last time I posted this I think it got sent to the spam graveyard, so hopefully his one will stick.
Awesome work!
I immediately put in 5 pegs with 100 disks, and surprisingly it didn’t break lol
(I set it to a speed of 0.01s so that I could see the whole thing in under a minute)
I also just tried 100 disks with 101 pegs (which is the minimal number of pegs required to minimize disk movement - it only requires 199 moves, which is 2 moves for every disk except the largest one)
Much faster than 5 pegs! But obviously not very interesting lol
for the Q in 14:00:
if mod(n,2) == 0 start by moving the smallest disk to the peg that is not your target, else start by moving it to the target
In the Hanoi puzzle with 3 pegs and n discs, number the discs from 1 to n from the top. Then in the optimal solution an even numbered disc is never placed upon another even disc, nor an odd numbered disc upon another odd disc, but always odd upon even, or vice versa, or onto an empty peg.
True! I think I read this in a Martin Gardner column long ago
I suddenly have an urge to program an animation for something like 35 discs moving using 6 pegs, just so I can sit back and watch 35 discs moving using 6 pegs.
This is the reason I like math - it can be very beautiful sometimes...
------------
Update: (I'm going to keep updating this as I discover new things until I'm done with my programming, at which point I'll post the program here) While trying to make this whole thing more algorithmic, I discovered another way to find the next move of a Tower of Hanoi puzzle of 3 pegs given ONLY the state of the puzzle (so none of that "every second move, move the smallest disc" stuff allowed):
Say your state is ABBAC (as in disc 5 is on A, disc 4 is on B, disc 3 is on B, disc 2 is on A, and disc 1 is on C) and your ultimate goal is to move disk 5 to peg C. Now, change each of these letters to a number in the following way: for odd-numbered discs, change A --> 0, B --> 2, and C --> 1 (mod 3) as our goal will now be to move disc 5 from 0 to 1. For even numbered discs, change A --> 0, B --> 1, and C --> 2 (basically swap the roles of B and C). This changes ABBAC to 01201. Now follow the following procedure:
M5 (the number of times we moved disc 5, mod 3) equals 0, since it started on peg 0 and ended on peg 0 (no change).
Q5 is defined as "whether or not we moved disk 5", and can be 0 or 1. With the largest disc, this is easy; Q5 = M5 = 0.
Now define M4 as the number of times we moved disc 4 (mod 3 - from now on we're working in mod 3), which is going to be 1 (the second digit in 01201 - this is actually the reason I defined this convoluted procedure of converting letters to numbers, so that we could easily see this correlation).
At this point, let's quickly talk about something else. Notice that the order in which we move each of the discs (seen in the animations of 3-peg Hanoi in the video) is an ABACABADABA pattern (or rather, a 121312141213121 pattern). We will use this to our advantage; let's say we chop the string of moves 1213121412131215121312141213121 - which is the solution for 5-disc 3-peg Hanoi - somewhere in the middle, like here:
121312141213121512131 / 2141213121
Note that the number of 4s before the split is always going to be the number of 5s, and possibly one more. Similarly, M3 (going with the notation used earlier) is always M4 + M5 + [either 0 or 1]; M2 = M3 + M4 + M5 + [either 0 or 1], etc. Redefine Q_n to be this [either 0 or 1] value for disc n - note that this doesn't change the value of Q5 - and continue working as follows:
M4 = 1 = M5 + Q4 = 0 + Q4
∴ Q4 = 1
M3 = 2 = M5 + M4 + Q3 = 0 + 1 + Q3
∴ Q3 = 1
M2 = 0 = M5 + M4 + M3 + Q2 = 0 + 1 + 2 + Q2
∴ Q2 = 0
(remember, mod 3...)
M1 = 1 = M5 + M4 + M3 + M2 + Q1 = 0 + 1 + 2 + 0 + Q1
∴ Q1 = 1
Remember, these Mn values are coming from the string of numbers we found earlier (01201).
Now organize these Q values from smallest to largest disc: 10110
Pick the first 0 you find (left to right), which in this case is Q2, which corresponds to disc 2. Move the disc you chose from A-->C-->B if odd (since this is the direction in which we want disc 5 to move), and move the disc from A-->B-->C if even. This means the next move of the puzzle is to move disc 2 from A to B.
...and that's it! Whew, quite long, don't you think? I'm still surprised it's even possible, so I'm not going to complain though... Time to implement this into my code!
It's often used to teach recursion. And last semester our professor used Fibonacci sequence and towers of Hanoi as two examples to show different programming languages. Including postscript, which was quite fascinating
I've been recently working on Tower of Hanoi animations for my channel and in the process discovered some of the stuff mentioned in the video, for example the algorithm to solve Tower of Hanoi without recursion by moving the smallest disk every second turn. I also proved why it works.
Answer to challenge questions:
Direction to move the smallest disk is: if (n is even) then Right else Left
That's because to move (N)-tower in some direction, you first have to move (N-1)-tower in the opposite direction, so the direction to move the smallest disk changes every time and it starts with Left for N=1 disk
The number of turns is (as mentioned in the video) equal to the number of reachable states, which is = 3^n, because:
there are 'n' disks, each disk can be placed in one of 3 towers, so there are 3^n valid states. Each valid state is reachable with a standard recursive algorithm, so there are 3^n reachable states.
Another interesting puzzle for you:
given a number of disks (N) and a number of turns (T), how do you quickly find the state of all disks in the optimal solution of N disks after making T turns?
I had to solve this puzzle while making my Tower of Hanoi animations, so I can instantly preview my animation at any moment in time (instead of re-playing it from the start), which becomes increasingly important with several-hour animations. Check out my channel for these animations: I've already published the shorter ones and longer once, including 10-hour 16-disk solution animation, coming soon:)
There was no Easter egg at the end, but I always watch the entire (always wonderful) video(s). Thank you, Mathologer!
That's great :)
I've played enough (3 peg) Hanoi puzzles in various video games that moving the tower in the minimum moves is easy... I sometimes end up second guessing myself on the 'direction' the tip of the tower has to go... Although seeing the pattern play out, I now get that you only have to determine which direction the base has to move, and then the direction the top piece moves is based on if there are an odd number of pieces (same direction as the bottom), or even (opposite direction of the bottom).
Excellent video, I love the visuals & extending the tower of hanoi puzzle beyond what's typically talked about
By the way, Dr. Who was a great show! Great choice for introducing the Tower of Hanoi puzzle!
So happy to see the video for this month. Wish they were more times then once a month, but am sure it takes a long time to make these, and happy that you make them
Yes, sadly my uni job keeps me insanely busy these days. That and family leaves hardly any time for Mathologer. Anyway, I'll keep trying to put one out every month.... :)
18:16 (shortest solution with extra adjacent-peg rule): it is obvious that we have to visit all the nodes in the graph, and a path traversing x nodes exactly once requires x-1 arcs. So, the question boils down to evaluate the number of nodes in such a graph, that is essentially composed by all the possible valid configurations of disks on pegs. With 1 disk we have 3 valid configurations (the smallest triangle), with 2 disks we have 9 valid configurations (the 2nd-smallest triangle), with 3 disks we have 27 valid configurations (...), etc. Note that when we assign a "set" of disks to a peg, their placement is uniquely determined (since it must comply the no-big-over-small rule) by the total ordering of disk sizes. Then, the total number of configurations is the number of ways to assign n disks to 3 pegs; that is the question "with n available digits, how many numbers can I build that are 3-digits long" and the answer is 3^n. Having 2^n nodes in the graph, having to traverse all of them exactly once, the shortest "adjacent-peg" solution is of length 3^n-1 with 3 pegs; more generally with p pegs the shortest "adjacent-peg" solution is of length p^n-1 by the same reasoning.
I'm currently finding tower of Hanoi a good muse problem for getting my flat in order! (Long overdue tidying) So extra specially well pleased I watched this recently! (I'm picking things up off one surface, and putting them down on another temporarily.. Tower of Hanoi, I've learned (through this video) teaches that it's much less work with more permanent (rather than temporary - eg a table top or 2, rather than balancing pins on the tops of empty beer bottles while waiting to see if enough needless etc will emerge from the mess quantity to warrant a "sewing stuff box"...
Already smashed the like button multiple times before Intro was finished. Such was the enthusiasm to learn.
That's great :)
I feel like this must have some application in cpu register allocation or cache hierarchies. Especially interesting in light of the idea of grouping disks into super disks etc.
True fastest solution; If each rod is a processor register... Just rename the processor registers so that *r0 (rod A)* is now *r2 (rod C)*
To me, it is amazing that the state transition graph is (1) connected and (2) planar. The connectedness I can make sense of. But I can think of no obvious explanation for its being planar.
It’s because there’s only 3 pegs, so you just make a bunch of triangles
But with 4 pegs, you might need tetrahedrons… 🤔
Trying to get from A to B, I think if N is odd, you move the smallest disk clockwise, otherwise, move it counterclockwise. As far as the other disks, I think each move is forced by where the smallest one is.
I didn't even notice that the movie and tv references were gone, nice to see a revival!
Try opening the pod bay doors...
"Oh , I know about this puzzle"
"how tf I never thought about multiple pegs"
I had the Tower of Hanoi on my graphing calculator way back in middle school, and used to 'speedrun' 10 disc solutions when I was bored in math class, so I can actually say with relatively high confidence I could still pull it off without a mistake. There's a nice rhythm to it once you get the hang of it, almost meditative. Interestingly, because it was presented as a straight line of pegs instead of a triangle of them, I never stumbled on the clockwise/counterclockwise solution to figuring out where the top disc goes, another example of how how you frame a problem affects how you solve it.
Instead, my method was to think in terms of a start peg, a storage peg, a goal peg, and partial pyramids. Move the top part of the pyramid to one peg (the target peg if the pyramid has odd number of discs, the storage peg if it has an even number), move the top disc of the bottom part of the pyramid to the other peg, move the top part of the pyramid on top of it, and now you have a bigger top part and a smaller top part. Repeat until there's just one disc on the start peg, move it to the other peg, and then you have a new whole pyramid, and you recurse back to the start, just with the start and the storage peg switched places, and a pyramid one disc shorter.
The tower of Hanoi was the first animation I did on a computer (way back in the stone age :)
18:20 The number of moves is just the number of possible states (3^n) minus 1, since the algorithm visits each state exactly once; and since the initial state requires 0 moves to reach from the initial state. The number of pegs is always 3; so, the number of moves, for n discs, is: (3^n)-1. Tada! 😎
1st question: which way should the smallest disc go first? (there are too many details here, just to be clear)
There are 6 moves in 1 complete cycle of the smallest disc, as there are 3 pegs.
At 1, 2 (mod 6) the smallest disc is on the first peg you go to.
At 3, 4 (mod 6), the smallest disc is on the 2nd peg.
At 5, 0 (mod 6), it returns to the starting peg.
Because 2*2 = 1 (mod 3), 2^n = 1 (mod 3) if n is even and 2^n=2 (mod 3) if n is odd. (induction from 2^1=2)
=> 2^n-1 = 0 (mod 3) if n is even, 2^n-1 = 1 (mod 3) if n is odd.
As 2^n-1 is odd, 2^n-1=3 (mod 6) if n is even, 2^n-1=1 (mod 6) if n is odd.
So if n is odd, make your first move to the target peg but if n is even, make your first move to the other peg.
Couldn’t be happier to see this video and try the challenges!
The classical algorithm is a recursive one and pretty simple. However, there also is a non-recursive solution. Figuring that one out (+ implementing it) makes for a fun afternoon
Hi,
I post my answer before reading the other comments (about where to move the first disc):
- if you have only one disc, you move it to the destination peg,
- if you have two discs, you move the small one to the third peg, not the destination one,
- so the rule is : if the number of discs is odd, you move the first disc to the destination peg, if it is even, you move it to the other peg
About the rule for moving the other discs afterwards (moving the small one clock-wise, every even step, and for the odd steps : do the only move you can), I found it when I was 18, just observing what happens when you apply the recursive algorithm. I successed doing the recursive algorithm up to 4 discs, but very difficult with 5, and impossible for me with more. You don't know where you are any more.
Thank you for this video. See you.
Tower of Hanoi is a super popular interview question, so much so that I bet interviewers have to tweak the question so it's new to interviewees. I imagine asking about more pegs is a frequent extension. Now I feel prepared. Great vid
A simple solution is to add more pegs before you start moving the discs. For 10 discs and 11 pegs the puzzle becomes trivial :)
Shortest solution for 9 discs:
Superdiscs: 2+3+4
Order: 2, 3, 2, 4, 2, 3, 2
Sum: 3+7+3+15+3+7+3 = 41
Love Your Mind, My Friend,,, Keep up the Incredible Work; You have a #1 Fan Here!!!
Amazing!!!
Enjoy your storytelling style to explain the mathematical concepts and algorithms.
Funny and awesome, as always! I've enjoyed it.
I'll think about the puzzle with for and five pegs!
I just recently found a code golf where the challenge was to quine that output a unique program every iteration, without repeat, for however many iterations. I immediately thought of Gray code, and have been absorbed. This is great!
Props for mentioning the Celestial Toymaker... Jeez, I'm old. Remember watching this on the original transmission!
Lucky you.
Variations of Tower of Hanoi with more than one stack of disks are described in U.S. pat. no. 7,566,057. The simplest Multistack T of H (2X4) involves four pegs on the corners of a square with two different colored stacks arranged diagonally to each other. The object is to reverse the positions of the two stacks. The restriction is that each stack can only be moved among its starting and ending pegs and one of the pegs on the other diagonal. Also covered by the patent are a 2X5 variant of the Reve's version of T of H. Both the 2X4 and the 2X5 are the first iterations of their respective series. P.S.: the last puzzles mentioned are in a puzzle museum on one of the U of Indiana campuses.
I'm so glad to see (literally) that your color scheme became more colorblind-friendly!
For the direction of the smallest disk for n disks, check the parity of n. If n is odd, start by moving the disk onto the peg where you want the final disk. If n is even, start by moving it to the other peg. Then continue the small disk movement in the same circular direction. In the Doctor-Toymaker setup, that means that an even n moving to peg B requires moving the smallest disk counterclockwise, while an odd n requires moving the disk clockwise.
I distinctly remember seeing this on our steam driven television the first time round... by then I’d graduated from watching from behind the sofa (for safety reasons...), it had a big impact on me ... I made a version of the game at school and started a craze for playing it that lasted two whole weeks! Nerd heaven.....
Yea I think I could figure it out if I was in the Doctor's shoes, I figured it out when I was, Idk, early in my teens? And it's also mindlessly easy to execute *if* you get the first move right, everything else just falls into place. The Doctor is far smarter than me, and more experienced than I was or even am now
But as always with your videos even if it's a topic I find myself familiar with you manage to surprise with the depth it can be taken to and the adjacent fields we can otherwise analyse it through. One of the channels I get the happiest about seeing longer videolengths
For the second problem, recursion is T(n) = 3T(n-1) +2 as largest disc moves twice and the n-1 disc pile has to be moved from one extreme to another thrice. Solving the recursion gives the promised beautiful answer - 3^n-1
I've always liked the tower of hanoi because it is a nice binary system and there is an intuitive algorithm to follow
The Tower of Hanoi puzzle is probably my favorite puzzle is math. I remember in highschool I tried trying to find an algoritm for the shortest solution for 3 pegs...
but I ended up essentially using brute force, by writing out the solution for up to 5 disks and circling patterns until I found an algorithm that I thought worked.
Took me ~8 hours to notice that numbers of disks with the same parity all had the same moves at the beginning. Also that the first half is always followed by a move from the starting tower to the target tower followed by the first half of moves backwards with the to and from towers swapped and the starting tower and the target towers swapped.
Later I was able to come up with the reasoning for this, which led to the recursive algorithm. Being that in order to solve for n disks, you must solve for n-1 disks, but with the target and extra tower swapped so that the last disk is able to be moved to the target tower. Then you just have to undo what you just did, but with the starting tower and the target tower swapped.
I then programmed this algorithm in Java and made it animate the solution. Probably my favorite programming/math project to date. My first attempt at this took me ~80 hours, but it was my first time designing/programming a GUI. Though my second attempt only took me ~20 hours.
I'm probably not going to watch the entire video because I want to try finding the solution for the n-peg hanoi puzzle myself, hopefully without the brute force this time.
I love the little giggles. Could be a bady in a bond movie
If they ever offer me a role as a mathematical supervillain I'd definitely go for it :)
@@Mathologer you most defo should.an if the role comes along? I assume you know all about percentages 😁
My solutions:
If I want it to be in position B, then I will have to move the tip to C. Therefore the answer is counterclockwise. Using the minimal number of steps, you have to move the tip to C if you want it on B and if you want it on C, then you will have to move the tip to B. The formular was (2^n)-1 for n layers and (2^n+1)-1 for n+1 layers.
4:58. Yes I would be happy to, though when I saw this when originally transmitted I was only 11 and it was beyond me then.
Another BBC programme, Blue Peter, ran a competition in parallel with the initial transmission of this story inviting people to submit solutions and I remember that the winners of the coveted Blue Peter badge submitted their solution on a l-o-n-g strip of paper from a bus ticket roll.
Years later i independently discovered the recursive algorithm. I was at Uni when I first was shown the iterative algorithm in a computer class to demonstrate that recursion is generally time and data hungry. The take away was to only use recursion if we didn't know any iterative way.
And it was only because I pestered the lecturer that I was shown the validity proof.
That's because I know the iterative solution. That's one that is harder to explain why it's valid but easier to do in practice.
Incidentally it is a lot less machine cycles if you track the program on a computer for each algorith. If you get the first move right the rest is automatically correct.
I remember finding formula for the smallest number of moves required for n disks and an algorithm to solve it, when I were 12 years old. Those were great times.
Is there still a video in the works about the unsolvability of the quintic?
Sure, the problem is to find the time. Since COVID my job at uni really got insane and I just don't have enough time to really go for a complex project like this :(
Searching a sorted list only takes log_2 N steps. Yet, maintaining a sorted list can be costly in terms of space/time whilst adding and removing values. Using the concepts of the Tower of Hanoi puzzle, multiple sorted lists can be maintained while amortizing the cost of merging the list over a large time scale and using little additional space. (If one doesn't care about space then a double-linked list has constant time insert/removal.)
I've just seen this video (16/10/2022).
It occurred to me that we can trivially fill in the table (at 33:33) by well over 50% for any number of pegs and disks.
So the left two columns are always 1 and 3 moves. And the top row (P=3) is always 2^N - 1.
Now looking at the middle downward left to right diagonal (where P = N + 1) we have, for any N, the minimum moves M is always just 2N - 1. This is also true for all P > N + 1.
Similarly, if we reduce P by one so P = N then we always need an extra two moves giving M = 2N + 1 for P = N. So I reckon that's a lot of useful minima for any P >= N and for P=3. Well over 50% complete with a set of constraints and boundaries for any N and P. Of course, we could probably fill in the rest of the table by reductive induction from P = N +1. (For this stage we'll need to maintain P > N/2).
My interest in maths came back after my exam .