Now we can see that we have moved the tower of size 2 to the peg AUX, but the target had been peg TARGET. Now, we have to move the smallest disk again, because we don't want to move the largest disk back to SOURCE again. So the only move which makes sense is moving the other disk, i.e. Now there are two choices: We can move this disk again, either back to the SOURCE peg, which obviously doesn't make sense, or we could move it to AUX, which doesn't make sense either, because we could have moved there as our first step.

So let's start by moving the smallest disk from SOURCE to TARGET.

There is a general rule for moving a tower of size n (n > 1) from the peg S to the peg T: The last three moves move the tower consisting of D2D1 from peg A to T to place them on top of D3. Now we can move D3 to T, where it is finally positioned. We can see that we move in three moves the tower of size 2 (the disks D1 and D2) to A. Let's number the disks as D1 (smallest), D2 and D3 (largest) and name the pegs as S (SOURCE peg), A (AUX), T (TARGET). If your first step consists of moving the smallest disk to AUX, you will not be capable of finishing the task with less than 9 moves. We know from our formula that the minimal number of moves necessary to move a tower of size 3 from the SOURCE peg to the target peg is 7 (23 - 1) You can see in the solution, which we present in our image that the first disk has to be moved from the peg SOURCE to the peg TARGET. We have seen in the cases n=1 and n=2 that it depends on the first move, if we will be able to successfully and with the minimal number of moves solve the riddle. There are two possibilities to move the first disk, the disk on top of the stack of SOURCE: We can move this disk either to TARGET or to AUX.

Let's look now at a tower with size 2, i.e. The solution for a tower with just one disk is straightforward: We will move the one disk on the SOURCE tower to the TARGET tower and we are finished. Before we examine the case with 3 disks, as it is depicted in the image on the right side, we will have a look at towers of size 1 (i.e. The pole in the middle (we will call it AUX) is needed as an auxiliary stack to deposit disks temporarily. Playing around to Find a Solution From the formula above, we know that we need 7 moves to move a tower of size 3 from the most left rod (let's call it SOURCE to the most right tower (TARGET). The number of moves necessary to move a tower with n disks can be calculated as: 2 n - 1

It can be put on another rod, if this rod is empty or if the most upper disk of this rod is larger than the one which is moved.

Only the most upper disk from one of the rods can be moved in a move.

The aim of the game is to move the tower of disks from one rod to another rod. the largest disk at the bottom and the smallest one on top. A number of disks is stacked in decreasing order from the bottom to the top of one rod, i.e. The game 'Towers of Hanoi' uses three rods. The rules of the game are very simple, but the solution is not so obvious.

The legend and the game 'towers of Hanoi' had been conceived by the French mathematician Edouard Lucas in 1883.

But there is - most probably - no ancient legend. But don't be afraid, it's not very likely that they will finish their work soon, because 264 - 1 moves are necessary, i.e. When they would have finished their work, the legend tells, the temple would crumble into dust, and the world would end. But one rule has to be applied: a large disk can never be placed on top of a smaller one. The priests, if the legend is about a temple, or the monks, if it is about a monastery, have to move this stack from one of the three poles to another one. each disk on the pole a little smaller than the one beneath it. The disks are of different sizes, and they are put on top of each other, according to their size, i.e. There is an old legend about a temple or monastery, which contains three poles. Enjoying this page? We offer live Python training courses covering the content of this site.

Hanoi towers problem