Towers of Hanoi

This article covers the puzzle game. For the data backup type of the same name, see data backup .

The towers of Hanoi

The towers of Hanoi are a mathematical puzzle and patience game .

construction

The game consists of three sticks of the same size A , B and C , on which several perforated discs are placed, all of different sizes. At the beginning, all discs are on bar A , sorted by size, with the largest disc on the bottom and the smallest on top. The aim of the game is to move the entire stack of discs from A to C.

With each move the top disc of any stick may be placed on one of the other two sticks, provided that there is not already a smaller disc there. Consequently, at any point in time during the game, the discs on each field are sorted according to size.

history

Presumably, the game was in 1883 by the French mathematician Edouard Lucas therefore sometimes - invented Lucas towers (eng. Lucas Tower ) called. He made up the story that Indian monks would have to move a tower made of 64 gold discs in the great temple at Benares , at the center of the world, and if they had succeeded, the end of the world would have come.

Sequences of moves for small towers

The game can be played with any number of discs. For explanation, the slices from the smallest to the largest are denoted by S ₁ to S _n , where n is the number of slices. The statement S ₁ - AC for example, means that the disk S ₁ from the rod A to the rod C is moved.

The trivial case with n  = 1, i.e. with a disk, can be solved in one go. The train is enough:

S ₁ - AC.

The case n  = 2, i.e. with two disks, is also simple. First, the upper small disc to the rod B set, then the lower larger disc to the rod C , and finally the small disc from the bar B to the bar C set. The task is thus solved by the following three moves:

S ₁ - AB | S ₂ - AC | S ₁ - BC.

Solving the problem with three discs

For the case n  = 3, i.e. with three disks, the following preliminary consideration can be made. The largest, that is located below disc according C , must be able to move the two stacks (stacks of two disks) also on B to be moved. To this 2-stack B to move, 1-stack must of about, first to the highest thus, the smallest disk C are moved. Subsequently, the central disc can by B and the smallest disc of C to B to be moved. The result is the sequence of moves:

S ₁ - AC | S ₂ - AB | S ₁ - CB

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

Now the third, bottom pane can be moved to the right. This corresponds to the train:

S ₃ - AC

Finally, the 2 pile must be moved from the middle to the right to solve the task. This works just like the sequence of moves at the beginning, except that staff A with staff B , staff B with staff C and staff C with staff A play reversed roles. So the sequence of moves remains:

S ₁ - BA | S ₂ - BC | S ₁ - AC

execute. So a total of seven moves are required.

Solving the problem with four discs

In general, the stack can for each additional disc with a first slice on B , then the lowermost disc according C of the stack, and then B to C are moved along. For the case n  = 4, i.e. with four discs, the sequence of moves results with the 15 solution steps:

S ₁ - AB | S ₂ - AC | S ₁ - BC | S ₃ - AB | S ₁ - CA | S ₂ - CB | S ₁ - AB

S ₄ - AC

S ₁ - BC | S ₂ - BA | S ₁ - CA | S ₃ - BC | S ₁ - AB | S ₂ - AC | S ₁ - BC

Recursive algorithm

The story of the monks and the move orders for small numbers of discs lead to the solution of the game with a recursive algorithm. Since a computer program to solve the game can be written in just a few lines, Towers of Hanoi is a classic example of this type of problem-solving.

The algorithm essentially consists of a function move that has four parameters. With i the number is referred to shifting discs, with a rod of which is to be moved, with b of the rod which serves as an intermediate destination and c are to be moved, the rod on which the pulleys. To solve the actual problem, move with i  = n, a  =  A , b  =  B and c  =  C is called.

The move function solves a partial problem by dividing it into three simpler problems, provided the tower to be moved has a height of at least 1. Otherwise the move function is inactive. The three sub-problems are carried out sequentially. First of all, the tower, which is one disk smaller, is moved from a to intermediate destination b by calling the function move itself with the appropriate parameters. The bars b and c swap their roles. Then the only remaining disc is moved from a to c . Finally, the tower previously moved to b is moved to its destination c , with a and b swapping roles here .

