The Towers of Hanoi in ML



Given three rods and $n$ disks on the leftmost rod, move the disks onto one of the other rods, subject to the constraints
  1. Only one disk may be moved at one time
  2. Only the top disk on a rod may be removed, and placed onto another rod
  3. Every disk must be placed on top of a larger disk (if it is being placed on top of a disk)

Thinking about the problem recursively, we can easily solve it in ML. To move $n$ disks from peg A to B via C, we have to move the top $n-1$ disks from A to C via B, then the bottom disk to B, then the $n-1$ pegs from C to B via A. We have split the problem into a trivial problem and two smaller ones. Together with the knowledge of how to move a single disk from one peg to another, we can implement the recursive solution in ML 
    datatype hanoiword = Move|disc|from|peg|A|to|B|C;
    
    fun move(0,a,b,c) = []
       |move(x,a,b,c) = move(x-1,a,c,b) @ [(Move,disc,x,from,peg,a,to,peg,b)] @ move(x-1,c,b,a);
where we index the disks from the top. Let's prove that this solves the problem in the fewest number of moves as possible by induction on the disks.

Let $\phi(x,A,B,C)$ be the property that the algorithm moves x pegs from A to B via C in the fewest number of moves possible, for all distinct pegs A, B and C.

Base case, $\phi(1,A,B,C)$. To move a peg from a peg to a non identical peg requires at least one move. The algorithm terminates with a one element list containing one move, so $\phi(1,A,B,C)$ holds for all distinct A, B and C.

Consider $\phi(n,A,B,C)$. Assume $\phi (k,A,B,C)$ holds for $ k = n - 1$.
By definition of the algorithm, to move $n$ disks from A to B via C, we first move $n-1$ disks from A to C via B, then move one disk from A to B, then move the others from C to B via A. By the inductive hypothesis, this is composed of the fewest number of moves in the first and last stages. Assume that this is not done in the fewest number of moves possible. Then one of the three sub-operations described can be done in a fewer number of moves or the operation consists of sub-operations that are not entirely required. But all three sub-operations are done in the fewest number of moves and are all required (consider the case when any one of the three is not done), deduce that the assumption is false and that it is done in the fewest number of moves possible, so $\phi(n,A,B,C)$ holds. The property holds $\forall n \in \mathbb{N}$ by induction.

The number of moves required, $M(n)$, is the solution to $M(n) = 2M(n-1) + 1$ with $M(0) = 0$, $M(n) = 2^{n}-1$