Tower of Hanoi

The Towers of Hanoi is a mathematical puzzle and patience.

Construction

The game consists of three equal-sized bars A, B and C, the number of drilled discs are placed, all different in size. Initially, all disks are on bar A, sorted by size, with the largest and the smallest disk below the top. The aim of the game is to move the entire stack slices from A to C.

Each train the topmost disc of any rod may be placed on one of the other two rods, provided there is not already a smaller disc. Consequently, the discs are at any time of the game sorted on any field by size.

History

Presumably the game was invented in 1883 by the French mathematician Edouard Lucas - therefore also sometimes called Lucas- towers (English Lucas Tower ). He thought to the history of that Indian monks in the great temple at Benares, put in the center of the world, a tower of 64 golden discs would, and, when they had succeeded in the end of the world would come.

In the history of the monks solve the problem as follows: The oldest monk is given the task to move the tower from 64 slices. Since he can not cope with the complex task, it is the second oldest monk the task to put the top 63 slices on an auxiliary space. He ( the elder ) would then bring the great last slice to the destination. Then the second oldest could bring back the 63 slices of auxiliary space to goal.

The second oldest monk of the task also feels unable to cope. He is the third oldest monk commissioned to transport the top 62 discs, on the final place. He himself ( the second oldest ) would then bring the second to last disc in the auxiliary space. Finally, he would again ask the third elders who provide 62 slices of the target field to the auxiliary space. This continues until the 64th monk ( the youngest) to continue, which can move the top of lying smallest disk alone.

Since there are 64 monks in the monastery and all have plenty of time, they can schedule the task in a finite, albeit very long time do.

Headways for small towers

The game can be played with any number of disks. Illustrating the disks of the smallest to the largest referred to as S1 to Sn, where n is the number of slices is. Specifying S1 AC for example, means that the disc S1 is shifted from the rod A to the C wand.

The trivial case n = 1, ie with a slice is soluble in a train. It is sufficient to train S1 -AC.

The case n = 2, that is, with two discs, is also easy. First the top small disc is attached to the rod B, then set the wheel on the lower major rod C, and finally the small disc from the bar B to the bar C. The task is thus achieved by the following three features:

For the case n = 3, ie with three discs, the following preliminary consideration can be made. In order to move the largest, that is located below disc to C, the two stacks ( stacks of two disks ) to be moved about on B. To move these 2 stack to B, the 1- stack must about it, so the top, smallest disc, be first moved to C. Subsequently, the central disc to B and the smallest disc of C to B can be moved. Thus, there is the move order:

This sequence of moves thus corresponds to the case with two discs, but the rods play B and C swapped roles.

Now the third, bottom plate can be shifted to the right. This corresponds to the train:

The end of the stack 2 has to be shifted from the center to the right, to achieve the object. This works the same as the sequence of moves at the beginning, except that A rod with rod B, bar B play with rod C and C rod with rod A reversed roles. It remains the move order:

Perform. In total, seven moves are needed.

In general, for each of the first stack of additional disc of a disc B, then the lowermost disc of the stack and then from B to C to be moved, and C. For the case n = 4, ie, with four discs, so arises the move order with the 15 solution steps:

Recursive algorithm

The story of the monks and the headways for small disk numbers directly lead to a recursive algorithm for the solution of the game. Since a computer program for the solution of the game can be written with a few lines, Tower of Hanoi is a classic example of this type of problem solving.

The algorithm essentially consists of a moving function, having four parameters. With i the number of disks to be moved is indicated, with a rod to be moved from the, with b the bar, which serves as an intermediate target and with c the rod on which the disks are to be moved. To solve the actual problem will move with i = n, a = A, b = B and c = C called.

The function move solves a sub-problem in that it divides this into three simpler problems, unless the tower to be moved at least has a height of 1. Otherwise, the function is inactive move. The three subproblems are executed sequentially. First of a disk smaller tower from a to b the intermediate target is shifted by moving the function itself with the appropriate parameters calls itself. The bars b and c swap doing their roles. Then the only remaining disc is shifted from a to c. At the end of the previously shifted to b tower is moved to its destination c, where here a and b switch roles.

Function move ( number i, bar a, bar b, bar c ) {      if ( i> 0) {         move (i-1, a, c, b);         move top disk from a to c;         move (i-1, b, a, c);      } } Thus, the function behaves in three slices ( the rods were numbered, left: 1, center: 2, right: 3, and the movement is exactly like in the picture above):

