Related Books
Books / Introduction to Recursion and Backtracking / Chapter 7
Recursive Algorithms - Towers of Hanoi
The last problem we will consider is the famous Towers of Hanoi problem.
The Tower of Hanoi puzzle was first published by the French teacher and recreational mathematician Édouard Lucas in 1883, under the pseudonym “N. Claus (de Siam)” (an anagram of “Lucas d’Amiens”) as an actual physical puzzle.
The following year, Henri de Parville described the puzzle with the following remarkable story:
In the great temple at Benares. . . beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.
You are given three pegs, labeled A, B, and C. Each peg can hold n disks. Initially, n disks of different sizes are arranged on peg A in such a way that above any disk are only smaller disks. The largest is therefore at the bottom of the pile and the smallest at the top. The problem is to devise an algorithm that will move all of the disks to peg B moving one disk at a time subject to the following two rules:
- Only the top disk can be moved from its stack; and
- A larger disk may never be on top of a smaller disk.
Figure 1: Towers of Hanoi
This is a problem with no obvious, simple, non-recursive solution, but it does have a very simple recursive solution:
- Ignore the bottom disk and solve the problem for n − 1 disks, moving them to peg C instead of peg B.
- Move the bottom disk from peg A to peg B.
- Solve the problem for moving n − 1 disks from peg C to peg B.
Now all disks will be on peg B in the correct order.
N. Claus (de Siam) pointed out in the pamphlet included with his puzzle, the secret to solving this puzzle is to think recursively. Instead of trying to solve the entire puzzle at once, let’s concentrate on moving just the largest disk. We can’t move it at the beginning, because all the other disks are in the way. So first we have to move those n 1 smaller disks to the spare peg. Once that’s done, we can move the largest disk directly to its destination. Finally, to finish the puzzle, we have to move the n 1 smaller disks from the spare peg to their destination
Figure 2: The Tower of Hanoi algorithm; ignore everything but the bottom disk
If we write towers(count, source, destination, spare) to represent the algorithm that moves count
many disks from source to destination using the spare as needed, subject to the rules above, then the algorithm we just described can be written as follows:
towers(n-1, A, C, B);
towers(1, A, B, C);
towers(n-1, C, B, A);
It is astonishingly simple. The base case is when there is a single disk. Putting this together, we have:
typedef char peg;
void towers(int count, peg source, peg dest, peg spare) {
if (count == 1)
cout << "move the disk from peg" << source << "to peg " << dest << endl;
else {
towers(count - 1, source, spare, dest);
towers(1, source, dest, spare);
towers(count - 1, spare, dest, source);
}
}
This is an example of a recursive algorithm with three recursive calls. In each call the problem size is smaller. The problem size is the number of disks. The recursion stops when the problem size is 1. The function produces, as its output, a sequence of statements showing which disk was moved. Alternatively, we could just store this sequence in an array of strings that could be passed back via a parameter and then printed by the calling code.
What is not clear is how many steps this takes. If we were to measure the steps by how many times a disk is moved from one peg to another, then the interesting question is how many moves this makes when given an initial set of N disks on a peg. We will return to this when we discuss recurrence relations a bit later.