Tower Of Hanoi

Tower Of Hanoi

Introduction The Tower of Hanoi is a mathematical puzzle invented by E Lucas in1883. It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, 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.

Mathematical Model Here we assume that there are three pages named Source(S), Intermediate(I) and Destination(D). Our aim is to move a tower of n disks from a starting peg S onto a destination peg D, I being the remaining third peg and assuming S≠D. If there is only one disk (or even none at all), the problem is trivial. If n=1, then simply move the disk from peg S to peg D. If n>1, then somewhere along the sequence of moves, the largest disk must be moved from peg S to another peg, preferably to peg D. The only situation that allows this move is when all smaller n-1 disks are on peg I. Hence, first all h-1 smaller disks must go from S to D. Subsequently move the largest disk and finally move the n-1 smaller disks from peg I to peg D. Now the problem is reduced to moving n-1 disks from one peg to another one, first from S to I and subsequently from I to D, but the same method can be used both times by renaming the pegs. In the implementation of Tower of hanoi, the user is prompted to input the number of plates and that integer is stored in a variable n. The following is a procedure for moving a tower of n disks from a peg S onto a peg D, with T being the remaining third peg: •

Step 1: If n>1 then first use this procedure to move the n-1 smaller disks from peg S to peg D.

•

Step 2: Now the largest disk, i.e. disk can be moved from peg S to peg D.

•

Step 3: If n>1 then again use this procedure to move the n-1 smaller disks from peg S to peg D.

Algorithm Hanoi(n: integer; source, intermediate, destination) Begin 1. if (n=1) then a) write: SOURCE  DESTINATION. b) Return. [End of If structure] 1.

Call Hanoi(n-1, source, destination, intermediate);

2.

Write: SOURCE

3.

Call Hanoi(n-1,intermediate, source, destination);



DESTINATION.

4. Return. Source Code Outputs and Testing

Analysis ➢ Time Analysis No. of moves = 2n – 1 Where n is the number of plates. The following table is an observation of time taken by a computer with 2.1GHz(core 2) processing power and an adequate amount of physical memory for solving the Tower of Hanoi problem without graphics. Observatio n No.

No. of plates (n)

No. of moves (m)

Time taken (in secs) (t)

Time taken by single move (ts)

1

1

2

0.0000000

0.000000000

2

5

31

0.0000000

0.000000000

3

8

255

0.0549450

0.000215470

4

9

511

0.1098900

0.000215048

5

10

1,023

0.2197800

0.000214838

6

11

2,047

0.4395600

0.000214733

7

12

4,095

0.8241760

0.000212639

8

13

8,191

1.6483520

0.000201239

9

14

16,383

3.2976703

0.000201286

10

15

32,767

6.6483520

0.000202897

11

16

65,535

13.296703

0.000202894

12

17

131,071

26.593407

0.000202893

13

18

262,143

53.186813

0.000202892

14

19

524,287

106.428574

0.000202996

15

20

1,048,5 75

212.802200

0.000294418





Time taken for a single move by the computer ts is the average of time observed by a single move in all the observations. ts =

0.00278424313

= 0.000214172 seconds Time taken to move 64 disks by computer = (264-1)*ts = (18,446,744,073,709,551,616-1) * 0.000214172 = 18,446,744,073,709,551,615 * 0.000214172 No. of disks 

= 3,950,776,071,754,522.08848778 seconds = 4,572,657,490.566227876015 days =

4,572,657,490.21437602664296365.242199

years

No.12,519,521.30047923631804374280421 of disks  =

years ≈ 12.5 million years

Time taken to move 64 disks at the rate of 1 disk per second = (264-1)*1 = 18,446,744,073,709,551,615 * 1 = 18,446,744,073,709,551,615 seconds = 213,503,982,334,601.29184027days =

213,503,982,334,601.29184027365.242199 years

= 584,554,530,991.0952864465635 years

≈ 584 million years

Graph analysis ➢

This problem is isomorphic to finding a Hamiltonian path on an hypercube.

➢ The problem can be represented by an undirected graph,

the nodes representing distributions of disks and the branches representing moves. For one disk, the graph is a triangle:

The graph for 2 disks is 3 triangles arranged in a larger triangle:

The nodes at the vertices of the outermost triangle represent distributions with all disks on the same peg. For n+1 disks, take the graph of h disks and replace each small triangle with the graph for 2 disks. For 3 disks the graph is:

• call the pegs a, b and c • list disk positions from left to right in order of increasing size The sides of the outermost triangle represent the shortest ways of moving a tower from one peg to another one. The branch in the middle of the sides of the largest triangle represents a move of the largest disk. The branch in the middle of the sides of each next smaller triangle represents a move of each next smaller disk. The sides of the smallest triangles represent moves of the smallest disk. In general, for a puzzle with n disks, there are 3n nodes in the graph; every node has three branches to other nodes, except the three corner nodes, which have two: it is always possible to move the smallest disk to the one of the two other pegs; and it is possible to move one disk between those two pegs except in the situation where all disks are stacked on one peg. The corner nodes represent the three cases where all the disks are stacked on one peg. The diagram for n+1 disks is obtained by taking three copies of the n-disk diagram -- each one representing all the states and moves of the smaller disks for one particular position of the new largest disk -- and joining them at the corners with three new branches, representing the only three opportunities to move the largest disk. The resulting figure thus

has 3n+1 nodes and still has three corners remaining with only two branches. The longest non-repetitive way for three disks can be visualized by erasing the unused branches:

The circular Hamiltonian path for three disks is:

The graphs clearly show that:

• From every arbitrary distribution of disks, there is exactly one shortest way to move all disks onto one of the three pegs. • Between every pair of arbitrary distributions of disks there are one or two different shortest paths. •

From every arbitrary distribution of disks, there are one or two different longest non self-crossing paths to move all disks to one of the three pegs.

•

Between every pair of arbitrary distributions of disks there are one or two different longest non self-crossing paths.

•

Let Nn be the number of non self-crossing paths for moving a tower of n disks from one peg to another one. Then: ○

N1=2

○

Nn+1=(Nn)2+(Nn)3.

○

For example: N8≈1.5456x10795