If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Towers 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?

  • piceratops ultimate style avatar for user Artem Nyzhnyk
    Where does 2^n - 1 come from?
    (15 votes)
    Default Khan Academy avatar avatar for user
    • spunky sam blue style avatar for user Isaac
      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)
  • leafers seedling style avatar for user Alex Sales
    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)?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Varun Patro
    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)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user John Smith
    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)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user otrevor
    In the paragraph on monks, what if there was more than one monk and they used parallel computation?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • spunky sam blue style avatar for user bindaladitya001
    I'm stuck on step 2 in hanoi challenge
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user ifaturotiadeyemi
    In the Solve Hanoi recursively Challenge I am not too sure what is expected in the 4th step . Can anyone help?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • leafers seed style avatar for user William
      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)
  • male robot hal style avatar for user Feraru Silviu Marian
    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)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Bailey Gough
    why would anyone come up with this anyway it's so complicated.
    (3 votes)
    Default Khan Academy avatar avatar for user
  • mr pink orange style avatar for user Trọng Công
    what does the word Hanoi mean, dose it mean the capital of Vietnam?
    (2 votes)
    Default Khan Academy avatar avatar for user