Home › Fun & Games › Tower of Hanoi
Tower of Hanoi
Move the whole tower from peg A to peg C, one disk at a time, never putting a bigger disk on a smaller one. Drag a disk or click two pegs, then see how close you got to the minimum number of moves.
Moves0
Minimum15
Time0:00
A 1
B 2
C 3 target
Drag a disk, or click a peg and then another peg.
Solved!
Advertisement
Advertisement
How to use the Tower of Hanoi
- Pick the number of disks (3 is easy, 8 needs 255 moves) and press New game.
- Move a disk by dragging it to another peg, or click the peg you want to take from and then the peg you want to put it on. Keys 1, 2 and 3 work too.
- Follow the one rule: a disk can only go on an empty peg or on a larger disk.
- Rebuild the tower on peg C. Your move count is compared with the minimum possible, 2ⁿ − 1.
- Stuck? Press Hint for the best next move, Undo to take a move back, or Solve to watch the optimal solution from where you are.
Minimum moves for each number of disks
The fewest moves needed to move a tower of n disks is 2n − 1. It comes from the recurrence T(n) = 2·T(n − 1) + 1 with T(1) = 1: you move the smaller tower out of the way, move the biggest disk once, and move the smaller tower back on top.
| Disks | Minimum moves (2n − 1) | Smallest disk moves | Largest disk moves |
|---|---|---|---|
| 3 | 7 | 4 | 1 |
| 4 | 15 | 8 | 1 |
| 5 | 31 | 16 | 1 |
| 6 | 63 | 32 | 1 |
| 7 | 127 | 64 | 1 |
| 8 | 255 | 128 | 1 |
| 10 | 1,023 | 512 | 1 |
| 64 | 18,446,744,073,709,551,615 | 263 | 1 |
In an optimal solution disk k (counting from the smallest, k = 1) moves exactly 2n − k times, which is why the smallest disk moves on every second turn.
How to solve the Tower of Hanoi
The recursive method
- Move the top n − 1 disks from the start peg to the spare peg (using the target peg as the helper).
- Move the largest disk from the start peg to the target peg.
- Move the n − 1 disks from the spare peg onto the target peg (using the start peg as the helper).
Each of steps 1 and 3 is the same puzzle with one disk fewer, so you repeat the idea until only one disk is left. This is a classic first example of recursion in computer science.
The easy pattern to remember
- Alternate moves. On odd-numbered moves (1st, 3rd, 5th…) move the smallest disk. On even-numbered moves make the only legal move that doesn't involve the smallest disk.
- Keep the smallest disk going the same way. With an odd number of disks it cycles A → C → B → A…; with an even number it cycles A → B → C → A….
- Disks on the same peg alternate parity. In an optimal solution an odd-numbered disk never lands directly on another odd-numbered disk, and even never on even.
Keyboard controls
| Key | Action |
|---|---|
| 1, 2, 3 (or A, B, C) | Pick up from / drop onto that peg |
| Esc | Put the lifted disk back |
| Ctrl + Z | Undo the last move |
| Tab, then Enter | Focus a peg and select it |
Frequently asked questions
What are the rules of the Tower of Hanoi?
All disks start stacked on one peg, largest at the bottom. You must move the whole stack to another peg, moving only one disk at a time (the top disk of a peg) and never placing a larger disk on top of a smaller one.
What is the minimum number of moves?
The minimum for n disks is 2^n − 1. That is 7 moves for 3 disks, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 255 for 8. Every extra disk doubles the moves and adds one.
What is the trick to solving it?
Think recursively: to move n disks to a target peg, first move the top n − 1 disks to the spare peg, move the largest disk to the target, then move the n − 1 disks on top of it. A handy pattern is that the smallest disk moves on every other turn, always in the same direction around the pegs.
Which way should the smallest disk move first?
With an odd number of disks, move the smallest disk straight to the target peg first (A to C). With an even number, move it to the middle peg first (A to B). Following this makes the optimal solution easy to find.
Can the solver finish a game I already started?
Yes. Press Solve at any time and it computes the shortest sequence of moves from your current position to a complete tower on peg C, then plays it with animation. You can stop it whenever you like.
How long would 64 disks take?
In the legend of the temple puzzle, monks move 64 golden disks. That needs 2^64 − 1, or about 18.4 quintillion, moves. At one move per second it would take roughly 585 billion years.
Related tools
Sliding PuzzlePlay the 15 puzzle and 3×3 to 6×6 sliding tile puzzles with numbers or your own photo.Sudoku OnlinePlay free Sudoku with 4 difficulty levels, notes, hints and a timer.Mastermind GameCrack the secret 4-color code in 10 tries using black and white feedback pegs.2048 GamePlay 2048 online with swipe controls, undo and best score.SolitairePlay classic Klondike Solitaire with Draw 1 or Draw 3 and undo.Spider SolitairePlay Spider Solitaire online with 1, 2 or 4 suits, hints, unlimited undo and a timer.Play Chess vs ComputerPlay chess online against the computer at 8 difficulty levels.Connect FourPlay Connect 4 online against the computer or a friend.Snake GamePlay classic Snake online with speeds, wall modes and high scores.Tic Tac ToePlay tic tac toe against an unbeatable AI or a friend.Block Puzzle GameClassic falling blocks puzzle game with levels and high score.MinesweeperPlay classic Minesweeper: 3 difficulties, flags, timer and a safe first click.Coin FlipFlip a coin online: heads or tails, multiple coins and stats.Yes or No WheelSpin the wheel for a yes or no answer to any question.Random Name GeneratorGenerate random first and last names by gender and origin.Random Team GeneratorSplit a list of names into random, balanced teams.Zodiac Sign CalculatorFind your zodiac sign, element and best matches from your birthday.Zodiac CompatibilityCheck love compatibility between two zodiac signs.Love CalculatorEnter two names and get a fun love compatibility score.Dice RollerRoll a D6 or any RPG dice (D4 to D100) with totals and history.Random Number GeneratorPick random numbers in any range, unique or lottery-style.Random Letter GeneratorPick random letters from the alphabet, with vowel, case and no-repeat options.Random Country GeneratorPick random countries with flags, capitals, population and area.Random Date GeneratorGenerate random dates between two dates, with weekday and format options.Numerology CalculatorFind your life path, expression and soul urge numbers from name and birthday.Birth Flower & Birthstone FinderLook up the birthstones and birth flowers for any month, with meanings.Picker WheelSpin a wheel to pick a random name or choice.Random Dog PicturesRandom dog photos and fun dog facts.Random Cat PicturesRandom cat photos and fun cat facts.Random Parrot PicturesRandom parrot photos and bird trivia.Dog Web StumbleJump to a random dog website.Cat Web StumbleJump to a random cat website.Parrot Web StumbleJump to a random parrot website.Random Animal GeneratorGet a random animal with its class, habitat and a fun fact, with filters.Word Guess GameGuess the hidden five-letter word in six tries. Unlimited games, stats and hard mode.Rising Sign CalculatorFind your ascendant sign and degree from birth date, time and place.Random Movie PickerCan't decide what to watch? Pick a random film by genre, decade and runtime.HangmanClassic friendly hangman word game with categories, hints and difficulty levels.Tarot Card ReadingDraw a free tarot spread from a full 78-card deck with upright and reversed meanings.Random Food PickerCan't decide what to eat? Spin a cuisine wheel and get a dish that fits your diet.Memory Card GameFlip cards and match emoji pairs on 4×3 to 6×6 grids, with moves, timer and best scores.Fortune Cookie GeneratorCrack a virtual fortune cookie for an original fortune, lucky numbers and a daily pick.Truth or Dare GeneratorDraw clean truth or dare questions for family, teens or parties, with player turns.Flappy GameTap to flap a round chick through bamboo gaps and beat your high score.Baby Name GeneratorDiscover 1,700+ baby names filtered by gender, origin and letter, and save favorites.Would You Rather QuestionsRandom would you rather dilemmas in five categories. Vote and see your A/B split.Dino Runner GameJump cacti and duck buzzing beetles in an original endless desert runner.Pet Name GeneratorFind the perfect name for a dog, cat, bird or bunny by species, style and coat color.Never Have I Ever QuestionsClean and party never have I ever questions with a built-in point counter for players.Typing GameType the falling words before they land; level up and track your WPM and accuracy.Fantasy Name GeneratorCreate elf, dwarf, orc, dragon and other fantasy names from race-specific syllable rules.Chinese Zodiac CalculatorFind your Chinese zodiac animal, element and yin or yang from your exact birth date.Random Question GeneratorRandom conversation starters: icebreakers, deep, funny, work-friendly and kids questions.Math Quiz GameTimed mental math rounds with four operations, five levels, streaks and high scores.Username GeneratorGenerate cool usernames and gamertags by style, fitted to each platform's rules.Magic 8 BallAsk a yes-or-no question, shake the ball and get one of the 20 classic answers.Flag QuizGuess the flags of all 196 countries in four modes, from multiple choice to timed.Band Name GeneratorInvent band names for 14 music genres, or blend two genres, with album titles too.Writing Prompt GeneratorRandom story starters, first lines, characters, settings, twists and poem prompts in 11 genres.Map QuizFind countries on a clickable world map or name the highlighted one, by continent.Drag Name GeneratorFind your drag queen or drag king name: puns built from your own name in seven styles.Fantasy Creature GeneratorInvent original fantasy creatures with a name, body, powers, habits, weakness and danger level.Periodic Table QuizLearn all 118 elements: quiz symbols, names and atomic numbers or click them on the table.Rapper Name GeneratorTurn your name into a rap name in seven styles, from Lil and MC to trap, drill and emo rap.Lottery Number GeneratorSecure random quick picks for Powerball, Mega Millions, EuroMillions, Lotto and custom games.Spelling Bee GameMake words from 7 honeycomb letters, always using the center letter. New daily puzzle.Superhero Name GeneratorInvent original superhero names with powers, an origin story and a weakness.Secret Santa GeneratorDraw Secret Santa names with exclusions and send everyone a private reveal link, no sign-up.Jigsaw PuzzleTurn a sample picture or your own photo into a 12 to 150 piece jigsaw puzzle and solve it.Pirate Name GeneratorGet swashbuckling pirate names from your first name, plus ship names, in four styles.Raffle DrawPaste names, add extra tickets and draw one or many random raffle winners with confetti.Couple Name GeneratorBlend two names into ranked ship names and couple names, from Brangelina-style to overlaps.Random Card DrawShuffle a 52-card deck and draw one or more random playing cards, with jokers and history.Mahjong SolitaireMatch pairs of free tiles to clear the Turtle and two smaller layouts, with hints, shuffle and undo.Age on Other PlanetsSee how old you are on Mars, Jupiter and every other planet, plus your next birthdays.Anagram SolverFind every anagram of a word or phrase: single words, multi-word anagrams and all sub-words.Scrabble Word FinderFind the highest-scoring words from your rack, with blank tiles, patterns and bingo bonus.Wordle SolverEnter your guesses and colours to see every possible answer and the best next guess.Crossword SolverFind words that fit a crossword pattern like c?t from the length and the letters you know.Word Search GeneratorMake a word search puzzle from your words, play it online or print it with an answer key.Pong GamePlay classic Pong online against the computer on 3 levels or with a friend, first to 11.Breakout GameClassic brick breaker game with levels, power-ups and lives. Play with mouse, touch or keyboard.Whack-a-MoleWhack the moles before they hide in 30 or 60 second rounds. Speed increases, best score saved.Simon Says GameRepeat the growing color and sound sequence. Classic memory game with strict mode and high score.Rock Paper ScissorsPlay rock paper scissors vs the computer in best-of matches, with stats and a lizard-Spock mode.CheckersPlay checkers online against the computer or a friend, with kings, undo and hints.ReversiPlay Reversi (Othello rules) online vs a 3-level computer or a friend, with move hints.GomokuGet five in a row on a 15×15 board against a smart computer or a friend.Battleship GamePlace your fleet and sink the computer's ships in this classic naval guessing game.FreeCellPlay FreeCell solitaire online with the classic numbered deals, undo, hints and auto-move.Maze GeneratorCreate random mazes in any size, solve them with the arrow keys, then print or save as PNG.Sudoku SolverType in any Sudoku and solve it instantly, get step-by-step hints and check it has one solution.Bingo Card GeneratorMake printable 75-ball or custom word bingo cards, from 1 to 200 unique cards, as PDF or print.Bingo Number GeneratorFree bingo caller for 75 or 90 balls with a live board, auto-call timer and spoken numbers.Online ScoreboardKeep score for any game: big team scores, game clock, periods, fullscreen and sport presets.Tournament Bracket GeneratorMake single or double elimination brackets for 2-64 players, click winners to advance, print.Trivia Quiz300+ general knowledge trivia questions in 10 categories. 10-question rounds with a timer and score.Random Fact GeneratorGet random fun facts about animals, space, the body, history, science, food and more.Random Joke Generator200+ clean, family-friendly jokes: dad jokes, puns, knock-knock jokes and more. Tap to reveal.Random Riddle Generator150+ riddles with hidden answers in easy, hard and kids levels. Guess, get a hint or reveal.Team Name GeneratorGenerate catchy team names for sports, work, trivia nights and gaming, with your own keyword.Business Name GeneratorTurn a keyword and industry into brandable business name ideas, with a .com check link.Charades GeneratorRandom charades words by category and difficulty, with a round timer, team scores and kids mode.