Recursive Algorithm: Towers of Hanoi

The classic problem of the Towers of Hanoi is a mathematical game or puzzle, where you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom, the smallest at the top, thus making a conical shape. 

Objective

The objective of the puzzle is to move the entire stack to another rod, with following constraints:

  1. Only one disk can be moved at a time.
  2. A disk is slid off the top of one tower onto another tower.
  3. A disk cannot be placed on top of a smaller disk.

The problem can be visualized as below:

tower-of-hanoi 

Source: Wikipedia

 

Solution

Like in the above figure, tower A is the source, tower B is the target tower and tower C is the helping tower.

Let's start with the smallest possible case with only one disk.

Case N = 1

1. We can simply move the disk 1 from tower A to B.

Case N = 2

1. Move disk 1 from tower A to C

2. Move disk 2 from tower A to B

3. Move disk 1 from tower C to B

Case N = 3

1. We already know two disks can be moved from one tower to another as shown in Case N = 2, but in this case, let's move it to tower C.

2. Move disk 3 to tower B

3. Move disk 1 and 2 to tower B by just repeating the process in step 1.

And so on for the higher number of disks.

This can be visualized as:

Step 0: Given the initial state

Tower-of-Hanoi

Step 1: Move top (N – 1) disks to helping tower

Step 2: Move the last disk to target tower.

Step 3: Move (N – 1) disks from helping tower to target tower.

 

This approach leads to a natural recursive algorithm which can be outlined as pseudocode below:

function move(n, source, target, buffer):
    if n == 0:
       return

    # move n - 1 disks from source to helping tower, so they are out of the way
    move(n - 1, source, buffer, target)

    # move the nth disk from source to target
    target.append(source.pop())

    # move the n - 1 disks that we left on helping onto target
    move(n - 1, buffer, target, source)

 

Implementation

Here is Java implementation for above pseudocode:

import java.util.Stack;
public class TowerOfHanoi {
    public static void moveDisks(int disks, Stack<Integer> origin, Stack<Integer> target, Stack<Integer> buffer) {
        if (disks <= 0) return;

        // move n - 1 disk from origin to buffer
        moveDisks(disks - 1, origin, buffer, target);

        // move top to target
        moveTopDisk(origin, target);

        // move n - 1 disk from buffer to target
        moveDisks(disks - 1, buffer, target, origin);
    }

    private static void moveTopDisk(Stack<Integer> origin, Stack<Integer> target) {
        target.push(origin.pop());
    }

    public static void main(String[] args) {
        Stack<Integer> origin = new Stack<>();
        Stack<Integer> target = new Stack<>();
        Stack<Integer> buffer = new Stack<>();

        origin.push(4);
        origin.push(3);
        origin.push(2);
        origin.push(1);

        System.out.println(origin);  // [4, 3, 2, 1]

        moveDisks(4, origin, target, buffer);

        System.out.println(target);  // [4, 3, 2, 1]
    }
}

You can see that after moving disks, the target tower has all disks in the order they were in source target.

As always, the source code for example above is available on GitHub.

References:

https://en.wikipedia.org/wiki/Tower_of_Hanoi

https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

http://www.crackingthecodinginterview.com/

Queue ADT Implementation
Memoization: Make Recursive Algorithms Efficient