funktion bewege (Zahl i, Stab a, Stab b, Stab c) {
    falls (i > 0) {
       bewege(i-1, a, c, b);
       verschiebe oberste Scheibe von a nach c;
       bewege(i-1, b, a, c);
    }
}

This is how the function behaves with three discs (the bars have been numbered, left: a, middle: b, right: c; the sequence of movements is exactly as in the picture above):

bewege(3,a,b,c) {
    bewege(2,a,c,b) {
        bewege(1,a,b,c) {
            bewege(0,a,c,b){};
            verschiebe oberste Scheibe von a nach c;
            bewege(0,b,a,c){};
        };
        verschiebe oberste Scheibe von a nach b;
        bewege(1,c,a,b){
            bewege(0,c,b,a){};
            verschiebe oberste Scheibe von c nach b;
            bewege(0,a,c,b){};
        };
    };
    verschiebe oberste Scheibe von a nach c;
    bewege(2,b,a,c){
        bewege(1,b,c,a){
            bewege(0,b,a,c){};
            verschiebe oberste Scheibe von b nach a;
            bewege(0,c,b,a){};
        };
        verschiebe oberste Scheibe von b nach c;
        bewege(1,a,b,c){
            bewege(0,a,c,b){};
            verschiebe oberste Scheibe von a nach c;
            bewege(0,b,a,c){};
        };
    };
};

The correctness of the algorithm is intuitively believable, but formally cannot be proven trivially. Basically, two things need to be shown. On the one hand, the partial solutions must work correctly. On the other hand, it must be shown that this can even be carried out. After all, none of the panes that are not considered in partial solutions must prevent the transport. That this is actually the case follows from the property that the function move only moves the smallest i slices in each partial solution . Both this property and the correctness of the partial solutions can be demonstrated by complete induction .

Iterative algorithm

In 1980, Buneman and Levy described an iterative algorithm that generates the same sequence of moves. In this case, the correctness is not immediately recognizable, but the behavior is understandable without the concept of recursion. It is assumed that rods A , B and C are arranged in a clockwise direction on a circle with an even number of discs, otherwise counterclockwise. The discs are all on bar A at the beginning and on bar C at the end .

As long as there are disks on at least one of the two bars A and B , first the smallest disk ( ) is moved clockwise and then, if possible, a different disk. Notated as pseudocode , the following algorithm results: ${\displaystyle S_{1}}$ ${\displaystyle S_{1}}$

solange (Stab A oder B enthalten Scheiben) {
    Verschiebe  ${\displaystyle S_{1}}$ im Uhrzeigersinn um einen Platz;
    falls (eine von  ${\displaystyle S_{1}}$ verschiedene Scheibe ist verschiebbar)
        Verschiebe eine von  ${\displaystyle S_{1}}$ verschiedene Scheibe;
}

This is how the function behaves with three disks (compare picture above).

In order to synchronize with the picture, it is shifted by two instead of one field clockwise ${\displaystyle S_{1}}$ :

Anfangsposition:
A = 3,2,1 | B = 0,0,0 | C = 0,0,0

Erster Durchlauf:
A = 3,2,0 | B = 0,0,0 | C = 1,0,0 //  ${\displaystyle S_{1}}$ von A nach C
A = 3,0,0 | B = 2,0,0 | C = 1,0,0 //  ${\displaystyle S_{2}}$ von A nach B

Zweiter Durchlauf: 
A = 3,0,0 | B = 2,1,0 | C = 0,0,0 //  ${\displaystyle S_{1}}$ von C nach B
A = 0,0,0 | B = 2,1,0 | C = 3,0,0 //  ${\displaystyle S_{3}}$ von A nach C

Dritter Durchlauf:
A = 1,0,0 | B = 2,0,0 | C = 3,0,0 //  ${\displaystyle S_{1}}$ von B nach A
A = 1,0,0 | B = 0,0,0 | C = 3,2,0 //  ${\displaystyle S_{2}}$ von B nach C

Letzter Durchlauf
A = 0,0,0 | B = 0,0,0 | C = 3,2,1 //  ${\displaystyle S_{1}}$ von A nach C

