# 2.7.2: Towers of Hanoi

Another standard example of recursion is the Towers of Hanoi problem. Let n be a pos- itive integer. Imagine a set of n discs of decreasing size, piled up in order of size, with the largest disc on the bottom and the smallest disc on top. The problem is to move this tower of discs to a second pile, following certain rules: Only one disc can be moved at a time, and a disc can only be placed on top of another disc if the disc on top is smaller. While the discs are being moved from the first pile to the second pile, discs can be kept in a third, spare pile. All the discs must at all times be in one of the three piles.

The Towers of Hanoi puzzle was first published by Édouard Lucas in 1883. The puzzle is based on a legend of temple wherein there initially was one pile of discs neatly sorted from largest to smallest. In Lucas’s story, monks have since been continuously moving discs from this pile of 64 discs accord- ing to the rules of the puzzle to again created a sorted stack at the other end of the temple. It is said that when the last disc is placed, the world will end. But on the positive side, even if the monks move one disc every second, it will take approximately 42 times the age of the universe until they are done. And that is assuming they are using the optimal strategy... Source: en.Wikipedia.org/wiki/Tower_of_Hanoi

For example, if there are two discs, the problem can be solved by the following sequence of moves:

 Move disc 1 from pile 1 to pile 3
Move disc 2 from pile 1 to pile 2
Move disc 1 from pile 3 to pile 2


A simple recursive subroutine can be used to write out the list of moves to solve the problem for any value of n. The recursion is based on the observation that for n > 1, the problem can be solved as follows: Move n − 1 discs from pile number 1 to pile number 3 (using pile number 2 as a spare). Then move the largest disc, disc number n, from pile number 1 to pile number 2. Finally, move the n − 1 discs from pile number 3 to pile number 2, putting them on top of the nth disc (using pile number 1 as a spare). In both cases, the problem of moving n − 1 discs is a smaller version of the original problem and so can be done by recursion. Here is the subroutine, written in Java:

void Hanoi(int n, int A, int B, int C) {
// List the moves for moving n discs from
// pile number A to pile number B, using
// pile number C as a spare. Assume n > 0.
if (n == 1) {
System.out.println("Move disc 1 from pile " + A + " to pile " + B);
}
else{
Hanoi(n-1, A, C, B);
System.out.println("Move disc " + n + " from pile " + A + " to pile " + B);
Hanoi(n-1, C, B, A);
}
}


This problem and its fame have led to implementations in a variety of languages, including a language called Brain f*ck. In the Computer Organisation course, you can implement an interpreter for this language and test it on the implementation of the Hanoi algorithm.

We can use induction to prove that this subroutine does in fact solve the Towers of Hanoi problem.

Theorem 3.12.

The sequence of moves printed by the Hanoi subroutine as given above correctly solves the Towers of Hanoi problem for any integer n ≥ 1.

Proof. We prove by induction that whenever n is a positive integer and A,B, and C are the numbers 1, 2, and 3 in some order, the subroutine call Hanoi(n, A, B, C) prints a sequence of moves that will move n discs from pile A to pile B, following all the rules of the Towers of Hanoi problem.

In the base case, n = 1, the subroutine call Hanoi(1, A, B, C) prints out the single step “Move disc 1 from pile A to pile B”, and this move does solve the problem for 1 disc.

Let k be an arbitrary positive integer, and suppose that Hanoi(k, A, B, C) correctly solves the problem of moving the k discs from pile A to pile B using pile C as the spare, whenever A, B, and C are the numbers 1, 2, and 3 in some order. We need to show that Hanoi(k + 1, A, B, C) correctly solves the problem for k + 1 discs. Since k + 1 > 1,Hanoi(k + 1, A, B, C) begins by calling Hanoi(k, A, C, B). By the induction hypothesis, this correctly moves k discs from pile A to pile C. disc number k + 1 is not moved during this process. At that point, pile C contains the k smallest discs and pile A still contains the(k + 1)st disc, which has not yet been moved. So the next move printed by the subroutine,

“Move disc (k + 1) from pile A to pile B”, is legal because pile B is empty. Finally, the subroutine calls Hanoi(k, C, B, A), which, by the induction hypothesis, correctly moves the $$k$$ smallest discs from pile $$C$$ to pile $$B,$$ putting them on top of the $$(k+1)^{\text { st }}$$ disc, which does not move during this process. At that point, all (k + 1) discs are on pile B, so the problem for k + 1 discs has been correctly solved.