Skip to content

12.4   Tower of Hanoi

In merge sort and binary tree reconstruction, we divided the original problem into two subproblems, each half its size. The Tower of Hanoi uses a different division strategy.

Question

Given three rods called A, B, and C, initially rod A holds \(n\) disks arranged from smallest at the top to largest at the bottom. Move all \(n\) disks to rod C while preserving their order, as shown in Figure 12-10. The following rules apply.

  1. A disk can only be removed from the top of one rod and placed on top of another.
  2. Only one disk may be moved at a time.
  3. A smaller disk must always be above a larger disk.

Example of the Tower of HanoiExample of the Tower of Hanoi

Figure 12-10   Example of the Tower of Hanoi

Let \(f(i)\) denote a Tower of Hanoi problem of size \(i\). For example, \(f(3)\) means moving \(3\) disks from A to C.

1.   Considering the base cases

For \(f(1)\), with just one disk, simply move it directly from A to C, as shown in Figure 12-11.

Solution for a problem of size 1Solution for a problem of size 1

hanota_f1_step2hanota_f1_step2

Figure 12-11   Solution for a problem of size 1

For \(f(2)\), with two disks, we need to use B because the smaller disk must remain above the larger one, as shown in Figure 12-12.

  1. Move the smaller top disk from A to B.
  2. Move the larger disk from A to C.
  3. Move the smaller disk from B to C.

Solution for a problem of size 2Solution for a problem of size 2

hanota_f2_step2hanota_f2_step2

hanota_f2_step3hanota_f2_step3

hanota_f2_step4hanota_f2_step4

Figure 12-12   Solution for a problem of size 2

We can summarize the solution to \(f(2)\) as moving two disks from A to C using B. Here, C is the destination rod and B is the auxiliary rod.

2.   Dividing the problem

For \(f(3)\), with three disks, the situation is a little more complicated.

Since we know how to solve \(f(1)\) and \(f(2)\), we can use divide and conquer: treat the top two disks on A as a group and follow the steps in Figure 12-13. This moves all three disks from A to C.

  1. Use B as the destination and C as the auxiliary rod to move two disks from A to B.
  2. Move the remaining disk directly from A to C.
  3. Use C as the destination and A as the auxiliary rod to move two disks from B to C.

Solution for a problem of size 3Solution for a problem of size 3

hanota_f3_step2hanota_f3_step2

hanota_f3_step3hanota_f3_step3

hanota_f3_step4hanota_f3_step4

Figure 12-13   Solution for a problem of size 3

In essence, we have divided \(f(3)\) into two \(f(2)\) subproblems and one \(f(1)\) subproblem. Solving these three subproblems in order solves the original problem. This shows that the subproblems are independent and their solutions can be combined.

We can now state the divide-and-conquer strategy for the Tower of Hanoi, illustrated in Figure 12-14: divide \(f(n)\) into two subproblems \(f(n-1)\) and one subproblem \(f(1)\), then solve them in this order.

  1. Move \(n-1\) disks from A to B using C.
  2. Move the remaining \(1\) disk directly from A to C.
  3. Move \(n-1\) disks from B to C using A.

Each of the two \(f(n-1)\) subproblems can be divided recursively in the same way until we reach the smallest subproblem, \(f(1)\). The solution to \(f(1)\) is a single move.

Divide-and-conquer strategy for the Tower of HanoiDivide-and-conquer strategy for the Tower of Hanoi

Figure 12-14   Divide-and-conquer strategy for the Tower of Hanoi

3.   Code implementation

We define a recursive function dfs(i, src, buf, tar) that moves the top \(i\) disks from rod src to destination rod tar using auxiliary rod buf:

hanota.py
def move(src: list[int], tar: list[int]):
    """Move one disk"""
    # Take a disk from the top of src
    pan = src.pop()
    # Place the disk on top of tar
    tar.append(pan)

def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
    """Solve the Tower of Hanoi problem f(i)"""
    # If this subproblem has only one disk to move, move it directly from src to tar
    if i == 1:
        move(src, tar)
        return
    # Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf)
    # Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar)
    # Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar)

def solve_hanota(A: list[int], B: list[int], C: list[int]):
    """Solve the Tower of Hanoi problem"""
    n = len(A)
    # Move the top n disks from A to C using B
    dfs(n, A, B, C)
