3 ms·
> 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 ne
by 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.