Endposition:
A = 0,0,0 | B = 0,0,0 | C = 3,2,1

The second move within the loop is always possible and clear, except for the last loop pass. In order to see this, let the rod on which lies with a and of the two remaining rods the one with the smaller disc on top with b , the other with c . Obviously the uppermost disk can be moved from b to c . This is also the only way to move a disc differently from . Because neither the topmost slice of b nor of c can be moved to a , because that's where the smallest slice is. Moving the top disc from c to b is also not possible depending on the designation of the bars. The case that no other target is slidable only occurs when all targets are back on a stick, i.e. the goal has already been reached. ${\displaystyle S_{1}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{1}}$

Optimality of the algorithms

For every number of slices there is only one optimal solution to the problem, i.e. only a shortest sequence of moves. This is run through by both algorithms. In this sense, the algorithms are optimal.

This is easy to see for the recursive algorithm. Before the lowest disc of a (partial) tower can be moved, all the discs above must be moved to the intermediate goal (of course they must land there in an orderly order). Only then can the bottom disc be moved onto the target rod. Because only then is it exposed and only if all of the targets originally above this target are on the intermediate target, none of these smaller targets can block the movement of the lowest target onto the target.

For the optimality of the iterative algorithm it suffices to show that the sequence of moves determined by the recursive algorithm satisfies the conditions of the iterative algorithm. This results from the following consideration: The relocation of a non-empty partial tower begins and ends with a movement of the smallest disc. In the recursive function is thus immediately before and immediately after the displacement of the i th wheel moves the smallest disc. Since every movement of a disc is based on this instruction and the smallest disc is never moved twice in direct succession due to optimality, it is moved in every second move. The cyclic direction in which the two sub-towers are moved in a call to the function is the same for the two recursive calls a – c – b and b – a – c of the function, namely opposite to the direction a – b – c . As a result, the cyclic direction is the  same for all calls with i = 1, that is, the smallest slice is always moved in the same direction. Thus the recursive algorithm creates the same sequence of moves as the iterative one.

The iterative algorithm also leads to the solution if the bars are arranged the wrong way round on the circle. In the event of a wrong arrangement, the discs are moved onto rod B first . Since the termination condition is not fulfilled in this situation, it is then shifted further to C. In this case, the algorithm needs twice as many moves and is therefore not optimal.

The following conditions are obviously necessary for an optimal sequence of moves:

1. A certain game situation may not be reached again.
2. The last moved disc must not be moved again immediately.

But they are not sufficient, as the example shows for three discs with a total of 11 moves:

S ₁ - AB | S ₂ - AC | S ₁ - BC | S ₃ - AB | S ₁ - CB | S ₂ - CA | S ₁ - BA | S ₃ - BC | S ₁ - AB | S ₂ - AC | S ₁ - BC .

The move orders given above for small numbers of targets are optimal, i.e. they correspond exactly to the move orders that are generated by the algorithms.

Properties of optimal train sequences

A whole range of properties can be derived for optimal train sequences. Because of the optimality of the recursive algorithm, this is particularly easy to do based on its mode of operation.

Let n be the number of slices again. The number of moves of the optimal solution is then . This can easily be shown inductively. This is certainly correct for a single disk, because it only has to be moved from A to C , so the optimal sequence of moves, as claimed, consists of one move. For larger numbers of targets, the number of moves is verified by summing the moves for the sub-problems. The number of moves corresponds to twice the minimum number of moves for the tower that is one disc smaller, since it has to be moved twice, plus the one train to move the largest disc. As stated below: ${\displaystyle 2^{n}-1}$

${\displaystyle \left(2^{n-1}-1\right)+1+\left(2^{n-1}-1\right)=2^{n}-1.}$

