Key to the Tower of Hanoi - Numberphile
video description
I really admire her dedication to the puzzle, though. All the c, b, a stuff is just sort of explanation for a layman. I don't mean to invalidate or dismiss her amazing understanding of the puzzle and its tricks, but this is just a weird video. I'm not sure what I'm learning here.
I imagine you could learn up to so many levels of the hanoi puzzle (within reason) just by rote. It's not easy to do and takes a lot of time-
okay Brady just mentioned rubix cubes and lol. He was thinking just what I was.
I think if you put out a challenge for completing the tower of hanoi with physical blocks of a specific size, you'd have someone doing it in 10 seconds with time to take a couple shots. That's how hardcore people get when they ignore the math.
Date: 2022-04-09
Related videos
Comments and reviews: 9
Sean
The pattern i figured out when i was younger was by looking at the portion of the tower you want to move, determine if the number of rings is odd or even, and decide where the target location of that portion is. If the number is odd, you place the top piece on the target location; even, and its on the non-target location.
Take the 3 piece tower. Odd number, you want to put it on the right side. Top piece goes to the right. What remains is even, so the next piece goes to the middle. The next piece you want to move is the top piece, and your target is on the second piece. Now you can move the third piece, which standing alone, is an odd number. Move it to the right. The remaining portion in middle is even, so piece goes away from target, second piece is odd, goes on the right side, then cap it off.
Its a completely repeatable pattern for any number of rings. If you had even number of rings to start, you'd just move the first piece to the center.
reply
The pattern i figured out when i was younger was by looking at the portion of the tower you want to move, determine if the number of rings is odd or even, and decide where the target location of that portion is. If the number is odd, you place the top piece on the target location; even, and its on the non-target location.
Take the 3 piece tower. Odd number, you want to put it on the right side. Top piece goes to the right. What remains is even, so the next piece goes to the middle. The next piece you want to move is the top piece, and your target is on the second piece. Now you can move the third piece, which standing alone, is an odd number. Move it to the right. The remaining portion in middle is even, so piece goes away from target, second piece is odd, goes on the right side, then cap it off.
Its a completely repeatable pattern for any number of rings. If you had even number of rings to start, you'd just move the first piece to the center.
reply
sharkuc
I've always hated the Tower of Hanoi with a passion. The rules are simple enough, I can follow along well enough when I see someone else do it like in this video. Something about the way my brain works always makes me lose track though and I end up going through one of the suboptimal tracks, sometimes even with a little circular -dangit, I've been here before- track thrown in for good measure. Doesn't help that in the mid-2000s the Tower of Hanoi was the go-to for just about every game that needed some sort of puzzle to unlock a door, I've seen Mass Effect and KoToR mentioned, and I remember those, but I also seem to remember seeing it in a Tomb Raider game. I even avoided watching this video for a couple of days to mentally prepare myself. All that said, hearing it set to music, I hate it a little bit less. Still not my favourite puzzle by any means, but at least my blood doesn't instantly boil any more.
reply
I've always hated the Tower of Hanoi with a passion. The rules are simple enough, I can follow along well enough when I see someone else do it like in this video. Something about the way my brain works always makes me lose track though and I end up going through one of the suboptimal tracks, sometimes even with a little circular -dangit, I've been here before- track thrown in for good measure. Doesn't help that in the mid-2000s the Tower of Hanoi was the go-to for just about every game that needed some sort of puzzle to unlock a door, I've seen Mass Effect and KoToR mentioned, and I remember those, but I also seem to remember seeing it in a Tomb Raider game. I even avoided watching this video for a couple of days to mentally prepare myself. All that said, hearing it set to music, I hate it a little bit less. Still not my favourite puzzle by any means, but at least my blood doesn't instantly boil any more.
reply
Beeples01
There is a simpler pattern. Using the original board with three spikes in a triangle. Starting with the tower on one spike. Give each block a number, starting with the top most block being '1' and numbering the blocks 2, 3, 4, 5, 6 and so on down the tower. The first move is block '1' to another spike. This is either a clockwise or anticlockwise direction. Which ever it is, it sets the moves for all the other blocks. If, for example you moved '1' in a clockwise direction, to the next spike, then all odd numbered blocks will move in a clockwise direction, from then on, when it is their turn to move and all even numbered blocks will move in an anticlockwise direction when it is their turn to move. Opening moves: '1' cw, '2' ccw, '1' cw (onto '2', '3' cw, '1' cw, '2' ccw (onto '3', '1' cw (onto '2' & '3'. '4' ccw', and so on.
reply
There is a simpler pattern. Using the original board with three spikes in a triangle. Starting with the tower on one spike. Give each block a number, starting with the top most block being '1' and numbering the blocks 2, 3, 4, 5, 6 and so on down the tower. The first move is block '1' to another spike. This is either a clockwise or anticlockwise direction. Which ever it is, it sets the moves for all the other blocks. If, for example you moved '1' in a clockwise direction, to the next spike, then all odd numbered blocks will move in a clockwise direction, from then on, when it is their turn to move and all even numbered blocks will move in an anticlockwise direction when it is their turn to move. Opening moves: '1' cw, '2' ccw, '1' cw (onto '2', '3' cw, '1' cw, '2' ccw (onto '3', '1' cw (onto '2' & '3'. '4' ccw', and so on.
reply
artzfreak
When I was in high school (USA, some branch of the military came and did this weird recruitment thing in the gym with like examples from basic training or the recruitment test or something. And they had a large scale Tower of Hanoi, but they had four spikes, not three. I asked the guy why there were four spikes, and he said -because you need four to solve it. - And I was like, -uh, no, you definitely only need three. - Dude would straight up not believe me until I proved it by doing the optimal solve in about 2 minutes (the blocks were very big. I am still baffled to this day why they had this very classic puzzle with just a completely incorrect setup.
reply
When I was in high school (USA, some branch of the military came and did this weird recruitment thing in the gym with like examples from basic training or the recruitment test or something. And they had a large scale Tower of Hanoi, but they had four spikes, not three. I asked the guy why there were four spikes, and he said -because you need four to solve it. - And I was like, -uh, no, you definitely only need three. - Dude would straight up not believe me until I proved it by doing the optimal solve in about 2 minutes (the blocks were very big. I am still baffled to this day why they had this very classic puzzle with just a completely incorrect setup.
reply
Superb17C
I instantly recognized the optimal solve music as -The Ruler Song-, a melody that my friends and I -discovered- in grade school while looking at (American) measuring sticks. Every inch was marked with a long line, every half-inch with a shorter line, every quarter-inch with an even shorter line, and so forth down to the sixteenths of an inch. To play The Ruler Song, simply -read- the ruler from left to right and play a note at each marking: the longer the line, the lower the note. So cool to hear the same tune again after all these years in a new mathematical context that's also related to the powers of two.
reply
I instantly recognized the optimal solve music as -The Ruler Song-, a melody that my friends and I -discovered- in grade school while looking at (American) measuring sticks. Every inch was marked with a long line, every half-inch with a shorter line, every quarter-inch with an even shorter line, and so forth down to the sixteenths of an inch. To play The Ruler Song, simply -read- the ruler from left to right and play a note at each marking: the longer the line, the lower the note. So cool to hear the same tune again after all these years in a new mathematical context that's also related to the powers of two.
reply
Half
I only knew, that there is a definite start and a definite end.
With that, the oddity of the number of discs is important. When the positions are A, B and C, where A is start and C is the end, then the rules of optimal solving goes like this:
When the number of discs is even (2, 4, 6, ) then disc 1 goes A -> B -> C. When the number of discs is odd (1, 3, 5, ) then disc 1 goes A -> C -> B.
Disc 1 has the first move and takes every second move.
On the other turns (an empty position is seen like a very big disc, the smaller disc goes to the bigger disc.
reply
I only knew, that there is a definite start and a definite end.
With that, the oddity of the number of discs is important. When the positions are A, B and C, where A is start and C is the end, then the rules of optimal solving goes like this:
When the number of discs is even (2, 4, 6, ) then disc 1 goes A -> B -> C. When the number of discs is odd (1, 3, 5, ) then disc 1 goes A -> C -> B.
Disc 1 has the first move and takes every second move.
On the other turns (an empty position is seen like a very big disc, the smaller disc goes to the bigger disc.
reply
Arturs
Three stages of me watching this clip
Phase 1: yes, yes, I know, 2-n-1, easily provable (if n rings require f(n) moves, additional n+1th ring requires moving n rings off, move n+1th, move n onto him back or f(n+1)=2-f(n)+1 which reduces to f(n)=2-n-1. Nothing new to see.
Phase 2: An easy algorithm? Just alternate moving the smallest in circles and the only other available move? Seriously? Wow, didn't know this. Great video.
Phase 3: Sierpinski? I am speechless. My mind is blown.
reply
Three stages of me watching this clip
Phase 1: yes, yes, I know, 2-n-1, easily provable (if n rings require f(n) moves, additional n+1th ring requires moving n rings off, move n+1th, move n onto him back or f(n+1)=2-f(n)+1 which reduces to f(n)=2-n-1. Nothing new to see.
Phase 2: An easy algorithm? Just alternate moving the smallest in circles and the only other available move? Seriously? Wow, didn't know this. Great video.
Phase 3: Sierpinski? I am speechless. My mind is blown.
reply
Yevgeniy
This video didn't go into the main conceptual idea of solving the Tower of Hanoi, which is recursion; i. e. the way to solve the tower with N pieces is to solve the tower with N-1 pieces once, then move the largest piece and then solve the tower with N-1 pieces a second time (this time putting it on top of the largest piece. This is also why the number of moves to solve the N tower is equal to 2 - (number of moves to solves the N-1 tower) + 1 (as shown in the video.
reply
This video didn't go into the main conceptual idea of solving the Tower of Hanoi, which is recursion; i. e. the way to solve the tower with N pieces is to solve the tower with N-1 pieces once, then move the largest piece and then solve the tower with N-1 pieces a second time (this time putting it on top of the largest piece. This is also why the number of moves to solve the N tower is equal to 2 - (number of moves to solves the N-1 tower) + 1 (as shown in the video.
reply
debbie
Here's the key. Arrange the the three pegs in a triangle (pull the left and right down a bit) Now move the smallest disk either clockwise or cc to an empty peg. It will now move every other move, same direction (cw or ccw) throughout. Then when the smallest disk stays put, move the smaller of the remaining disks on top one place in the opposite direction that you chose for the smallest disk staring out. This will eventually get your tower moved to another peg.
reply
Here's the key. Arrange the the three pegs in a triangle (pull the left and right down a bit) Now move the smallest disk either clockwise or cc to an empty peg. It will now move every other move, same direction (cw or ccw) throughout. Then when the smallest disk stays put, move the smaller of the remaining disks on top one place in the opposite direction that you chose for the smallest disk staring out. This will eventually get your tower moved to another peg.
reply
Add a review, comment
Other channel videos