Move ( 3,1,2,3 ) {      move ( 2,1,3,2 ) {          move ( 1,1,2,3 ) {              move ( 0,1,3,2 ) {};              move top disk from 1 to 3;              move ( 0,2,1,3 ) {};          };          move top disk from 1 to 2;          move ( 1,3,1,2 ) {              move ( 0,3,2,1 ) {};              displacing top plate 3 of Figure 2;              move ( 0,1,3,2 ) {};          };      };      move top disk from 1 to 3;      move ( 2,2,1,3 ) {          move ( 1,2,3,1 ) {              move ( 0,2,1,3 ) {};              move top disk from 2 to 1;              move ( 0,3,2,1 ) {};          };          displacing top plate from 2 to 3;          move ( 1,1,2,3 ) {              move ( 0,1,3,2 ) {};              move top disk from 1 to 3;              move ( 0,2,1,3 ) {};          };      }; }; The correctness of the algorithm should be intuitively plausible, formal but not trivial provable. Essentially, two things must be shown. Firstly, the partial solutions have to work properly. The other is to show that they can be carried out at all. Finally, it should none of the disks, which will not be considered for partial solutions to prevent the transport. That this is indeed the case follows from the property that the function move at every partial solution still moves only the smallest i discs. Both this property, as well as the correctness of the partial solutions, can be show by induction.

Iterative algorithm

Buneman and Levy 1980 have described an iterative algorithm that generates the same sequence of moves. In this, the correctness is not immediately apparent, but the course of action without the concept of recursion. It is assumed that the bars A, B and C are arranged in straight plate number in a clockwise direction on a circle, or in the counterclockwise direction. The discs are the beginning all on bar A, at the end on rod C.

As long as there is at least one of the two rods A and B slices is only the smallest disc ( ) in the clockwise direction, and then, if possible, a different offset from the disc. Listed as pseudocode so results in the following algorithm:

While ( bar contain A or B slices) {      Move clockwise around a place;      if (one of several disc is movable)          Displacement of a different disk; } Thus the function (see image above) behaves in three slices.

To synchronize with the image is two, instead of a box moved in the clockwise direction:

Initial position: A = 3,2,1 | 0,0,0 = B | C = 0,0,0 First pass: A = 3,2,0 | 0,0,0 = B | C = 1,0,0 / / from A to C A = 3,0,0 | 2,0,0 = B | C = 1,0,0 / / from A to B Second Pass: A = 3,0,0 | 2,1,0 = B | C = 0,0,0 / / from C to B A = 0,0,0 | 2,1,0 = B | C = 3,0,0 / / from A to C Third run: A = 1,0,0 | 2,0,0 = B | C = 3,0,0 / / from B to A A = 1,0,0 | = 0,0,0 B | C = 3,2,0 / / from B to C Last run A = 0,0,0 | 0,0,0 = B | C = 3,2,1 / / from A to C Final position: A = 0,0,0 | 0,0,0 = B | C = 3,2,1 The second train within the loop is to the last time through the loop always possible and unique. To see this, is the rod on which is a and of the two remaining bars those with the smaller obenaufliegenden disc with b denoting other with c. Obviously, the top plate of B to C can be moved. This is also the only way to move a disc different from. Neither the upper slice of b nor c can be moved to a because is there with the smallest disk. Also, a displacement of the top disk from c to b is not possible on the choice of the names of the bars. The case that no other disk is available as sliding, occurs only when all disks are again on a bar, the goal is therefore already achieved.

Optimality of the algorithms

There are any number of disks only for an optimal approach to the problem, thus only a shortest sequence of moves. This is run by two algorithms. In this sense, the algorithms are thus optimal.

For the recursive algorithm, that is easy to view. Before the bottom plate of a (sub - ) tower can be moved, all overlying disks must be moved to the intermediate destination (where they must of course end up in an orderly fashion ). Only then the bottom plate can be moved to the target rod. Only then is this freely and only if all disks originally located on this disc are on the intermediate target, none of these smaller discs can block the movement of the bottom plate to the target.

