Tower of Hanoi

Problem

We are given a tower of n disks, initially stacked in decreasing size on one of three pegs: The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.

Solution

The minimal number of moves required to solve a Tower of Hanoi puzzle is \( 2^n-1 \), where n is the number of disks. This is precisely the nth Mersenne number.

recurrence relation

\( T_0=0, T_1=1 \)
\( T_n=2T_{n-1}+1 \)

if we let \( u_n=T_n+1 \), we have
\( u_0=1 \)
\( u_n=2u_{n-1} \), for n>0
\( u_n=2^n \)
hence \( T_n=2^n-1 \)

Java

recurrence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class HanoiTower {

    public static void move(int n, char source, char target, char auxiliary) {
        if (n==1)
            System.out.println("move " + source + " to " + target);
        else {
            // Move n - 1 disks from source to auxiliary, so they are out of the way
            move(n-1,source,auxiliary,target);
            // Move the nth disk from source to target
            System.out.println("move " + source + " to " + target);
            // Move the n - 1 disks that we left on auxiliary onto target
            move(n-1,auxiliary,target,source);
        }
    }

    public static void main(String[] args) {
        move(3, 'A', 'C', 'B');
    }
}

resources