PSG COLLEGE OF TECHNOLOGY

DISCRETE STRUCTURES

TOWER OF HANOI

GROUP MEMBERS:
N.Prem(09Z331)
Mohammed Arafath Badushah(09Z303)
N.Prakash(09Z330)
R.Shyamnath(09Z343)
S.Vignesh(09Z351)
N.A.Ashwin(10Z432)
Tower of Hanoi
The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It
consists 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.

Origins
The puzzle was invented by the French mathematician Édouard Lucas in 1883.
There is a legend about a Vietnamese temple which contains a large room with
three time-worn posts in it surrounded by 64 golden disks. The priests of Hanoi,
acting out the command of an ancient prophecy, have been moving these disks, in
accordance with the rules of the puzzle, since that time. The puzzle is therefore
also known as the Tower of Brahma puzzle. According to the legend, when the
last move of the puzzle is completed, the world will end. It is not clear whether
Lucas invented this legend or was inspired by it.
If the legend were true, and if the priests were able to move disks at a rate of one
per second, using the smallest number of moves, it would take them 2 64−1
seconds or roughly 585 billion years;[1] it would take 18,446,744,073,709,551,615
turns to finish.
There are many variations on this legend. For instance, in some tellings, the
temple is a monastery and the priests are monks. The temple or monastery may
be said to be in different parts of the world — including Hanoi, Vietnam, and may
be associated with any religion. In some versions, other elements are introduced,
such as the fact that the tower was created at the beginning of the world, or that
the priests or monks may make only one move per day.
The Flag Tower of Hanoi may have served as the inspiration for the name.

Solution
The puzzle can be played with any number of disks, although many toy versions
have around seven to nine of them. The game seems impossible to many novices,
yet is solvable with a simplealgorithm. The number of moves required to solve a
Tower of Hanoi puzzle is 2n-1, where n is the number of disks.
Iterative solution
The following solution is a simple solution for the toy puzzle.
Alternate moves between the smallest piece and a non-smallest piece. When
moving the smallest piece, always move it in the same direction (to the right if the
starting number of pieces is even, to the left if the starting number of pieces is
odd). If there is no tower in the chosen direction, move the piece to the opposite
end, but then continue to move in the correct direction. For example, if you
started with three pieces, you would move the smallest piece to the opposite
end, then continue in the left direction after that. When the turn is to move the
non-smallest piece, there is only one legal move. Doing this will complete the
puzzle using the least amount of moves to do so.
It should perhaps be noted that this can be rewritten as a strikingly elegant set of
rules:

Simpler statement of iterative solution

For an even number of disks:

 make the legal move between pegs A and B

 make the legal move between pegs A and C
 make the legal move between pegs B and C
 repeat until complete
For an odd number of disks:

 make the legal move between pegs A and C

 make the legal move between pegs A and B
 make the legal move between pegs B and C
 repeat until complete
In each case, a total of 2n-1 moves are made.

Recursive solution
Let call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). To better understand
and appreciate the following solution you should try solving the puzzle for small number of
disks, say, 2,3, and, perhaps, 4. However one solves the problem, sooner or later the bottom
disk will have to be moved from Src to Dst. At this point in time all the remaining disks will have
to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst
these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the
problem appears to be solved if we know how to accomplish the following tasks:

1. Move the top N - 1 disks from Src to Aux (using Dst as an intermediary peg)
2. Move the bottom disk from Src to Dst
3. Move N - 1 disks from Aux to Dst (using Src as an intermediary peg)

Assume there is a function Solve with four arguments - number of disks and three pegs (source,
intermediary and destination - in this order). Then the body of the function might look like

Solve(N, Src, Aux, Dst)

if N is 0
exit
else
Solve(N - 1, Src, Dst, Aux)
Move from Src to Dst
Solve(N - 1, Aux, Src, Dst)

This actually serves as the definition of the function Solve. The function is recursive in that it
calls itself repeatedly with decreasing values of N until a terminating condition (in our case N =
0) has been met. To me the sheer simplicity of the solution is breathtaking. For N = 3 it
translates into

1. Move from Src to Dst

 2. Move from Src to Aux
3. Move from Dst to Aux
4. Move from Src to Dst
5. Move from Aux to Src
6. Move from Aux to Dst
7. Move from Src to Dst

Of course "Move" means moving the topmost disk. For N = 4 we get the following sequence

1. Move from Src to Aux

2. Move from Src to Dst
3. Move from Aux to Dst
4. Move from Src to Aux
5. Move from Dst to Src
6. Move from Dst to Aux
7. Move from Src to Aux
8. Move from Src to Dst
9. Move from Aux to Dst
10. Move from Aux to Src
11. Move from Dst to Src
12. Move from Aux to Dst
13. Move from Src to Aux
14. Move from Src to Dst
15. Move from Aux to Dst

Recurrence relations
Let TN be the minimum number of moves needed to solve the puzzle with N disks. From the
previous section T3 = 7 andT4 = 15. One can easily convince oneself that T2 = 3 and T1 = 1. A
trained mathematician would also note that T0 = 0. Now let us try to derive a general formula.

The recursive solution above involves moving twice (N - 1) disks from one peg to another and
making one additional move in between. It then follows that
  TN ≤ TN-1 + 1 + TN-1 = 2TN-1 + 1

The inequality suggests that it might be possible to move N disks with fewer than 2TN-1 +
1 moves. Which is actually not the case. Indeed, when the time comes to move the bottom
disk, (N - 1) smaller disks will have been moved from Src to Aux in at least TN-1 moves. Since we
are trying to use as few steps as possible, we may assume that that portion of the task took
exactly TN-1 moves. It takes just one move to move the biggest disk from Src to Dst. One then
needs exactly TN-1more steps to finish the task. Therefore the minimum number of moves
needed to solve the puzzle with N disks equalsTN-1 + 1 + TN-1 = 2TN-1 + 1 moves.

In other words,

  TN = 2TN-1 + 1

Thus we can define the quantity TN as

T0 = 0
 
TN = 2TN-1 + 1 for N > 0

We may compute T1 = 2T0 + 1 = 1, T2 = 2T1 + 1= 3, T3 = 2T2 + 1 = 7 and so on sequentially.

The above expression is known as a recurrence relation which, as you might have noticed, is but
a recursive function. TN is defined in terms of only one of its preceding values. Other recurrence
relations may be more complicated, for example,f(N) = 2f(N - 1) + 3f(N - 2). Recurrence relations
appear under various guises in numerous branches of Mathematics and applications.

Returning to the definition of TN, define SN = TN + 1. Then S0 = 1 and SN = TN + 1 = (2TN-1 + 1) + 1 =
2TN-1 + 2 = 2(TN-1 + 1) = 2SN-1. Which is to say that SN could be defined as

S0 = 1
 
SN = 2SN-1 for N > 0

The latter is solved easily in the closed (non-recurrent) form S N=2N. Wherefrom

  TN = 2N - 1 for N ≥ 0.

Applications
The Tower of Hanoi is frequently used in psychological research on problem
solving. There also exists a variant of this task called Tower of London for
neuropsychological diagnosis and treatment of executive functions.
The Tower of Hanoi is also used as Backup rotation scheme when performing
computer data Backups where multiple tapes/media are involved.
As mentioned above, the Tower of Hanoi is popular for teaching recursive
algorithms to beginning programming students. A pictorial version of this puzzle is
programmed into the emacs editor, accessed by typing M-x hanoi. There is also a
sample algorithm written in Prolog.
The Tower of Hanoi is also used as a test by neuropsychologists trying to
evaluate frontal lobe deficits.