The Towers of Hanoi - Introduction

An ancient ledgend says that in Hanoi there is an elegantly-crafted cosmic puzzle which controls the birth and the death of the world. Initially, the first of the three pegs contains 64 disks with wholes in the middle stacked on it. They all are of different size and are sorted such that the biggest one is at the bottom and the smallest on top. A team of untiring priests works endlessly in shifts, moving only one disk at a time from one peg to another without ever placing a bigger disk on a smaller disk. When they moved the whole tower from the first peg to the last peg, time will end and the world will crumble to dust.

Hanoi is one of the standard recursive problems, as it can be solved very simply in a recursive way.
Assume we want to move n disks from peg A to peg C. So we move n-1 disks from peg A to peg B, move 1 disk from peg A to peg C and move n-1 disks from peg B to peg C. That's it! But wait, how do we move n-1 disks from peg A to peg B? Well, we apply the same principle and move one disk less (n-2 disks) to the spare peg which is now C, then move one disk from A to B and n-2 disks from C to B This algorithm is quite simple and can be implemented in a very few lines in most of the common programming languages. The initial problem is being simplified until there are only two disks (or even one) which can be moved without using recursion. As this algorithm leads to this state, you can be sure that your program terminates after some time.

In discussions between programmers who like recursions and those who don't, Hanoi is often referred to as a good example for applying recursions. Furthermore, many people still believe Hanoi couldn't really be solved in a neat iterative way. As these opinions are not quite acceptable somehow, I will start with a mathematical approach to an iterative Hanoi. Another thing of higher interest is how hanoi with an additional peg would be like. As you will see, the number of moves can be reduced significantly. I will present a really short solution to Hanoi 4Peg and explain in a quick walk-thru how this initially long program can be shortened efficiently. Last but not least I'll have a go on nPeg Hanoi.

For iterative Hanoi I will use a Delphi-implementation. Delphi is an object- and event-oriented programming language based on Pascal and used to be my favourite programming language for years.
The functional language Haskell is rather for research than for real-world programming. However, this makes it a really good choice for implementing Hanoi 4Peg and nPeg.

During my first year studies at Imperial College I came in touch with hanoi, when I was asked to do coursework of 3Peg Hanoi in Haskell and both 3 and 4Peg Hanoi in Java. My Programming Tutor, Susan Eisenbach, gave me a hint, that 3Peg Hanoi can be done easily if the disks are moved in clockwise and anti-clockwise circles from peg to peg. 4Peg Hanoi in Java was quite a long mess and when I heard that it was done in roughly 6 lines in Haskell by Tony Field it fascinated me. Throughout these pages the idea by Mrs Eisenbach and a line of code by Dr. Field are the only pieces of knowledge that I didn't figure out myself. Hope you enjoy reading!