How to Solve Tower of Hanoi Puzzles
The Tower of Hanoi is one of the truly classic puzzle games, challenging players with its seemingly simple but frustratingly difficult goal. In the Tower of Hanoi puzzle a player attempts to move a large pile of disks, known as the Tower, from the leftmost peg to the rightmost on the puzzle board. The rules of the puzzle state that the player can only move one disk per turn and can never place a larger disk onto a smaller one at any time.
Based on these guidelines, players attempt to move their initial Tower disk-by-disk towards the target third peg in a seemingly complex method of movement using any of the three available pegs until it is rebuilt onto the rightmost peg exactly as it was on the initial leftmost peg at the start of the puzzle. The puzzle was invented by the French mathematician Edouard Lucas in 1883 and is often described as a mathematical puzzle, although solving the Tower of Hanoi doesn't require any mathematical equations at all for a human player. In fact, the ChessandPoker.com Tower of Hanoi solution provides two simple algorithms that allow players to optimally solve Tower of Hanoi puzzles with any number of disks when applied to the puzzle!
Optimal Algorithms for Solving Tower of Hanoi Puzzles
Tower of Hanoi Puzzles may consist of any number of disks as long as they total three or more. The most common total of disks is seven, but you may have puzzles with more (or less) disks in play. The proper solution for a Tower of Hanoi puzzle is very similar for all of the various puzzles, but varies slightly based on whether or not the total number of disks in the puzzle is Odd or Even. In this guide we'll focus on solving a seven-disk Tower of Hanoi puzzle and we've provided an example of our puzzle board in the graphic above, complete with colored disks for reference purposes.
In our solution algorithms below we'll focus mainly on the top three disks of the Tower. These three disks are moved around quite a bit in an optimal solution, so it will be necessary to become familiar with them. The topmost disk is known as Disk 1. It is colored Red in our graphic and is the smallest of all the disks. The second disk from the top is called Disk 2. It is the second smallest disk in the puzzle and is colored Orange in our examples. Finally, the third disk down is called Disk 3 and is colored Yellow. The remaining disks of various colors are simply known as Big Disks, and numbering them is not necessary. We'll now take a look at the algorithms used to solve the Tower of Hanoi and how these three focus disks will factor into each solution.
| Odd Number of Disks | Even Number of Disks |
1. Move Disk 1 to the LEFT |
1. Move Disk 1 to the RIGHT |
In the chart to the left you'll find the two optimal move algorithms for any Tower of Hanoi puzzles based on the total number of disks in your starting Tower. The leftmost column shows the move algorithm for puzzles with an odd number of disks, and the rightmost column details the solution for puzzles with an even number of starting disks. In our guide we'll be using the "odd" algorithm since our example puzzle contains seven disks. To solve their puzzle a player will perform the applicable 8-move algorithm to their board repeatedly until all of the disks have been transferred from the leftmost starting peg to the rightmost target peg.
The two algorithms share some notable similarities, particularly that the tiny Disk 1 is repositioned on every other move in an optimal solution. For example, the odd algorithm has it moving one peg to the left on steps 1, 3, 5 and 7. So if Disk 1 currently resides on the right most peg, it would move one peg to the left to the middle peg on its turn. And if it was instead resting on the middle peg it would move one peg to the left onto the leftmost peg. But what if it is already on the leftmost peg? As we can see in our movement graphic above, you may think of the Disk 1 movements across the board as a circular motion. If Disk 1 is on the leftmost peg, moving it left would bring it back around to the right most peg. This completes the circle of movement and would once again allow Disk 1 to move left onto the middle peg and then back onto the leftmost peg again, ready to jump back around to the rightmost peg and start the sequence again. Of course, for puzzles with an Even number of disks the movements would be reversed but would follow the same pattern. Disk 1 would jump from the leftmost peg to the right, landing on the middle peg. From the middle peg it would move right onto the rightmost peg, and then back around to the leftmost peg again to complete the circular sequence.
We'll now take a look at the first application of our algorithm to the seven-disk Tower of Hanoi board, which will start us on our way towards the optimal solution for the puzzle. An optimal solution solves the applicable Tower of Hanoi puzzle in the least possible number of moves. By using our algorithms, the player is assured that their solution will always be optimal since it efficiently ensures that there are no wasted maneuvers of any disks!
How to Solve a Seven-Disk Tower of Hanoi Puzzle
Step One - Move Disk 1 to the Left: The first step in the "odd" puzzle algorithm instructs us to move Disk 1 to the left. As we've just discussed, whenever Disk 1 is on the leftmost peg moving it left entails looping it back around to the rightmost peg to complete the circular left-to-right motion. As you can see in the graphic, Step 1 has been performed and now shows Disk 1 on the target rightmost peg.
Step Two - Move Disk 2: On Step 2 we're informed that we need to move Orange Disk 2, but it doesn't say where to move it. However, a closer examination of the board shows us that, based on the rule that a player may not place a bigger disk onto a smaller one, Disk 2 only has one legal move. We can confidently move Disk 2 to the middle peg to complete the step. In fact, Disk 2 will always only have one legal move.
Step Three - Move Disk 1 to the Left: The third step once again has tiny Disk 1 moving itself to the left, which means that this time it will be jumping onto Disk 2 which just moved there on our previous step. This is a legal move, of course, since Disk 1 is smaller than Disk 2. It's useful to note that Disk 1 will frequently be moving onto Disk 2. In fact, it does so twice in each algorithm on steps 3 and 7.
Step Four - Move Disk 3: Step 4 has us moving Yellow Disk 3 for the first time in the algorithm. As is the case for Disk 2, there will always only be one legal move available for Disk 3 when using our algorithms. Since Disk 3 cannot be placed on the peg containing the smaller Disk 1 as the topmost disk, the only peg Disk 3 can claim residence on is the rightmost peg. Our graphic shows the board after this move has been played.
Step Five - Move Disk 1 to the Left: As you've no doubt now become acquainted with, Step 5 requires Disk 1 to yet again be moved one peg to the left. For those players with an eye for patterns, you may notice that Disk 1 doesn't seem to like Disk 3. In fact, if you're applying the algorithm correctly you'll actually never be placing Disk 1 onto Disk three. It always moves onto Disk 2 or a Big Disk.
Step Six - Move Disk 2: Step 6 brings about another movement for Disk 2, which once again has only one legal move available to it, this time hopping onto Yellow Disk 3. More patterns? Indeed, it would appear that each step in the algorithm so far has been working to rebuild the Disk 1-2-3 section of the initial tower. The next move will of course complete the construction and bring us closer to the end of the algorithm.
Step Seven - Move Disk 1 to the Left: Disk 1 moves to the left, looping back around to the rightmost peg and preparing for the final move of the first run-through of the algorithm. If we were just solving a three-disk Tower of Hanoi, the puzzle would already be solved at this point! But with more disks to go, we'll need to proceed to the final step of the algorithm before we'll be ready for another application.
Step Eight - Move a Big Disk: Up to this point, we've only been moving the smallest three disks back and forth on top of one another. Now that their mini-tower has been rebuilt by the algorithm, it's time to move a Big Disk. The big disk that has a legal move available to it would in this case be the Green Disk. Step 8 will always feature a completed mini-tower and only one big disk with a legal move. That's it for the first run-through!
Multiple Algorithm Applications
After finishing Step 8, the first application of the algorithm is complete. To continue the solution, the odd algorithm must once again be performed in its entirety. Move Disk 1 to the left, move Disk 2, move Disk 1 to the left again, move Disk 3, move Disk 1 to the left for the third time, move disk 2, move Disk 1 to the left and finally move the next Big Disk (in this case it's the Light-Blue disk). The graphic above shows the board after the second run-through of the algorithm so you'll be able to verify that your technique is correct. Now that you've got the hang of it, continue to apply the algorithm until your Tower of Hanoi puzzle is completely solved. Of course, if your starting tower has an even number of disks you'll need to use the alternate "Even" algorithm to solve the puzzle, which follows the same process but in the opposite direction. Complete each of the eight steps before restarting the algorithm, and eventually you'll have a completely solved Tower of Hanoi!
ChessandPoker.com Browsing Options
Thank you for reading this featured game article! Please select one of the links below to continue navigating the Chess and Poker Dot Com website. Let us know if we can be of any further help. Good luck and happy gaming!
Game Strategy Guides More strategy guides and game solutions are waiting for you on our homepage!
Discuss this article Visit the game forums and chat with our knowledgeable community members.
Shop for games Browse our store and find some great savings on pretty cool merchandise.
Read our Blog for site updates and commentary on a variety of interesting subjects.
Contact us to make a suggestion, ask a question or comment on this article.
Make a Donation to the ChessandPoker.com website at your convenience.
Copyright © 2003 James Yates All Rights Reserved. Article written by James Yates, founder and owner of the ChessandPoker.com website. Please review our Terms of Use page for information concerning the use of this website.
Rubik's Cube Solution
Solve the Rubik's cube in seven steps with our beginner-level guide.
Carcassonne Strategy
Rules and strategy for the most addictive game you've never heard of.
Sudoku Strategy
Covers beginner and advanced techniques for solving Sudoku puzzles.
Tic Tac Toe Solution
Reveals how to win or draw at the classic Pencil and Paper game.
Einstein's Problem
Solve Einstein's famous puzzle by dissecting his clever list of clues.
Peg Solitaire Strategy
Graphical notation shows how to optimally solve this perplexing puzzle.
Fifteen Puzzle Solution
Unravel the scrambled numbers of the famous fifteen puzzle.
Rock Paper Scissors
Prepare yourself for the hand-to-hand combat encounter Roshambo.
Dice Probabilities
Understand the probabilities at work when you throw the dice.
Domino Strategy
Groundbreaking work explores the strategy of All-Fives dominoes.
Solitaire Strategy
Learn how to efficiently clear your columns when solving Klondike Solitaire.
Vegas Solitaire
The dastardly Klondike variant which introduces three cards at a time.
Blackjack Basic Strategy
Details an effective strategy for all plays in the popular card game.
Video Poker Strategy
Covers optimal strategy for the video poker variant Jacks or Better.
Chess Strategy
Advanced tactics and strategy for the most popular board game ever.
Limit Hold em Strategy
Beginner-level guide designed to focus your play in Limit Hold'em.