hanota.cpp
/* Move one disk */
void move(vector<int> &src, vector<int> &tar) {
    // Take a disk from the top of src
    int pan = src.back();
    src.pop_back();
    // Place the disk on top of tar
    tar.push_back(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) {
    // If only one disk remains to be moved from src, move it directly to tar
    if (i == 1) {
        move(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
    int n = A.size();
    // Move the top n disks from A to C using B
    dfs(n, A, B, C);
}
hanota.java
/* Move one disk */
void move(List<Integer> src, List<Integer> tar) {
    // Take a disk from the top of src
    Integer pan = src.remove(src.size() - 1);
    // Place the disk on top of tar
    tar.add(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
void dfs(int i, List<Integer> src, List<Integer> buf, List<Integer> tar) {
    // If only one disk remains to be moved from src, move it directly to tar
    if (i == 1) {
        move(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
void solveHanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    int n = A.size();
    // Move the top n disks from A to C using B
    dfs(n, A, B, C);
}
hanota.cs
/* Move one disk */
void Move(List<int> src, List<int> tar) {
    // Take a disk from the top of src
    int pan = src[^1];
    src.RemoveAt(src.Count - 1);
    // Place the disk on top of tar
    tar.Add(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
void DFS(int i, List<int> src, List<int> buf, List<int> tar) {
    // If only one disk in this subproblem remains on src, move it directly to tar
    if (i == 1) {
        Move(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    DFS(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    Move(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    DFS(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
void SolveHanota(List<int> A, List<int> B, List<int> C) {
    int n = A.Count;
    // Move the top n disks from A to C using B
    DFS(n, A, B, C);
}
hanota.go
/* Move one disk */
func move(src, tar *list.List) {
    // Take a disk from the top of src
    pan := src.Back()
    // Place the disk on top of tar
    tar.PushBack(pan.Value)
    // Remove the disk from the top of src
    src.Remove(pan)
}

/* Solve the Tower of Hanoi problem f(i) */
func dfsHanota(i int, src, buf, tar *list.List) {
    // If only one disk in this subproblem remains on src, move it directly to tar
    if i == 1 {
        move(src, tar)
        return
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfsHanota(i-1, src, tar, buf)
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar)
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfsHanota(i-1, buf, src, tar)
}

/* Solve the Tower of Hanoi problem */
func solveHanota(A, B, C *list.List) {
    n := A.Len()
    // Move the top n disks from A to C using B
    dfsHanota(n, A, B, C)
}
hanota.swift
/* Move one disk */
func move(src: inout [Int], tar: inout [Int]) {
    // Take a disk from the top of src
    let pan = src.popLast()!
    // Place the disk on top of tar
    tar.append(pan)
}

/* Solve the Tower of Hanoi problem f(i) */
func dfs(i: Int, src: inout [Int], buf: inout [Int], tar: inout [Int]) {
    // If only one disk in this subproblem remains on src, move it directly to tar
    if i == 1 {
        move(src: &src, tar: &tar)
        return
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i: i - 1, src: &src, buf: &tar, tar: &buf)
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src: &src, tar: &tar)
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i: i - 1, src: &buf, buf: &src, tar: &tar)
}

/* Solve the Tower of Hanoi problem */
func solveHanota(A: inout [Int], B: inout [Int], C: inout [Int]) {
    let n = A.count
    // The end of each list represents the top of the peg
    // Move the top n disks from A to C using B
    dfs(i: n, src: &A, buf: &B, tar: &C)
}
hanota.js
/* Move one disk */
function move(src, tar) {
    // Take a disk from the top of src
    const pan = src.pop();
    // Place the disk on top of tar
    tar.push(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
function dfs(i, src, buf, tar) {
    // If only one disk remains to be moved from src, move it directly to tar
    if (i === 1) {
        move(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
function solveHanota(A, B, C) {
    const n = A.length;
    // Move the top n disks from A to C using B
    dfs(n, A, B, C);
}
hanota.ts
/* Move one disk */
function move(src: number[], tar: number[]): void {
    // Take a disk from the top of src
    const pan = src.pop();
    // Place the disk on top of tar
    tar.push(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
function dfs(i: number, src: number[], buf: number[], tar: number[]): void {
    // If only one disk remains to be moved from src, move it directly to tar
    if (i === 1) {
        move(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
function solveHanota(A: number[], B: number[], C: number[]): void {
    const n = A.length;
    // Move the top n disks from A to C using B
    dfs(n, A, B, C);
}
hanota.dart
/* Move one disk */
void move(List<int> src, List<int> tar) {
  // Take a disk from the top of src
  int pan = src.removeLast();
  // Place the disk on top of tar
  tar.add(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
void dfs(int i, List<int> src, List<int> buf, List<int> tar) {
  // If only one disk remains to be moved from src, move it directly to tar
  if (i == 1) {
    move(src, tar);
    return;
  }
  // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
  dfs(i - 1, src, tar, buf);
  // Subproblem f(1): move the remaining disk of this subproblem from src to tar
  move(src, tar);
  // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
  dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
void solveHanota(List<int> A, List<int> B, List<int> C) {
  int n = A.length;
  // Move the top n disks from A to C using B
  dfs(n, A, B, C);
}
hanota.rs
/* Move one disk */
fn move_pan(src: &mut Vec<i32>, tar: &mut Vec<i32>) {
    // Take a disk from the top of src
    let pan = src.pop().unwrap();
    // Place the disk on top of tar
    tar.push(pan);
}

/* Solve the Tower of Hanoi problem f(i) */
fn dfs(i: i32, src: &mut Vec<i32>, buf: &mut Vec<i32>, tar: &mut Vec<i32>) {
    // If only one disk remains to be moved from src, move it directly to tar
    if i == 1 {
        move_pan(src, tar);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move_pan(src, tar);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar);
}

/* Solve the Tower of Hanoi problem */
fn solve_hanota(A: &mut Vec<i32>, B: &mut Vec<i32>, C: &mut Vec<i32>) {
    let n = A.len() as i32;
    // Move the top n disks from A to C using B
    dfs(n, A, B, C);
}
hanota.c
/* Move one disk */
void move(int *src, int *srcSize, int *tar, int *tarSize) {
    // Take a disk from the top of src
    int pan = src[*srcSize - 1];
    src[*srcSize - 1] = 0;
    (*srcSize)--;
    // Place the disk on top of tar
    tar[*tarSize] = pan;
    (*tarSize)++;
}

/* Solve the Tower of Hanoi problem f(i) */
void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
    // If only one disk remains to be moved from src, move it directly to tar
    if (i == 1) {
        move(src, srcSize, tar, tarSize);
        return;
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, srcSize, tar, tarSize);
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
}

/* Solve the Tower of Hanoi problem */
void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
    // Move the top n disks from A to C using B
    dfs(*ASize, A, ASize, B, BSize, C, CSize);
}
hanota.kt
/* Move one disk */
fun move(src: MutableList<Int>, tar: MutableList<Int>) {
    // Take a disk from the top of src
    val pan = src.removeAt(src.size - 1)
    // Place the disk on top of tar
    tar.add(pan)
}

/* Solve the Tower of Hanoi problem f(i) */
fun dfs(i: Int, src: MutableList<Int>, buf: MutableList<Int>, tar: MutableList<Int>) {
    // If only one disk in this subproblem remains on src, move it directly to tar
    if (i == 1) {
        move(src, tar)
        return
    }
    // Subproblem f(i-1): move the top i-1 disks from src to buf using tar
    dfs(i - 1, src, tar, buf)
    // Subproblem f(1): move the remaining disk of this subproblem from src to tar
    move(src, tar)
    // Subproblem f(i-1): move the top i-1 disks from buf to tar using src
    dfs(i - 1, buf, src, tar)
}

/* Solve the Tower of Hanoi problem */
fun solveHanota(A: MutableList<Int>, B: MutableList<Int>, C: MutableList<Int>) {
    val n = A.size
    // Move the top n disks from A to C using B
    dfs(n, A, B, C)
}
hanota.rb
### Move one disk ###
def move(src, tar)
  # Take a disk from the top of src
  pan = src.pop
  # Place the disk on top of tar
  tar << pan
end

### Solve the Tower of Hanoi problem f(i) ###
def dfs(i, src, buf, tar)
  # If only one disk remains to be moved from src, move it directly to tar
  if i == 1
    move(src, tar)
    return
  end

  # Subproblem f(i-1): move the top i-1 disks from src to buf using tar
  dfs(i - 1, src, tar, buf)
  # Subproblem f(1): move the remaining disk in the current subproblem from src to tar
  move(src, tar)
  # Subproblem f(i-1): move the top i-1 disks from buf to tar using src
  dfs(i - 1, buf, src, tar)
end

### Solve the Tower of Hanoi problem ###
def solve_hanota(_A, _B, _C)
  n = _A.length
  # Move the top n disks from A to C using B
  dfs(n, _A, _B, _C)
end
Visualize execution

As shown in Figure 12-15, the Tower of Hanoi forms a recursion tree of height \(n\). Each node represents a subproblem and corresponds to a call to dfs(). The time complexity is therefore \(O(2^n)\), and the space complexity is \(O(n)\).

Recursion tree for the Tower of HanoiRecursion tree for the Tower of Hanoi

Figure 12-15   Recursion tree for the Tower of Hanoi

Quote

The Tower of Hanoi comes from an ancient legend. In a temple in ancient India, monks had three tall diamond rods and \(64\) gold disks of different sizes. They continually moved the disks, believing that the world would end when the last disk was placed in its correct position.

Even at one move per second, however, this would take about \(2^{64} \approx 1.84×10^{19}\) seconds, or roughly \(585\) billion years, far longer than current estimates of the age of the universe. If the legend is true, we should have little reason to worry about the end of the world.

Share your insights, questions, or suggestions in the comments