How Towers of Hanoi Works

Monks are known for their spiritual discipline, but the inhabitants of the Hindu temple of Benares are dedicated to the extreme. Day and night, they silently shuffle delicate gold wheels from one diamond post to another. The 64 disks, each thick as a bumblebee, are taken from their original post, slipped onto a second post and eventually begin to tower on a third post -- all with one unflinching rule: A larger disk may not be placed on a smaller one.

While the monks strive to finish their task, everyone else dreads its resolution. When the final disk falls into place, the tower, the temple and the world's terra firma will dissolve into thin air.

Fortunately, the downfall of humankind doesn't actually hinge on the completion of a puzzle. The gold-toting monks are simply part of an enduring legend that surrounds the Towers of Hanoi, a puzzle game invented in the late 1800s.

Even if there were monks actually completing a 64-disk switchback puzzle somewhere, a few reassuring calculations reveal it would require more than 580 billion years to complete the puzzle -- even if the monks moved a disk every single second [source: Lawrence Hall of Science].

Luckily, you can play a more manageable version of Towers of Hanoi in just a few minutes. Also known as the Tower of Brahma or simply Tower of Hanoi, the object is to rebuild the tower, usually made of eight wooden disks, by transferring the disks from Post A to Post B and Post C. As in the legend, the rules forbid placing a larger disk upon a smaller one.

The resulting waltz may seem deceptively simple, at least for the first three moves, which consist of moving the top disk to Post B or C, and the underlying disk to the remaining unoccupied post. After that, you'll need to employ strategy to solve the puzzle.

Still, the Towers of Hanoi can be tackled by children as young as 5 (who sometimes play a scaled-down version with fewer disks), yet it presents a wily challenge to adults. And you may just pick up a greater understanding of mathematical principles along the way.

The History of Towers of Hanoi

Towers of Hanoi was invented and marketed in 1883 by Edouard Lucas (who used the name Professor N. Claus, which was an anagram of his last name). Lucas, a French professor of mathematics, spread the legend that helped popularize the game by including a written account of the Brahmin monks' puzzling plight in each box, along with the game's instructions. The tale gained further traction when it was depicted in several publications of the day. Henri De Parville, editor of the journal "La Nature," also wrote about the legend in the late 1800s [source: Stockmeyer]. The setting of the legend occasionally varies, and has included the city of Hanoi in Vietnam.

Lucas became known for his work with the Fibonacci number sequence, a principle that recently experienced a popular resurgence after the "Angels and Demons" movie from 2009. The Fibonacci-related Lucas number series is, in fact, named after Lucas. In the Lucas series, each number is the sum of the two numbers preceding it (except for the first two numbers in the series). An example of the Lucas series is: 2, 1, 3, 4, 7 and 11.

In addition, Lucas perfected a way to determine whether a number was prime, a strategy that's still in use today. Many of his mathematical discoveries are standard coursework for budding mathematicians, and the Towers of Hanoi remains a helpful aid when illustrating recursive theory [source: Anderson, et al.]. At its most basic, recursive theory is like continuously slicing an orange into halves or pieces. One large problem is broken down into several smaller problems, which are then broken into smaller problems until they cannot be further reduced. By building smaller towers on various posts before reconstructing them as one large tower, puzzle solvers employ recursive theory.

Lucas died in 1891 after a broken dinner plate lacerated his cheek and caused an infection. His obituary in the January 1892 issue of "Popular Science Monthly" called his mathematical inventions "as amusing as they were instructive."

Solutions of Towers of Hanoi

While the Towers of Hanoi's past is grounded in recreational math, its future involves some serious scientific application. The game even is used to assess the extent of brain injuries, or to illustrate complex mathematical theory. It also shows promise as an aid to rebuild neural pathways.

Anyone who attempts to unravel the Towers of Hanoi mystery can benefit, regardless of whether or not he solves the puzzle. If you do want to build that tower, though, the key is to seek a solution. In doing so, you'll employ a host of problem-solving skills as you calculate moves and anticipate outcomes. The activity helps the pre-frontal cortex (the anterior portion of your brain's frontal lobe) forge new and useful connections [source: Miyake].

While Towers of Hanoi doesn't look like a complicated puzzle, if you don't recognize the pattern required to solve it, it can seem indecipherable. The solution is to move the disks in a clockwise, repeating pattern (remembering not to place a larger disk on a smaller one). Think of the three posts as Post A, Post B and Post C, and consider this solution for a three-disk version of the game:

begin with three disks on Post A
move the smallest disk clockwise from Post A to Post C
move the next largest disk from Post A to Post B
move the smallest disk from Post C to Post B
move the remaining (and largest) disk from Post A to Post C
move the smallest disk from Post B to Post A
move the next largest disk from Post B to Post C
finally, move the smallest disk from Post A to Post C, where you will have rebuilt the tower on Post C [source: Math Forum]

You'll follow the same pattern to solve the puzzle, no matter how many disks you play the game with.

By attempting to solve Towers of Hanoi, you'll be exercising the parts of your brain that help you manage time, present a business plan or make complex arguments. And that's not bad for a puzzle that predates the (admittedly towering) Statue of Liberty.

Author's Note

My favorite puzzles involve patterns, which is why I looked forward to solving the Towers of Hanoi. As I attempted a trial run at relocating the disks, the solution was just out of reach -- like a word I couldn't quite recall. I wasn't ready to read the answer key, which spelled out step-by-step moves, so I set the game aside. And, like most puzzlers, the answer became clearer as I gained distance from the problem. As I braided my daughter's hair, the pattern presented itself: I moved strands of hair from A to C, then to B and back to A. Sometimes the best connections come unexpectedly.

Sources

Anderson, Matt, et al. "Biographies: Edouard Lucas." (June 4, 2012) http://library.thinkquest.org/27890/biographies2.html
Hall, Granville Stanley, et al. "A Study of Puzzles." The American Journal of Psychology. University of Illinois Press. 1897. (June 4, 2012)
Lawrence Hall of Science. "Tower of Hanoi." (June 4, 2012) http://www.lawrencehallofscience.org/java/tower/index.html
Math Forum. "Tower of Hanoi." (June 4, 2012) http://mathforum.org/dr.math/faq/faq.tower.hanoi.html
Miyake, Akira, et al. "The Unity and Diversity of Executive Functions and Their Contributions to Complex 'Frontal Lobe' Tasks: A Latent Variable Analysis." The Journal of Cognitive Psychology. 2000. Vol. 41, 49 to 100. (June 4, 2012)
Popular Science Monthly. "Obituary Notes." January 1892. (June 4, 2012)
Roberts, Eric. "Recursive Procedures." Stanford University. (June 4, 2012) http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/chapters/06-recursive-procedures.pdf
Stockmeyer, Paul. "The Tower of Hanoi." (June 4, 2012) http://www.cs.wm.edu/~pkstoc/page_1.html
Wolfram MathWorld. "Tower of Hanoi." (June 4, 2012) http://mathworld.wolfram.com/TowerofHanoi.html