You’ve now been thinking about recursion for a few days, so it’s a good time to introduce one of the classic problems in early-education computer science: the Tower of Hanoi. Now, fair warning. When I learned the solution, about 2 years ago, it took me days of struggle and hours of literally playing with plates from the kitchen to figure it out. I will give the solution, but I cannot stress enough how important it is that you not read it until you too, have played with your own plates and come to it yourself. On a per-line basis, I think this was the code that was most thought-dense; that is, that required the most time thinking per line written, that I have ever written.
The story is the following. You’re a priest in a temple in Hanoi, and there are 3 giant pillars in the courtyard. On one of those disks is some number of increasingly sized disks as you work toward the base: the higher you go, the smaller the disks, and the lower you go, the bigger the disks.
Your task is the following:
- Given where the pile is now, move it all to another (specified) rod in such a way that
- You only move one disk at a time and
- No bigger disk ever is on top of a smaller one and
- Hopefully you get there in as few moves as possible because there’s a really important festival that cannot start until you’ve finished moving the temple’s disks
After factorials and Fibonacci, this is one of the most classic, basic recursive problems out there. Because it’s so basic, there are hundreds, thousands of videos and articles out there explaining the solution (and this is another). Resist the temptation to consult them until after you’ve found the solution yourself.
The solution comes in two parts:
- What pseudocode solves the problem? And
- What sequence of numbers counts the number of steps it takes, as the number of disks changes?
The most important problem-solving skill in the beginning of tackling a problem like Hanoi is knowing how to reduce a problem to something as simple as possible. You are guaranteed to have at least one disk, so what’s the simplest problem? One disk, of course!
All the screenshots here are from Tower of Hanoi | Math Playground. I encourage you to use it (or other games like it; there are plenty online) to work through the solution. But really, if you have them, literal physical dinner plates of various sizes are even better.
Now, the game state is such that there’s one disk on A. I want it to go to B.
I can move it from A to B directly without violating any of the rules, so I will.
So I’ve solved the (trivial) problem of moving one disk, when there is only one disk—just move it.
Recursion always has a base case—a stopping condition to prevent it from going on forever. We’ve just found it. This “move one disk” case will actually be very important at a key time (always at the same time) in the more general solution.
The thing that took me days to figure out was how the Tower problem is recursive. If the tower is n high, wouldn’t you say that moving all but one disk, then moving one disk, would solve it? Surely, right? Yes! This is the key insight into the problem—the “aha!” moment I did not want stolen earlier.
So, generally, get the top (n-1) disks out of the way, deal with the biggest (bottom) disk with the trivial move, and that should be enough, right?
Think about this. The whole pile starts on A and wants to end up on B. So… can we move the top (n-1) from A to B, and then move the big disk from A to B? No! We’d break the rules, because this would mean that the biggest disk would end up on top of the smallest. So we can’t just go A->B in one fell swoop. We need to use C as a go-between.
What we must do is in fact this (to move everyone from A to B):
- Almost the whole pile from A to C.
- The big disk directly from A to B in one move
- The whole pile on C back to B.
But notice how this is recursive. Steps 1 and 3 involve moving whole (slightly-smaller) piles to or from an intermediary rod, which isn’t the initial source or final destination.
We use C as a go-between to get most of the pile out of the way, to allow direct movement from A to B of the biggest disk. But to move most of the pile from A to C, B (the real destination) must have actually been a go-between, for an (n-1)-1 pile, move the biggest disk of the reduced pile, move the (n-1)-1 pile again, etc.
Then, by the same logic, once we’ve gotten to the go-between Pole C, we need to get from there to the real destination Pole B—using the original origin Pole A as the go-between this time.
Every one of these “move the big sub-pile” sub-problems is self-similar to the original problem, until the problem becomes simple enough that the answer is “just move one disk.”
A helpful observation is that you only ever have 3 possible moves: one is correct, one is useless, and one is illegal.
The correct one gets us closer to accomplishing at least a sub-goal (or sub-sub, or sub-sub-sub-sub… depending on how many disks there are). The useless one undoes what we just did; we just wasted a move for no reason, so it will never be in our best interest to take this route if we want to minimize the number of moves. The last option isn’t really even an option. It’s illegal because it puts a bigger disk on top of a smaller one.
Let’s go frame by frame to solve it for 3. Then, seeing this approach, you should in theory, be able to play with any number of disks.
We start all on A, trying to go to C:
Move 1: Disk 1 from A to C
Move 2: Disk 2 to B
Move 3: Disk 1 to B
Move 4: Disk 3 to C
Move 5: Disk 1 to A
Move 6: Disk 2 to C
Move 7: Disk 1 to C
The game on this website actually tells us we were as efficient as we could have hoped to be, with our 7 perfect moves (the modal might make it difficult to see, but, as intended, the whole pile of 3 disks is now on Peg C).
Even the 1-disk case has this 3-part structure, but it’s a little sneakier:
- Move *no* disks from A to B.
- Move 1 disk from A to C.
- Move *no* disks from B to C.
0, then, really is the most trivial of base-cases.
In any case, notice when (and how often) the biggest disk moved. In a 2-disk case, it moves on move 2 of 3; in this case, it moved on move 4 of 7; in a 4-disk case, it would move on move 8 of 15; in a 5-disk case, it would move on move 16 of 31.
We’ve done the hardest part, which is discovering that “move the top n-1 to a go-between; move the biggest disk directly; move the top n-1 to the final destination” is an efficient process. The next part is figuring out the rules for determining when the big disk moves, and how many moves there are, in a general, efficient solution.
Do you see a pattern, first in the move numbers of the big disks? (Other than that they only move once—which is key!).
- The big-disk move number is always even, or 1 in the 1-disk case
- The big-disk move number doubles with each additional disk
- The big disk move number is as close as possible (4/7, 8/15, 16/31, 32/63, etc.—getting even closer with more disks) to ½ of the total number of moves
- If n-1 disks can move in X total, the big disk in the n-disk case, will move on move X+1; outside the trivial 1-disk case, X is always odd, and so X+1 is always even
- If you’ve made it this far, you like computers, so you probably know about powers of two and binary. If you do, you probably recognize the sequence 1, 2, 4, 8, 16, 32, 64, etc.—as more than just “when the big disk moves.” These are the powers of two: start with 1, and for each additional term, double it to get the next one. Related to this sequence is 1, 3, 7, 15, 31, 63, etc.
Notice that both of these sequences play important roles in counting things. The pure power sequence counts when the big disk moves, when there are (power+1) disks: 2^0 is 1, so (power+1) = 1, so when there is 1 disk, the big disk moves on move 1; the big disk moves on move 2 when there are 2 disks (2 is 2^1 and 1+1 is 2 is the number of disks); on move 4 when there are 3 disks (4 is 2^2 and 2+1 is 3 is the number of disks), etc.
And the total number of moves is 2^(disks)-1: when there’s 1 disk, 2^1-1 is 1; when there are 2 disks, 2^2-1 is 3; when there are 3 disks (as we played out), 2^3-1 is 7; etc. For N disks, there’s exactly a one-to-one correspondence between efficient moves in the N-disk case and N-bit binary numbers.
No comments:
Post a Comment