medium

Tower of Hanoi

Find the sequence of moves that solves the Tower of Hanoi puzzle.

1. Define the problem

Tower of Hanoi

You have n disks stacked on rod A in decreasing size (largest at the bottom). Move the entire stack to rod C, using rod B as a helper rod , following the rules: move one disk at a time, only ever the top disk of a rod, and never place a larger disk on a smaller one. Return the sequence of moves as an array of strings like "A→C" . Use recursion : to move n disks from a source rod to a target rod, first move the top n − 1 disks from source to helper, then move the single largest disk from source straight to target, then move those n − 1 disks from helper to target.

Constraints

  • 1 ≤ n ≤ 10

Example

Inputn = 2
Output["A→B", "A→C", "B→C"]

Explanation Move the top disk out of the way to B, move the big disk straight to C, then move the small disk from B onto C.

2. Know the words first

In plain terms

Helper rod
A spare rod used as temporary storage while disks are moved between the source and target rods.
3. Visualize the solution

Move n − 1 disks aside, move the big disk, move them back

Move n − 1 disks aside, move the big disk, move them back
Statushanoi(2, A, C, B)

To move 2 disks from A to C, first move the top 1 disk from A to B (the helper).

What happens in this step

hanoi(2, A, C, B) calls hanoi(1, A, B, C)

count = 2 is not the base case. First recurse: move the top 1 disk out of the way, from source A to helper B (using target C as the spare for that sub-move). This call must return before the big disk can move.
Step 1 of 5

Steps to visualize

  1. hanoi(n, source, target, helper): if n is 0, there is nothing to move — base case, return immediately.
  2. Otherwise, first recurse: move the top n − 1 disks from source to helper, using target as the spare.
  3. Once that returns, move the single remaining disk directly from source to target.
  4. Then recurse again: move those n − 1 disks from helper over to target, using source as the spare.
  5. Each call does its own move sandwiched between two recursive calls — that's why the disk order comes out correct.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Move n − 1 disks aside, move the big disk, move them back
Statushanoi(2, A, C, B)

To move 2 disks from A to C, first move the top 1 disk from A to B (the helper).

What happens in this step

hanoi(2, A, C, B) calls hanoi(1, A, B, C)

count = 2 is not the base case. First recurse: move the top 1 disk out of the way, from source A to helper B (using target C as the spare for that sub-move). This call must return before the big disk can move.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function solveHanoi(n) {
  const moves = [];

  function hanoi(count, source, target, helper) {
    if (count === 0) {
      return; // base case
    }
    hanoi(count - 1, source, helper, target); // recursive case: clear the way
    moves.push(`${source}→${target}`);
    hanoi(count - 1, helper, target, source); // recursive case: bring them back
  }

  hanoi(n, 'A', 'C', 'B');
  return moves;
}
Time
O(2ⁿ)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
n = 2["A→B", "A→C", "B→C"]example from the docstring
n = 0[]base case, no disks to move
n = 1["A→C"]one disk moves straight from source to target
n = 3["A→C","A→B","C→B","A→C","B→A","B→C","A→C"]the classic 7-move solution, several calls deep
n = 415 moves following the same pattern twice, split by one direct move of the largest diskmove count doubles plus one with every extra disk (2ⁿ - 1)

Keep reading