It is easy to determine how often and with which moves a disc is moved with an optimal sequence of moves. In general, the disc is moved exactly once. It is moved the first time when you move and then again after each move. The smallest disc is moved every other pull, starting with the first pull. The second smallest disc is moved every fourth pull, starting with the second pull. The largest disc is moved once, namely with the middle, i.e. the -th move. The second largest disc is moved twice, namely after the first and third quarter of the move sequence increased by 1, i.e. for moves and . In this way it is possible to determine at each point in the sequence of movements which disc needs to be moved next. ${\displaystyle S_{k}}$ ${\displaystyle 2^{n-k}}$ ${\displaystyle 2^{k-1}}$ ${\displaystyle 2^{k}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle S_{n}}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle S_{n-1}}$ ${\displaystyle 2^{n-2}}$ ${\displaystyle 3\cdot 2^{n-2}}$

Practical unsolvability

Number of discs	Needed time
5	31 seconds
10	17.1 minutes
20th	12 days
30th	34 years
40	348 centuries
60	36.6 billion years
64	585 billion years

As shown in the previous section, with an optimal sequence of moves, moves are required to solve the problem, where n is the number of discs. So there is an exponential growth in the complexity of the problem. This means that a practical implementation of the solution is only possible for small n . The table on the right shows the duration assuming that one pane is shifted per second. ${\displaystyle 2^{n}-1}$

The game tree and the Sierpiński triangle

Play tree to the tower of height 3

Play tree to the tower of height 7, which approaches the Sierpinski triangle .

If you show all allowed moves in a graph , you get the game tree. Each game position is represented by a knot and each move by an edge . The nodes are labeled based on the position of the discs, starting with the position of the largest disc . ${\displaystyle S_{n}}$

The graphic opposite shows the play tree for a tower three height. The corners of the triangle with the positions AAA and CCC in accordance with the start or end position, the corner BBB corresponds to the position with all the discs on the center rod B . The edge color corresponds to that of the moving disk in the animation above: red for the smallest, yellow for the middle and blue for the largest disk . ${\displaystyle S_{3}}$

The first train the optimal solution - referred to above with - AC - that corresponds to the red edge between AAA and AAC and moves the small red disk from A to C . Then the yellow disc is pulled from A to B , changing the position from AAC to ABC . ${\displaystyle S_{1}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

The number of nodes in the graph - i.e. the number of possible game positions - is , because every disc can be on every rod and if there are several discs on the same rod, their arrangement is clearly given due to their size. ${\displaystyle 3^{n}}$

The smallest disc can be moved to two other bars from any playing position. If not all discs are on the same bar, you can also move the next smaller disc on top. From all positions you have three possible moves, except for the starting positions AAA , BBB and CCC , in which only two moves are possible.

So the number of edges in the graph is ${\displaystyle k_{n}}$

${\displaystyle k_{n}\;=\;{\frac {3\cdot 2\,+\,(3^{n}-3)\cdot 3}{2}}\;=\;{\frac {3}{2}}\,(3^{n}-1)}$

The division by two comes from the fact that every edge belongs to two nodes. The entirety of all moves is because you have to distinguish there and back. ${\displaystyle 2k_{n}}$

The recursive structure of the game graph makes it easy to prove that the diameter of the graph is the same . This means that from a given position any other position can be reached with at most trains, and there are positions whose shortest connection includes trains, such as the optimal sequence of moves from the start to the end position. ${\displaystyle 2^{n}-1}$ ${\displaystyle 2^{n}-1}$ ${\displaystyle 2^{n}-1}$

If a tower is raised by a disk, then both the number of nodes and the number of edges of its play tree grow in the order of 3, while the geometric diameter in the chosen illustration grows by a factor of 2. If the game trees are normalized to diameter one, the sequence of graphs normalized in this way tends towards the Sierpinski triangle .

The boundary structure is thus a self-similar fractal with the Hausdorff dimension ${\displaystyle H=\log 3/\log 2=1{,}58496...}$

Web links

• Introduction to Scientific Programming - Page 3, Stack Example: Towers of Hanoi (Lecture at the Technical University of Munich)
• Lernfunk.de - Demonstration of the algorithm (excerpt from the lecture Algorithms at the University of Osnabrück)
• Towers of Hanoi at Wolfram Research - related to various mathematical subjects
• Towers of Hanoi - an algorithm realized with Maple
• Towers of Hanoi - a graphic realization of the algorithm in Html5 canvas

This version was added to the list of articles worth reading on September 30, 2005 .