How to play the tower of Hanoi

This post shows how to play the tower of Hanoi, which is a fun game and is also interesting mathematically speaking.

___________________________________________________________________________

The Tower of Hanoi

The standard form of the game involves three rods and a number of disks of different sizes that can be slid onto any rod. At the start of the game, all the disks are placed on one rod in ascending order with the smallest disk on top. The following diagram shows a tower of Hanoi with 6 disks in the starting position.

Figure 1 – Tower of Hanoi with 6 Disks

towerhanoi-display-1

To play the game, you can buy a tower of Hanoi set from Amazon. Or play the game online. Another way is to create a homemade tower of Hanoi set. The following is a homemade set made with dinner plates, plastic covers, jar covers and a quarter at the top (for a total of eight disks). The three positions identified by paper take the place of rods.

Figure 2 – Home Made Tower of Hanoi with 8 Disks

towerhanoihomemade1

The following is a tower of Hanoi with 32 disks found in Mexico as shown in Wikipedia.

Figure 3 – Tower of Hanoi with 32 Disks

tower-of-hanoi-32-disk

___________________________________________________________________________

The Rules of the Game

Given a tower of Hanoi such as the one set up in Figure 1, the objective is to move all the disks to another rod (also in ascending order with the smallest disk on top). In making the moves, the following rules must be obeyed.

  • Only one disk can be moved at a time.
  • Only the uppermost disk on a rod can be moved.
  • No disk can be placed on top of a smaller disk.

The rod where all the disks are placed at the beginning (the leftmost rod in Figure 1 or the leftmost paper) is called the starting rod. The rod where all the disks land at the end of the game is called the destination rod. The destination rod can be any one of the two rods other than the starting rod (either the middle rod or the rightmost rod in Figure 1). The rod that is nether the starting rod nor the destination rod is called the intermediate rod. The distinction among the three rods is important as we describe the game in more details below.

The number of disks used in the game is called the height of the tower.

___________________________________________________________________________

Playing The Game

To get a sense of how the game is played, try playing with a tower with a small number of disks (e.g. three disks). Once the three-disk game is mastered, move onto the four-disk game. The following diagram shows the moves in a three-disk game.

Figure 4 – The Moves for the 3-Disk Game

towerhanoi-33

In Figure 4, the first row shows the three disks (red, orange and green) in the starting rod (the leftmost rod). The destination rod is chosen to be the rightmost rod. The first move is to place the red disk into the the destination rod. The second move is to place the orange disk into the intermediate rod, and so on. The game is completed in seven moves. The following two diagrams shows the moves in a 4-disk game.

Figure 5 – The Moves for the 4-Disk Game

towerhanoi-43-1

Figure 6 – The Moves for the 4-Disk Game (continued)

towerhanoi-43-2

As in the 3-disk game, the leftmost rod is the starting rod and the rightmost rod is the destination rod. In Figures 5 and 6, there is the additional blue disk (the largest disk). The game is completed in 15 moves – seven moves shown in Figure 5 and eight moves shown in Figure 6.

The diagrams for the 3-disk game and 4-disk game are very informative. They show that the game can be played in a recursive fashion. Note that the seven moves in Figure 5 transfer the top three disks into the middle rod (the intermediate rod). The next move is to transfer the largest disk (blue disk) from the starting rod into the destination rod. This is accomplished in the first move in Figure 6. The moves in the rest of Figure 6 are then to transfer the three disks from the middle rod into the destination. Essentially, the 4-disk game is accomplished by playing the 3-disk game twice with one additional move in between the two 3-disk games (to transfer the largest disk to the destination rod). It turns out that this recursive strategy is an optimal way to play the game.

___________________________________________________________________________

A Closer Look

As demonstrated by the above diagrams, the game of the tower of Hanoi is played recursively. With n disks, move the top n-1 disks into the the intermediate rod (by following the rules of course). Then move the largest disk in the starting rod into the destination rod. To complete the game, move the n-1 disks sitting in the intermediate rod into the destination rod. In other words, the n-disk game is executed by playing the (n-1)-disk game twice with a move of the largest disk in between.

The idea of recursion sounds simple enough. The game up to four disks are easy to play. When the disk count is larger, there are a lot of sub games to keep track of. Without some guiding principles, it is easy to get “lost”. Here’s some ideas to carefully manage the sub games that are required in the recursion.

The first move.

  • If the number of disks is even, move the smallest disk into the intermediate rod.
  • If the number of disks is odd, move the smallest disk into the destination rod.

For example, in moving 4 disks from rod A to rod C, the first move is to move the smallest disk (among the four disks) into rod B. On the other hand, in moving 3 disks from rod A to rod C, the first move is to move the smallest disk (among the three disks) into rod C.

The subsequent moves.

  • When moving m disks from rod A to rod B (rod A is the starting rod and rod B is the destination rod in this sub game with rod C being the intermediate rod), move m-1 disks to the rod C. Then to move the largest disk (in the m disks) to rod B. Then move the m-1 disks in the rod C to the rod B.
  • The moving of the m-1 disks is another sub game which can be executed by playing two (m-2)-disk games and one move in between with its own starting rod and destination rod.
  • The breaking down into smaller game continues until the number of disks is smaller enough to be processed as one continuous process. For example, the 3-disk game can be considered the smallest sub game that can be played without further reduced. If preferred, the 2-disk game can be used as the smallest unit.

To illustrate, consider the 8-disk game. The game requires a minimum of 255 moves. Instead of showing all the 255 moves, we break down the game into phases as shown in the following two diagrams.

Figure 7 – Phases of the 8-Disk Game

A = Leftmost Rod, B = Middle Rod and C = Rightmost Rod
towerhanoi-83-phases-i

Figure 8 – Phases of the 8-Disk Game (continued)

A = Leftmost Rod, B = Middle Rod and C = Rightmost Rod
towerhanoi-83-phases-ii

Figure 7 describes all the moves at a high level to place the top 7 disks into rod B. Then Figure 8 describes all the moves to place the 7 disks in rod B into rod C. In other words, the figures outline how to place two 7-disk games. Not shown in these two figures is the move of the largest disk (black) from rod A to rod C. The two figures are the results of thinking backward. For example, to achieve the result shown in phase 7 (7 disks on rod B), we must first place 6 disks on rod C, and for that to happen, we must first place 5 disks on rod B and so on. In Figure 7, to achieve the results shown in phase 14, we must first place 6 disks on rod A and before that place 5 disks on rod C (there are 6 disks on rod C but the one at the bottom is fixed).

The early phases in each figures are relatively easy. The later phases are very involved. For example, to go from phase 3 to phase 4, simple move the top disk in rod A in phase 3 to rod C. Then move the three disks in rod B in phase 3 to rod C. Going from phase 5 to phase 6 would require a lot more maneuvering. First move the top disk in rod A in phase 5 to rod C and then move the 5 disks in rod B in phase 5 to rod C. To make that happens, first move the top 3 disks to rod C, later 4 disks to rod A and then 5 disks to rod C.

To go from phase 6 to phase 7, first move the top disk in rod A in phase 6 to rod B. Then move the 6 disks in rod C in phase 6 to rod B. To do that, first move 3 disks to rod A, then 4 disks to rod B, then 5 disks to rod A and finally 6 disks into rod B. In other words, each phase will have multiple recursions. When it involves a large number of disks, it may be helpful to have a diagram such as Figure 7 or 8 drawn out for that phase.

___________________________________________________________________________

How Efficient is this Approach?

The 8-disk game described above in Figure 7 and Figure 8 indicates that the game of the tower of Hanoi can be very convoluted (this has only 8 disks)! The movement of disks is not direct. To move n disks into one particular rod, we must maneuver smaller blocks of disks among the three rods (for every smaller possible size and multiple times for each size). Is there a more efficient way to play the game other than the recursive idea described above? The answer is no.

In the algorithm described above, the number of moves required to complete the n-disk game is 2^n-1. This number is the minimum, i.e. it is impossible to play the game in fewer moves. In general, let M_n be the minimum number of moves for the n-disk game. Recall that the n-disk game is executed by playing the (n-1)-disk game twice with a move of the largest disk in between. So we have the following relation:

    M_n=2 \times M_{n-1}+1

The above relation says that when the n-disk game is executed by doing the two plays of the (n-1)-disk game in the minimal way plus one additional move, the resulting number of moves is minimal for the n-disk game.

It is clear that M_1 is 1, which is 2^1-1. It is also clear that M_2 is 3, which is 2^2-1. Suppose that M_{n-1}=2^{n-1}-1. Consider the following calculation:

    M_n=2 \times M_{n-1}+1=2 \times (2^{n-1}-1)+1=2^n-1

This inductive reasoning shows that a best strategy for playing the n-disk game of the tower of Hanoi is by executing an (n-1)-disk game with one subsequent move of the largest disk and by executing another (n-1)-disk game. The resulting number of moves is 2^n-1.

___________________________________________________________________________

A Different Take on the Game

The game of the tower of Hanoi was invented by the French mathematician Édouard Lucas in 1883. A year later, an author called Henri de Parville told of an interesting tale about the origin of the tower of Hanoi. The following is a translation in English, cited in [1].

    In the Temple of Benares, beneath the dome which marks the centre of the world, rests a brass-plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah! Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.

This is an enchanting story. It is not known whether Lucas, the inventor of the game, invented this legend or was inspired by it. One thing is clear. The legend accurately describes the enormity of the 64-disk game of the tower of Hanoi. The least number of moves that are required to play the 64-disk game is 2^{64}-1, which is

    18,446,744,073,709,551,615

Assume that the priests can move one disk per second, it would take about 5.85 \times 10^{11} years, or 585 billion years to complete the 64-disk game. In contrast, the age of the universe is believed to be 13.82 billion years. The age of the sun is believed to be 4.6 billion years. The remaining lifetime of the sun is believed to be around 5 billion years. So by the time the sun dies out the game is still not finished!

Consider the 32-disk tower of Hanoi shown in Figure 3 above. The number of moves would be 2^{32}-1 The total time it would take would be 4,294,967,295 seconds, assuming one second per move. This would be about 136.2 years. The 32-disk tower, half as tall as the one in the Temple of Benares, would be a fast project in comparison.

Towers such as the one in the Temple of Benares or even the 32-disk tower are not for us mortals. We play the game for enjoyment and, for some of us, for the mathematical aspects. The following table give an estimate of the required times (assuming moving one disk per second).

    \displaystyle \begin{array}{lllllll} \text{Disks} &\text{ } & \text{Approx Time} & \text{ } &\text{Disks} &\text{ } & \text{Approx Time}\\  \text{ } & \text{ } & \text{ }  \\  7 &\text{ } & 2.12 \text{ min} & \text{ } & 18 &\text{ } & 3.03 \text{ days}\\     \text{ } & \text{ } & \text{ } \\  8 &\text{ } & 4.25 \text{ min} & \text{ } & 19 &\text{ } & 6.07 \text{ days} \\  \text{ } & \text{ } & \text{ }  \\  9 &\text{ } & 8.52 \text{ min}  & \text{ } & 20 &\text{ } & 12.14 \text{ days} \\  \text{ } & \text{ } & \text{ }  \\  10 &\text{ } & 17.05 \text{ min} & \text{ } & 21 &\text{ } & 24.27 \text{ days} \\  \text{ } & \text{ } & \text{ }  \\  11 &\text{ } & 34.12 \text{ min} & \text{ } & 22 &\text{ } & 48.55 \text{ days}\\  \text{ } & \text{ } & \text{ }  \\  12 &\text{ } & 1.14 \text{ hours}  & \text{ } & 23 &\text{ } & 97.09 \text{ days}\\  \text{ } & \text{ } & \text{ }  \\  13 &\text{ } & 2.28 \text{ hours}  & \text{ } & 24 &\text{ } & 194.18 \text{ days}\\  \text{ } & \text{ } & \text{ }  \\  14 &\text{ } & 4.55 \text{ hours}  & \text{ } & 25 &\text{ } & 1.06 \text{ years}\\  \text{ } & \text{ } & \text{ }  \\  15 &\text{ } & 9.10 \text{ hours}  & \text{ } & 26 &\text{ } & 2.13 \text{ years}\\  \text{ } & \text{ } & \text{ }  \\  16 &\text{ } & 18.20 \text{ hours}  & \text{ } & 27 &\text{ } & 4.26 \text{ years}\\  \text{ } & \text{ } & \text{ }  \\  17 &\text{ } & 36.41 \text{ hours}  & \text{ } & 28 &\text{ } & 8.51 \text{ years}\\    \end{array}

One thing that stands out from the table is that adding one more disk to the game doubles the running time. This illustrates that the tower of Hanoi game is an exponential time problem. Recall that the n-disk game is executed by playing two (n-1)-disk games with one additional move in between. So an n-disk game would take twice as long as an (n-1)-disk game, assuming the speed for one move is uniform throughout.

The game of the tower of Hanoi is played in exponential time. This is evidenced by the above observation that by increasing one unit (one disk in this case), the total time (the total number of moves in this case) is increased by a constant multiple (doubling in this case). The relation that describes the game of the tower of Hanoi is T \approx 2^n, and in general T \approx a^n. To contrast, a game is played in linear time if by increasing one unit, the total time increases by a constant but additive amount. The relation that describes the linear time increase is T \approx a \times n.

What would be the increase in time (the number of moves) if the number of disks is doubled? From the above discussion, the total time for the 32-disk game is about 136.2 years (assuming one second per move). The total time for the 64-disk game is about 585 billion years (again assuming one second per move). No clarity here. By comparing in the same time unit of measurement (e.g. in seconds), we will see that the time for 64-disk game is roughly the square of the 16-disk game! This is also a phenomenal increase as there is an unbridgeable gulf between 1.36 century and 585 billion years! This is exponential time increase. Assuming the original number of disks is n, the total time for 2n disks is T \approx 2^{2n}=(2^n)^2. For a smaller illustration, the total time for an 8-disk game is 2^8-1=255 while the total time for a 16-disk game is 2^{16}-1=65535. The square of 255 is 65,025, which is roughly 65,535.

Towers with 8 or fewer than disks are good practices for anyone learning the game. Any game with 9 to 11 disks takes about a half hours or less and should be challenging but should be doable if someone desires to play by hand. Any game listed in the table that are stated in hours would be extremely challenging. The number of moves to keep track of would be staggering (for a human mind). The 16-disk game would take over 65,000 moves (65,535 to be exact)! This and the larger games listed in the table would be good computer programming exercises.

For the mathematical facts and/or generalizations of the 3-rod tower of Hanoi game, see this Wikipedia entry and [1].

___________________________________________________________________________

Reference

  1. Hinz Andreas M., Kla. Dzar Sandi, Milutinovic Uros, Ciril Petr, The Tower of Hanoi – Myths and Maths, Springer Basel, Heidelberg, New York, Dordrecht, London, 2013

___________________________________________________________________________
\copyright \ 2016 \text{ by Dan Ma}

Advertisements

2 thoughts on “How to play the tower of Hanoi

  1. Pingback: Tower of Hanoi – Climbing Math Everest

  2. Pingback: Tower of Hanoi | All Math Considered

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s