I don't know why but I recently came back to this old, interesting little problem. For those not familiar with the puzzle, here's an excerpt from Wikipedia:
[The Towers of Hanoi puzzle] consist of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.
Here's an image of how the initial configuration looks like with 8 disks (also from Wikipedia):
Also, here's an applet of the puzzle so you can try to solve it yourself:
MazeWorks - Tower of Hanoi. Try with 3, 4 and maybe 5 disks, and see if you can solve it with the fewest number of moves.
You'll notice that, according to that applet, the minimum number of moves for the puzzle with N disks seems to be
2^N-1. The other day it occurred to me that this can be proven by mathematical induction easily, and that the procedure for doing so is actually the recipe for a recursive algorithm to solve the problem. I'll talk about these two items separately.
Proof that it takes 2^N-1 moves to solve the puzzle.We want to prove that a solution to the Towers of Hanoi problem requires 2^N-1 moves, where N>=1 is the number of disks to move. Let's proceed by mathematical induction.
1) Base case: we prove the claim is valid for N=1.If there is one only disk, moving it to the correct peg requires (trivially) a single move. And 2^1 - 1 = 1, which show what we want to prove is true for the base case.
2) Induction Hypothesis: we assume the claim is valid for N=k, where k >= 1 is some number.This assumes that the solution to the k-disk problem takes 2^k - 1 moves. That is, we assume it takes 2^k - 1 moves to transfer k disks from one peg to an empty peg, using a third empty peg as auxiliary. Note that because of the rules, an "empty peg" is equivalent to "a peg containing one or more disks that are all larger than the disks we're moving".
3) Prove the claim holds for (k+1) disks: we must show that if the induction hypothesis is true, then we can prove that the claim is true for the (k+1)-disk problem as well.In other words, we want to show that if it's true that the k-disk problem requires 2^k-1 moves to solve, then the (k+1)-disk problem requires 2^(k+1)-1 moves to solve.
So we want to solve the (k+1)-disk problem. Let's call the peg on which the disks initially reside the S (source) peg, the peg to which we want to transfer all the disks the D (destination) peg, and the third peg the I (intermediary) peg, which we'll use as auxiliary peg during the process. Then, we proceed as follows:
- Move the upper k disks from the S peg to the I peg. This is possible since we assumed it in the induction hypothesis, which also establishes doing so takes 2^k - 1 moves. This leaves the largest disk alone on the S peg.
- Now that it's possible, move the largest disk from the S peg to the D peg. The disk is now in its final position, so we don't have to move it again. This takes 1 move.
- Move the k disks that were on the I peg to the D peg. Again, by induction hypothesis, this takes 2^k - 1 moves. It doesn't matter we're moving the disks to a non-empty peg, since the disk on the D peg is larger than any disk we're moving, and hence doesn't interfere with the task. The S peg is used as auxiliary peg in this process. After this, the problem is solved, for all disks lie on the D peg.
So what was the total move count? In step i), we used 2^k-1 moves, in step ii) a single move, and in step iii) 2^k-1 moves again. The total:
Moves = (2^k-1) + (1) + (2^k-1) = 2*(2^k) + (1-1-1) = 2^(k+1) - 1
And so, we have proved that if it takes 2^k-1 moves to solve the k-disk problem, then it takes 2^(k+1)-1 moves to solve the (k+1)-disk problem. This, together with the base case whose validity we verified in the first step, makes the claim valid for all N. Q.E.D.
OptimalityNote, however, that at first this proof does not guarantee this is the optimal number of moves needed to solve the problem, only that the N-disk problem can be solved with 2^N-1 moves. Luckily, it seems I can justify the optimality of the solution formally.
Consider the following modified proposition, which we'll prove by induction too: "It takes 2^N-1 moves to solve the N-disk problem, and this is the minimum number of moves of any solution". This is trivially true for the base case (N=1).
To prove the induction step, consider the following argument. We want to show that solving the (k+1)-disk problem requires a minimum of 2^(k+1)-1 moves.
But consider that no matter how you solve the problem, at one point you'll need to move the largest disk to the D peg. Since the largest disk cannot be placed on top of any other disk, this means that the remaining k disks must be on the I peg when this happens. There is no other way this could be. So any solution strategy, no matter what is is, must pass through this common state.
Now, by the (modified) induction hypothesis, moving k disks from one peg to another is done
optimally in 2^k-1 moves. So putting the puzzle in the configuration required to move the largest disk to the D peg requires a minimum of 2^k-1 steps. Similarly, after the largest disk is moved to the D peg, transferring the remaining k disks to the D peg also requires a minimum of 2^k-1 steps.
Finally, the middle step, moving the largest disk to the D peg, is trivially optimal, since we're moving a single disk.
With this, we prove that if the solution of the k-disk problem requires a minimum of 2^k-1 moves, then the solution of the (k+1)-disk problem requires 2^(k+1)-1 moves, and that it is also the minimum number of moves.
The uniqueness of the optimal solution is also proved with the same argument, since moving a single disk (both in the base case and in moving the largest disk to the D peg) is both optimal and the unique way to do it.
Solution AlgorithmA nice thing of this proof by induction is that it naturally produces a recursive solution algorithm. Basically, we define a function, let's it call it Solve(n, A, B, C), that moves n disks from peg A to peg C, using peg B as intermediary. The function is defined recursively following the logic of the proof above (Python pseudocode):
def Solve(n, A, B, C):
if (n==1):
A.transferTo(C)
else:
Solve(n-1, A, C, B)
A.transferTo(C)
Solve(n-1, B, A, C) This is almost full Python code; it's only missing the data structure definitions needed to handle the disks and pegs. But it shows the heart of the algorithm. Note how the function calls itself recursively twice: first in a series needed to move the (n-1) disks to the intermediate peg, then in a second series to move the (n-1) disks onto the final peg. In each call, the peg order is changed to reflect which pegs are source, destination and intermediate.
You can get the full Python code
here.
