A little bit about the Tower of Hanoi

An analysis of this and a discussion of the (invented) mythology and of the four peg version can be found in the rec.puzzles FAQ look for induction/hanoi.s

The Tower of Hanoi problem has a nice recursive solution.

Working out recursive solutions

To solve such problems ask yourself: "if I had solved the n-1 case could I solve the n case?"

If the answer to this question is positive you proceed under the outrageous assumption that the n-1 case has been solved. Oddly enough this works, so long as there is some base case (often when n is zero or one) which can be treated as a special case.

How to move n rings from pole A to pole C?

If you know how to move n-1 rings from one pole to another then simply move n-1 rings to the spare pole - there is only one ring left on the source pole now, simply move it to the destination, then pile the rest of them from the spare pole onto the destination pole.

For example when n is 4...






 First move three onto the spare pole (worry how to do this later).





 Now move one ring from the source pole to the destination pole.





 Now move three rings from the spare pole to the destination pole (again, we can worry about how to do this later).

We have finished!

More succinctly...

To move n rings from A to C using B as spare: As with most recursive solutions we have to treat some base case specially - here the base case occurs where we have only one ring to move.

How to do it in C

/* Tower of Hanoi - the answer */ /* How to move four rings from pin 1 to pin 3 using pin 2 as spare */ #include <stdio.h> void move(n,A,C,B) int n,A,B,C; /* number to move, source pole, destination pole and spare pole respectively */ { if (n==1){printf("Move from %d to %d.\n",A,C);} else {move(n-1,A,B,C);move(1,A,C,B);move(n-1,B,C,A);} } main() { move(4,1,3,2); }