Tower of Hanoi
Now you can try some brain strechting and training by playing the Tower of Hanoi or Towers of Hanoi, which is a mathematical game/ puzzle. It consists of three pegs, and a number of discs of different sizes which can slide onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape. The object of the game is to move the entire stack to another peg, obeying the following rules:
– Only one disc may be moved at a time.
– No disc may be placed on top of a smaller disc.
Most toy versions of the puzzle have 8 discs. The game seems impossible to many beginners, yet is solvable with a simple algorithm:
Recursive algorithm
1 - Label the pegs A, B, — these labels may move at different steps
2 - Let n be the total number of discs
3 - Number the discs from 1 (smallest) to n (largest)
4 - To move n discs from peg A to peg B:
5 - Move n?1 discs from A to C. This leaves disc #n alone on peg A
6 - Move disc #n from A to B
7 - Move n?1 discs from C to B so they sit on disc #n
The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n?1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.
The Tower of Hanoi is a problem often used brain stretching games, also for beginning programming, in particular as an example of a simple recursive algorithm. It is also an example of an exponential time algorithm — for all but the smallest number of discs, it will take an impractically huge amount of time, even on the fastest computers in the world. There is no way to improve on this, because the minimum number of moves required to solve the puzzle is exponential in the number of discs. A very nice game ideal for brain training.
Using recurrence relations, we can compute the exact number of moves that this solution
requires, which is 2n ? 1, where n is the number of discs. This result is obtained by noting that steps 1 and 3 take Tn ? 1 time and step 2 takes constant time, giving Tn = 2Tn ? 1 + 1.