4 ms·

Gerald Sussman covers the Tower of Hanoi problem in the SICP lectures [1]. The thing I find fascinating about this solution is that it doesn't even require the

Gerald Sussman covers the Tower of Hanoi problem in the SICP lectures [1]. The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs - it simply is never optimal to do so anyway. And the solution is so simple, I wonder if you could invent a game by first coming up with a solution and then seeing what it actually solves. [1] https://youtu.be/dlbMuv-jix8?t=47m17s https://youtu.be/dlbMuv-jix8?t=47m17s

jawarner 10y ago
Grant Sanderson has a beautiful video on the Towers of Hanoi problem too [1], part of his animated math project. [1] https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06WINNoBnCR&v=2SUvWfNJSsM https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06...
- clusmore 10y ago
  Wow, fantastic insight. Thanks for sharing.
khedoros1 10y ago
> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs - it simply is never optimal to do so anyway. It seems like without that rule, the game's solution is 2n-1 steps (dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n), rather than 2^n-1 moves.
- clusmore 10y ago
  >dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n In the case where you can place larger disks on top of smaller disks, the sub-problems don't have the same solutions, i.e. In order to move N disks from A to B you first move N-1 disks from A to C, then one disk from A to B, then the N-1 disks back from C to B. But in order to solve the N-1 disks, you don't need to ensure that the largest disk ends up on the bottom -- you just move them all straight to the target. I guess the rule is implicitly tied up in the fact that the sub-problems are solved in the same way as the larger problem.
justinpombrio 10y ago
> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs It had better. If you're allowed to put larger disks on smaller disks, you can solve towers of Hanoi in linear time. Call the rods A, B, and C: the goal is to move the stack from A to C. First flip the stack upside down, one disk at a time, from A to B. Then do that again, from B to C. The stack is now upright on C, after 2n moves. (In contrast, the real problem requires O(2^n) moves.)

jawarner 10y ago

Grant Sanderson has a beautiful video on the Towers of Hanoi problem too [1], part of his animated math project. [1] https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06WINNoBnCR&v=2SUvWfNJSsM https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06...

clusmore 10y ago
Wow, fantastic insight. Thanks for sharing.

khedoros1 10y ago

> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs - it simply is never optimal to do so anyway. It seems like without that rule, the game's solution is 2n-1 steps (dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n), rather than 2^n-1 moves.

clusmore 10y ago
>dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n In the case where you can place larger disks on top of smaller disks, the sub-problems don't have the same solutions, i.e. In order to move N disks from A to B you first move N-1 disks from A to C, then one disk from A to B, then the N-1 disks back from C to B. But in order to solve the N-1 disks, you don't need to ensure that the largest disk ends up on the bottom -- you just move them all straight to the target. I guess the rule is implicitly tied up in the fact that the sub-problems are solved in the same way as the larger problem.

justinpombrio 10y ago

> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs It had better. If you're allowed to put larger disks on smaller disks, you can solve towers of Hanoi in linear time. Call the rods A, B, and C: the goal is to move the stack from A to C. First flip the stack upside down, one disk at a time, from A to B. Then do that again, from B to C. The stack is now upright on C, after 2n moves. (In contrast, the real problem requires O(2^n) moves.)