Towers of Hanoi
If you've gone through the tutorial on recursion, then you're ready to see another problem where recursing multiple times really helps. It's called the Towers of Hanoi. You are given a set of three pegs and disks, with each disk a different size. Let's name the pegs A, B, and C, and let's number the disks from 1, the smallest disk, to , the largest disk. At the outset, all disks are on peg A, in order of decreasing size from bottom to top, so that disk is on the bottom and disk 1 is on the top. Here's what the Towers of Hanoi looks like for disks:
Three towers, labeled A, B, and C. Tower A has disks numbered 5, 4, 3, 2, and 1, with disk 5 on bottom and disk 1 on top. Towers B and C have no disks.
The goal is to move all disks from peg A to peg B:
Three towers, labeled A, B, and C. Tower B has disks numbered 5, 4, 3, 2, and 1, with disk 5 on bottom and disk 1 on top. Towers A and C have no disks.
Sounds easy, right? It's not quite so simple, because you have to obey two rules:
- You may move only one disk at a time.
- No disk may ever rest atop a smaller disk. For example, if disk 3 is on a peg, then all disks below disk 3 must have numbers greater than 3.
You might think that this problem is not terribly important. Au contraire! Legend has it that somewhere in Asia (Tibet, Vietnam, India—pick which legend on the Internet you like), monks are solving this problem with a set of 64 disks, and—so the story goes—the monks believe that once they finish moving all 64 disks from peg A to peg B according to the two rules, the world will end. If the monks are correct, should we be panicking in the streets?
First, let's see how to solve the problem recursively. We'll start with a really easy case: one disk, that is, . The case of will be our base case. You can always move disk 1 from peg A to peg B, because you know that any disks below it must be larger. And there's nothing special about pegs A and B. You can move disk 1 from peg B to peg C if you like, or from peg C to peg A, or from any peg to any peg. Solving the Towers of Hanoi problem with one disk is trivial, and it requires moving only the one disk one time.
How about two disks? How do you solve the problem when ? You can do it in three steps. Here's what it looks like at the start:
Three towers, labeled A, B, and C. Tower A has disk 2 on bottom and disk 1 on top. Towers B and C have no disks.
First, move disk 1 from peg A to peg C:
Three towers, labeled A, B, and C. Tower A has disk 2. Tower B has no disks. Tower C has disk 1.
Notice that we're using peg C as a spare peg, a place to put disk 1 so that we can get at disk 2. Now that disk 2—the bottommost disk—is exposed, move it to peg B:
Three towers, labeled A, B, and C. Tower A has no disks. Tower B has disk 2. Tower C has disk 1.
Finally, move disk 1 from peg C to peg B:
Three towers, labeled A, B, and C. Tower A has no disks. Tower B has disk 2 on bottom and disk 1 on top. Tower C has no disks.
This solution takes three steps, and once again there's nothing special about moving the two disks from peg A to peg B. You can move them from peg B to peg C by using peg A as the spare peg: move disk 1 from peg B to peg A, then move disk 2 from peg B to peg C, and finish by moving disk 1 from peg A to peg C. Do you agree that you can move disks 1 and 2 from any peg to any peg in three steps? (Say "yes.")
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?
- how do you this?(14 votes)
- You will need to start at the bottom because you can not put a ring underneath a ring that is already there.(3 votes)
- how can i solve the question without using recursion.(5 votes)
- I would guess just by using if else logic that goes through all possible moves while still complying with the two rules.(4 votes)
- what does this have to do with computer science?(4 votes)
- this is setup for the problem. The computer science part is the algorithms that you can use to solve this problem, and other similar types of problems. Continue on to the next three parts of this section for all the details. The short answer is: an exercise in recursive thinking, and some practice in coding recursively.(5 votes)
- If I used Recursion to solve the tower of Hanoi Problem time complexity is O(2^n) and if i solve this problem without using recursion ,what is the time complecity?(4 votes)
- How can we solve this solution without recursion?(2 votes)
- It is possible to generate a simple rule for which disk to move, given any intermediate state in a solution, and to apply this rule 2^(n+1) - 1 times iteratively.(3 votes)
- Formulate the recurrence and derive the closed form solution for Triple Tower of Hanoi problem. A triple tower of Hanoi is a regular tower of Hanoi with three pegs, but each peg has three equal sized disks. You can move at most one disk at a time, and you can only put one disk on another if the disk you are putting is smaller or equal to the disk you are putting on to. Can any one solve this problem??(2 votes)
- Closed form solution for what ?
If you want the closed form solution for number of moves to solve the Tower of Hanoi problem then check out:
- seems kind of easy, but that's only really when its less algorithm haha(2 votes)
- easy, just move everything to the far-right peg and then put the biggest to smallest in the middle one.(1 vote)
- That wouldn't work because you would be stack the 5 on the 4 on the 3 on the 2 on the 1(2 votes)
- Why is it the goal stated here is to move all the discs to the 2nd tower, when every other resource I've seen on this game states that the goal is to get them to the 3rd tower?(1 vote)
- Moving discs from tower 1 to tower 3, is equivalent to moving discs from tower 1 to tower 2. One could just swap the labels of tower 2 and tower 3 to prove that.
The labels that matter for this problem are:
-current peg (with the discs on it)
-the remaining peg
Thinking in terms of current, target and remaining pegs will help to understand how to approach the problem recursively.(1 vote)
- is it for the 64 disk problem we need 1+2+3+4......+64 steps?(1 vote)