10.2. Tower of Hanoi

This section discusses recursive and dynamic programming ways of solving the Tower of Hanoi problem.

The followings demonstrate the Tower of Hanoi problem:

Abstraction

Let us create the abstract class Hanoi:

public abstract class Hanoi {
    /**
     * @param n            the total number of rings.
     * @param source       the source tower.
     * @param intermediate the intermediate tower.
     * @param destination  the destination tower.
     * @return a list of steps to move all rings in the source tower to the destination tower.
     */
    public abstract List<String> solve(int n, char source, char intermediate, char destination);

    protected String getKey(int n, char source, char destination) {
        return n + ":" + source + "->" + destination;
    }
}

• L9: returns a list of movements to solve the given problem.

  • n: the total number of rings.

  • source: the ID of the source tower.

  • intermediate: the ID of the intermediate tower.

  • destination: the ID of the destination tower.

• L11: returns the string representation of a movement.

Recursion

Let us create the HanoiRecursive class inheriting Hanoi:

public class HanoiRecursive extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination);
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination) {
        if (n == 0) return;
        solve(list, n - 1, source, destination, intermediate);
        list.add(getKey(n, source, destination));
        solve(list, n - 1, intermediate, source, destination);
    }
}

Dynamic Programming

Let us create the HanoiDynamic class inheriting Hanoi:

public class HanoiDynamic extends Hanoi {
    @Override
    public List<String> solve(int n, char source, char intermediate, char destination) {
        List<String> list = new ArrayList<>();
        solve(list, n, source, intermediate, destination, new HashMap<>());
        return list;
    }

    private void solve(List<String> list, int n, char source, char intermediate, char destination, Map<String, int[]> map) {
        if (n == 0) return;
        int fromIndex = list.size();
        int[] sub = map.get(getKey(n - 1, source, intermediate));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, source, destination, intermediate, map);

        String key = getKey(n, source, destination);
        list.add(key);
        sub = map.get(getKey(n - 1, intermediate, destination));

        if (sub != null) addAll(list, sub[0], sub[1]);
        else solve(list, n - 1, intermediate, source, destination, map);

        if (!map.containsKey(key))
            map.put(key, new int[]{fromIndex, list.size()});
    }

    private void addAll(List<String> list, int fromIndex, int toIndex) {
        for (int i = fromIndex; i < toIndex; i++)
            list.add(list.get(i));
    }
}

Benchmark

The followings show performance comparison: