Navigation Panel: Previous | Up | Forward | Graphical Version | PostScript version | U of T Math Network Home

Patterns in the Towers of Hanoi Solution

Asked by Alex Doskey on May 7, 1997:
I first encountered the Towers of Hanoi puzzle when I was 8 years old. With an eager mind a attacked the puzzle and quickly discovered a pattern to its solution. This recursive solution is the one described in you web page discussion of this puzzle. At the same time I discovered another patten involved in moving the pieces, and since that time I have never seen any mention of this pattern in any discussion about this puzzle. This is not a difficult pattern, and I was wondering if I was just not reading the right articles.

Although there is much more to it than this, here is the basic pattern that I discovered: Each piece in the puzzle moves in the same direction (clockwise or counterclockwise) throughout the entire solution of the puzzle. If you number the pieces (from smallest to largest or vice versa) all of the odd numbered pieces will move in one direction, and all the even numbered pieces will move in the opposite direction.

The frequency of the moves is also predictable. The smallest piece will move every other turn, the next smallest every fourth turn, the next smallest every eighth turn and so on. These facts together lead to a very simple solution to the puzzle. Pick a direction to move the smallest piece. Move this piece every other turn. On the alternate turns, there is only one move available to you, so no thinking is required.

This solution is much easier to work with (especially for larger stacks of disks), than the recursive solution, and yet I have never seen or heard any mention of it. My question is has anyone else ever seen this, or did I make an amazing discovery when I was a child?

I do have more information about patterns involved in this puzzle if anyone has any questions. For example, how do you determine which direction to move the smallest disk if you want to move the stack from tower A to tower C and not tower B. The answer depends on if the stack has an odd or even number of disks. You can experiment with the ideas I presented in here, but I would recommend working with a physical representation of the puzzle, not a computer version. My first exposure was with towers and disks made of wood. If I hadn't had hands on experience with this puzzle, I may have never noticed these patterns.

Alex

What you have described is actually the same solution as the recursive solution (that is, it is the same sequence of moves). However, you have described that sequence of moves in a way that makes it quite a bit easier to actually play the game. You are to be congratulated on noticing those patterns at such a young age, and more mention should be made of them in articles describing the game.

The reason there is a heavy emphasis made on the recursive nature of the solution, rather than on the patterns you have noticed, is that it is only through the recursive nature of the solution that fundamental theoretical questions can be answered. For example, how do you know that the pattern of moves you described will always solve the puzzle, regardless of the number of disks? And how do you know that it does so in the most efficient way? You can verify it by experiment, but experiment only carries you so far. For instance, you might verify it for 1 disk and for 2 disks and 3 disks and 4 disks and 5 disks, but then how do you know it's true for 6? And if you verify it experimentally for 6, how do you know it's true for 7 as well? And so on.

The recursive formulation allows you to easily answer those questions. For example, here's a proof that your pattern always works:

To move the pile of n disks from tower 1 to tower 3 (which we shall call the "counterclockwise" direction), you must move the top n-1 disks from 1 to 2 (which we shall call "clockwise"), then move the bottom disk from 1 to 3 (counterclockwise), then the top pile from 2 to 3 (clockwise).

Therefore, in moving a pile of n disks counterclockwise, the bottom disk will move counterclockwise and the remaining n-1 disk pile will move clockwise.

Therefore, the bottom disk of that remaining n-1 disk pile (which is the second from the bottom in the original pile) will move clockwise, and the remaining n-2 disk pile will move counterclockwise.

Therefore, the bottom disk of that remaining n-2 disk pile (the third from the bottom in the original pile) will move counterclockwise, and the remaining n-3 disk pile will move clockwise.

And so on. To make the argument mathematically rigorous, you would use the principle of induction, but I want to keep this answer at an informal level. You end up with the fact that the bottom, third from the bottom, fifth from the bottom, etc. must all move counterclockwise, while the remaining disks must move clockwise. This is exactly the same pattern you noticed, except now it is no longer in the category of something that has been observed to be true in all the cases one has happened to verify, but it is in the category of something which is known to be true with full mathematical certainty, because it can be logically proven.

You can derive the rest of your patterns, about which disks move when, in a similar way.

The bottom line is essentially this: the patterns you noticed are probably the easiest way to play the game, and the easiest way to physically accomplish the task of moving the disks. However, the confidence that these patterns actually work, that they actually form the minimal way of moving the disks, comes from the recursive formulation of the solution and the powerful mathematical arguments that can be derived from it.

Together, these two things illustrate the two important halves of mathematical discovery: the experimentation and noticing of patterns (such as you noticing the clockwise-counterclockwise method of solving the Towers of Hanoi puzzle), coupled with the formulation of them in a way which leads to the discovery of mathematical arguments that allow one to know with complete certainty why the patterns are the way they are (such as the recursive formulation of the Towers of Hanoi solution).

[ Submit Your Own Question ] [ Create a Discussion Topic ]

This part of the site maintained by (No Current Maintainers)
Last updated: April 19, 1999
Original Web Site Creator / Mathematical Content Developer: Philip Spencer
Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu