Main content
Computer science
Course: Computer science > Unit 1
Lesson 7: Towers of HanoiTowers of Hanoi, continued
When you solved the Towers of Hanoi for three disks, you needed to expose the bottom disk, disk 3, so that you could move it from peg A to peg B. In order to expose disk 3, you needed to move disks 1 and 2 from peg A to the spare peg, which is peg C:
Wait a minute—it looks like two disks moved in one step, violating the first rule. But they did not move in one step. You agreed that you can move disks 1 and 2 from any peg to any peg, using three steps. The situation above represents what you have after three steps. (Move disk 1 from peg A to peg B; move disk 2 from peg A to peg C; move disk 1 from peg B to peg C.)
More to the point, by moving disks 1 and 2 from peg A to peg C, you have recursively solved a subproblem: move disks 1 through n, minus, 1 (remember that n, equals, 3) from peg A to peg C. Once you've solved this subproblem, you can move disk 3 from peg A to peg B:
Now, to finish up, you need to recursively solve the subproblem of moving disks 1 through n, minus, 1 from peg C to peg B. Again, you agreed that you can do so in three steps. (Move disk 1 from peg C to peg A; move disk 2 from peg C to peg B; move disk 1 from peg A to peg B.) And you're done:
And—you knew this question is coming—is there anything special about which pegs you moved disks 1 through 3 from and to? You could have moved them from any peg to any peg. For example, from peg B to peg C:
- Recursively solve the subproblem of moving disks 1 and 2 from peg B to the spare peg, peg A. (Move disk 1 from peg B to peg C; move disk 2 from peg B to peg A; move disk 1 from peg C to peg A.)
- Now that disk 3 is exposed on peg B, move to it peg C.
- Recursively solve the subproblem of moving disks 1 and 2 from peg A to peg C. (Move disk 1 from peg A to peg B; move disk 2 from peg A to peg C; move disk 1 from peg B to peg C.)
No matter how you slice it, you can move disks 1 through 3 from any peg to any peg, moving disks seven times. Notice that you move disks three times for each of the two times that you recursively solve the subproblem of moving disks 1 and 2, plus one more move for disk 3.
How about when n, equals, 4? Because you can recursively solve the subproblem of moving disks 1 through 3 from any peg to any peg, you can solve the problem for n, equals, 4:
- Recursively solve the subproblem of moving disks 1 through 3 from peg A to peg C, moving disks seven times.
- Move disk 4 from peg A to peg B.
- Recursively solve the subproblem of moving disks 1 through 3 from peg C to peg B, moving disks seven times.
This solution moves disks 15 times (7 + 1 + 7) and, yes, you can move disks 1 through 4 from any peg to any peg.
At this point, you might have picked up two patterns. First, you can solve the Towers of Hanoi problem recursively. If n, equals, 1, just move disk 1. Otherwise, when n, is greater than or equal to, 2, solve the problem in three steps:
- Recursively solve the subproblem of moving disks 1 through n, minus, 1 from whichever peg they start on to the spare peg.
- Move disk n from the peg it starts on to the peg it's supposed to end up on.
- Recursively solve the subproblem of moving disks 1 through n, minus, 1 from the spare peg to the peg they're supposed to end up on.
Second, solving a problem for n disks requires 2, start superscript, n, end superscript, minus, 1 moves. We've seen that it's true for:
- n, equals, 1 (2, start superscript, 1, end superscript, minus, 1, equals, 1, only one move needed)
- n, equals, 2 (2, squared, minus, 1, equals, 3, three moves needed)
- n, equals, 3 (2, cubed, minus, 1, equals, 7, seven moves needed)
- n, equals, 4 (2, start superscript, 4, end superscript, minus, 1, equals, 15, 15 moves need).
If you can solve a problem for n, minus, 1 disks in 2, start superscript, n, minus, 1, end superscript, minus, 1 moves, then you can solve a problem for n disks in 2, start superscript, n, end superscript, minus, 1 moves. You need:
- 2, start superscript, n, minus, 1, end superscript, minus, 1 moves to recursively solve the first subproblem of moving disks 1 through n, minus, 1
- 1 move to move disk n
- 2, start superscript, n, minus, 1, end superscript, minus, 1 moves (again) to recursively solve the second subproblem of moving disks 1 through n, minus, 1
If you add up the moves, you get 2, start superscript, n, end superscript, minus, 1.
Back to the monks. They're using n, equals, 64 disks, and so they will need to move a disk 2, start superscript, 64, end superscript, minus, 1 times. These monks are nimble and strong. They can move one disk every second, night and day.
How long is 2, start superscript, 64, end superscript, minus, 1 seconds? Using the rough estimate of 365.25 days per year, that comes to 584,542,046,090.6263 years. That's 584+ billion years. The sun has only about another five to seven billion years left before it goes all supernova on us. So, yes, the world will end, but no matter how tenacious the monks may be, it will happen long before they can get all 64 disks onto peg B.
Wondering how else we can use this algorithm, besides predicting the end of the world? Wikipedia lists several interesting applications.
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
- Where does
2^n - 1
come from?(16 votes)- It's just a pattern:
- For 2 disks you need 3 steps
- For 3 disks you need 7 steps
-For 4 disk you need 15 steps
Suppose you have the next sequence: 2, 4, 8, 16, 32, ... This sequence is called "Geometric progression" because each term in the sequence is 2 times the previous term.
Therefore we can write the sequence as follows: 2 * 2⁰ , 2 * 2¹ , 2 * 2² , ...
In general you can write the sequence as: 1 * 2^(n-1). So if you want the first element n = 1
you get 1 * 2^(1-1) = 1 * 2⁰ = 2 which is the first element.
The sequence that the Towers of Hanoi follow is 3, 7, 15, 31, ... And as you can see it follows a pattern similar to 2*2^(n-1) but you have to substract one unit, which leads to the expression of your question.(29 votes)
- OK, I've completed the challenge by I want to understand HOW the 3 main methods work: moveDisk(), getSparePeg(), isSolved(). There seems to be a lot going on in the hanoi library and it's a bit hard to follow. Is there link to a resource or a simplified version that shows/explains only the 3 main methods and how they work with the rest of the solution?
Also, should fromPeg/sparePeg/toPeg always be represented by a string data types like "A" or "B"? Would it be much harder to have the pegs represented by other Object data structures like Arrays or Stacks (e.g. var arrayA, arrayB, arrayC)?(6 votes) - how do you do the first part of the challenge?
my base case is like this:
if (numDisks === 0) {
hanoi.moveDisk(fromPeg, toPeg);
}
but i can't get it to run. how do you do it?(5 votes)- If you have 0 disks you have nothing left to do. Just return.(12 votes)
- So.... I "finished" the Challenge: Solve Hanoi recursively. Was something suppose to happen at the end? or was the function, that I was guided to, make suppose to display something or do anything?
I feel like all I did was make the gofer with sunglasses happy. It doesn't feel like I accomplished anything...(7 votes)- You should indeed see an animation, displaying every single step of solving the puzzle. Try to restart or change the browser.(3 votes)
- In the paragraph on monks, what if there was more than one monk and they used parallel computation?(5 votes)
- You can only move one disk at a time so it wouldn't be very helpful to have more than one monk.
It's not really a problem that lends itself to parallel computation. Problems which you can divide into subproblems that are independent of each other are good candidates for parallelization. Problems which have subproblems that remain dependent on each other are not good candidates for parallelization.(3 votes)
- I'm stuck on step 2 in hanoi challenge(2 votes)
- You need to make a recursive call to solveHanoi which has 3 parameters
Ask yourself "How many disks do I need to move ?"
-That should be what you use as the first parameter
Ask yourself "Which peg do I need to move the disks from ?"
-That should be what you use as the second parameter
Ask yourself "Which peg do I need to move the disks to ?"
-That should be what you use as the third parameter(5 votes)
- In the Solve Hanoi recursively Challenge I am not too sure what is expected in the 4th step . Can anyone help?(2 votes)
- In the previous steps, you moved all of the disks except the largest one onto the "spare" peg. Then you moved the largest disk onto the target peg. In the fourth step, you must move all of the disks on the "spare" peg on top of the largest disk on the target peg.(3 votes)
- I finished the challenge but I don't fully understand the code, can someone please explain what the code does exactly ?
I mean, it calls for solveHano with parameter numDisks-1, so, starting with numDisks 5
first time it's being called with 4, then with 3, then 2, then with 1, then with 0, when it's zero the whole function returns true, and the next piece of code is called, hanoi.moveDisk from peg A to peg B by the logic of alternating toPeg and sparePeg.
But then what ? I moved A to B, how does the code move from B to C now ?(3 votes) - why would anyone come up with this anyway it's so complicated.(3 votes)
- what does the word Hanoi mean, dose it mean the capital of Vietnam?(2 votes)