For the optimality of the iterative algorithm, it is sufficient to show that the particular sequence of moves by the recursive algorithm satisfies the conditions of the iterative algorithm. This arises from the following consideration: The displacement of a non- empty part of the tower starts and ends with a movement of the smallest pulley. Thus, in the recursive function is immediately before and immediately after the displacement of the i-th wheel moves the smallest disc. Since each movement of a disc on this statement is based, and the smallest disk is never twice moved directly behind the other, due to the optimality, it is put into every second train. The cyclic direction in which the two sub- towers are put in a call to the function is for the two recursive calls acb bac and the function is the same, namely the direction opposite abc. As a result, the cyclic direction is the same for all views, where i = 1, that is the smallest disc always moves in the same direction. Thus, the recursive algorithm generates the same sequence of moves such as the iterative.

The iterative algorithm also leads to the solution when the bars are arranged around wrong on the circle. In the case of an incorrect configuration, the disks but first moved to bar B. Since, in this situation, the termination condition is not satisfied, it is then further moved to C. The algorithm requires in this case twice as many turns, then is thus not optimal.

For an optimal sequence of moves following conditions are obviously necessary:

But they are not sufficient, this shows the example of three discs with a total of 11 trains:

The above headways for small disk numbers are optimal, ie, correspond exactly to the move sequences generated by the algorithms.

Properties of optimal move sequences

For optimal move sequences to a whole range of properties can be derived. Because of the optimality of the recursive algorithm, this is possible especially easy by its functioning.

Let n represents the number of slices. The number of moves of the optimal solution is then. This can easily be shown by induction. For a single plate, this is certainly true, because this needs to be moved from A to C, the optimal sequence of moves is thus, as claimed, from a train. For larger slice numbers the number of moves is proved by summing the trains for the sub-problems. The number of trains that is equal to twice the minimum number of moves for a disk of smaller tower, as this needs to be moved twice to move plus the one train the largest disk. As asserted follows:

It can be easily determined, how often and at which trains a disk is moved at an optimal sequence of moves. The general rule is that the disc is moved exactly once. They then moved the train for the first time and again after trains. The smallest disk is moved at every second train, starting with the first train. The second smallest disk is moved in every fourth train, starting with the second train. The largest disc is moved once, in mean, ie the -th train. The second largest disc is moved twice, after the first and third quarters of the sequence of moves increased by 1, ie when the trains and. In this way it is possible to determine at each point of the sequence of moves which disc has to be moved next.

Practical insolubility

As shown in the previous section, are at optimal sequence of moves moves needed to solve the task, where n is the number of disks. There is therefore an exponential growth of the complexity of the problem. For a practical implementation of the solution is possible only for small n. The adjacent table shows the duration assuming that a disk per second is moved.

The game tree and the Sierpiński Triangle

If you all allowed moves in a graph is then you get the game tree. Each board position is represented by a node and each train by an edge. The label of the node is based on the position of the discs, starting from the position of the largest disc.

The graph shows the game tree of a tower of height three. The corners of the triangle with the positions AAA and CCC correspond to the start and end position, the corner BBB corresponds to the position with all wheels on the middle rod B. The color corresponds to the edges of the moving plate in the animation above: red for the smallest, yellow for the middle, and blue for the largest disc.

The first train of the optimal solution - referred to above with -AC - that corresponds to the red edge between AAA and AAC and moved the little red disk from A to C. Then the yellow disc from A to B is drawn and the position by AAC to ABC changed.

The number of nodes in the graph - ie the number of possible game positions - is because each disk can be located on each rod and several slices on the same bar as their arrangement is clearly given because of their size.

From each playing position can be moved from two other rods the smallest disk. Are not all disks on the same staff, you also must still move the next smallest, overhead pulley. Of all the positions so one has three possible moves, except at the Aussgangspositionen AAA, BBB and CCC, in which only two moves are possible.

The number of edges in the graph is therefore

The division by two is because, each edge is one of two nodes. The totality of all trains is because you have to distinguish back and retreat.

Due to the recursive structure of the game graph can be easy to show that the diameter of the graph is the same. That is, from a given position from each other with a maximum position of trains available, and there are positions for which the shortest connection comprises features such as the optimal sequence of moves from the start to the end position.

Increases to a tower to a washer, then grow in both the number of nodes and the number of edges of its game tree in the order of 3, while the geometric diameter grows in the chosen illustration by a factor of 2. Normalizing the game trees on the diameter of one, then seeks the sequence of normalized graph so against the Sierpinski triangle.

The boundary structure is thus a self-similar fractal with Hausdorff dimension