Home › Guides › Tower of Hanoi

Tower of Hanoi: the classic puzzle, the card games, and the variants

By Decks editorial · last updated 2026-10-05

The Tower of Hanoi puzzle was published by the French mathematician Édouard Lucas in 1883: move a tower of discs to another peg, one disc at a time, never putting a larger disc on a smaller one. With three pegs and n discs, the minimum is 2ⁿ − 1 moves. The name also covers two card games: the classic tower played with cards, and a shuffled nine-card patience usually spelled Tower of Hanoy. This guide covers rules, history, variants and where to play. Disclosure: deckgames.app is the website of Decks, an iPhone card-game app that includes Tower of Hanoi.

Play the Tower of Hanoi game with cards in Decks: three to twelve cards, a four-place mode, and Two Towers. iOS only. Free to download; daily game limit without Premium.

Scan with your phone to install

The classic puzzle (rules in one minute)

The classic Tower of Hanoi puzzle is simple to state. You have three pegs and a stack of discs, largest at the bottom and smallest on top, all on one peg. Move the whole stack to another peg. You may move only one disc at a time, only the top disc of a peg, and never onto a smaller disc. That's all there is to it.

The three rules, as they are usually stated:

1. Move one disc at a time.
2. A move takes the top disc from one peg and places it on another peg, either an empty one or on top of other discs.
3. A disc may never be placed on a smaller disc.

The peg you start on, the peg you finish on and the third, "spare" peg are interchangeable in principle; most versions name a target peg, while card versions such as the one in Decks accept the tower on any place other than the one it started on.

Minimum moves: 2ⁿ − 1

With three pegs, the minimum number of moves for n discs is 2ⁿ − 1. Each extra disc doubles the work and adds one: three discs take 7 moves, eight take 255, ten take 1,023.

The growth is the point of the puzzle. Ten discs are a calm afternoon; the 64 discs of the legend (see the history section) would take 2⁶⁴ − 1 moves, which at one move per second is about 585 billion years. A separate minimum-moves guide, with the formula worked through and the four-peg numbers in full, is planned.

The recursive idea, in plain English

To move a tower of n discs from the start peg to the goal peg, first move the top n − 1 discs out of the way onto the spare peg, then move the largest disc to the goal, then move the n − 1 discs back on top of it. Moving those n − 1 discs is the same puzzle, one disc smaller, so you apply the same idea again, all the way down to a single disc.

That gives the count directly. If T(n) is the minimum for n discs, then T(n) = 2 × T(n − 1) + 1, with T(1) = 1. For four discs: move three to the spare (7 moves), move the largest (1 move), move three back on top (7 moves), 15 in all. Unroll the recurrence and you get 2ⁿ − 1, and no shorter solution exists, because the largest disc cannot move until every other disc is stacked on the spare peg.

The iterative tip: move the smallest every other turn

You don't need to think recursively to play perfectly. On every odd-numbered move (1st, 3rd, 5th…), move the smallest disc, always in the same direction around the pegs. On every even-numbered move, make the only legal move that doesn't involve the smallest disc; there is always exactly one.

The direction depends on the number of discs. With an odd number, the smallest disc's first move goes straight to the goal peg; with an even number, it goes to the spare peg first. For three discs the opening runs: smallest disc to the goal, middle disc to the spare, smallest disc onto the middle disc. Follow the rule and you finish in exactly 2ⁿ − 1 moves.

A short history (1883)

The puzzle — also called the Hanoi tower or Towers of Hanoi — was invented by Édouard Lucas, a French mathematician, and first presented in 1883 as a game "brought from Tonkin by Professor N. Claus (de Siam), Mandarin of the College of Li-Sou-Stian". The professor's name is an anagram of "Lucas d'Amiens" (Lucas was born in Amiens), and "Li-Sou-Stian" is an anagram of Saint Louis, the Paris lycée where he taught.

Lucas (1842–1891) is better known among mathematicians for number theory, including the Lucas sequence that bears his name and work on testing whether large numbers are prime. He wrote extensively on recreational mathematics, and the tower later appeared in a booklet (1889) and in a posthumously published volume of his Récréations mathématiques. The Puzzle Museum holds and describes an original 1883 set and leaflet; links are in the references.

The legend of the 64 golden discs

The leaflet that came with the game told a story, and it should be read as a story: in the great temple at Benares, priests move 64 discs of pure gold between three diamond needles according to the same rules, and when the last disc is moved, the world will end. Wikipedia describes the instruction booklet as giving the game's "purported" origins and notes that many variations of the legend exist (some set it in a monastery, some in Hanoi itself).

The legend's arithmetic is real even if the temple is not. 2⁶⁴ − 1 is 18,446,744,073,709,551,615 moves; at one move per second that's roughly 585 billion years, about 42 times the estimated age of the universe. There is no historical evidence for the temple, and we don't present it as anything other than the sales story printed with the set.

Four pegs and other mathematical variants

Adding a fourth peg cuts the number of moves sharply, and the best method for it took far longer to settle than the three-peg puzzle. The four-peg version is known as Reve's puzzle; the standard method, the Frame–Stewart algorithm, dates from 1941, and Thierry Bousch proved it optimal for four pegs in 2014.

Frame–Stewart works like this: pick a number k, move the top k discs to a spare peg using all four pegs, move the remaining n − k discs to the goal using only the three pegs still available, then move the k discs on top. Choosing the best k for each n gives the move counts listed in the OEIS as sequence A007664: 1, 3, 5, 9, 13, 17, 25, 33, 41, 49 for one to ten discs, and 81 for twelve.

Decks shows the same numbers in its four-place mode: 41 moves for nine cards, 49 for ten and 81 for twelve. Compare that with three places, where nine cards need 511 moves. The catch is that the simple "move the smallest every other turn" rule no longer works: you have to decide how to split the tower, and a poor split early on costs dozens of moves later.

For five or more pegs, whether Frame–Stewart is always optimal is still treated as an open question. One thing to watch if you read around: as of 5 October 2026, Wolfram MathWorld's entry still says no four-peg algorithm has been proved minimal, a statement that predates Bousch's paper.

Cyclic, linear, magnetic and two-colour towers

In Linear Hanoi, a disc may only move to the neighbouring peg, so nothing jumps straight from the left peg to the right one. Moving a stack from one end to the other then takes 3ⁿ − 1 moves, and the solution passes through every legal arrangement of the discs.

In Cyclic Hanoi, the three pegs sit in a circle and every move must go clockwise. The rules look almost the same as the classic puzzle, but the solution is longer and was the subject of its own papers, such as Gedeon's 1996 iterative solution.

In the Magnetic Tower of Hanoi, each disc has a north and a south face, usually shown in two colours. A disc flips over every time it moves, and you may not place it so that like poles touch. That one rule changes which moves are legal at every step.

The Bicolor Towers of Hanoi has two discs of every size, one black and one white, arranged in two towers of alternating colour; the goal is two single-colour towers. Wikipedia notes it was set for school pupils at the French mathematical games championship in 1988, and Chaugule published a recursive solution in 2015. It's a different puzzle from Two Towers in Decks, described below, where each tower is a single colour from the start and the goal is to swap them.

Tower of London: related, but not the same game

The Tower of London is a test from neuropsychology, introduced by Tim Shallice in 1982 to study planning. It uses coloured balls on pegs of different heights, and the person taking the test has to reach a target arrangement in a set number of moves. It borrows the feel of the Tower of Hanoi, but the pieces, the rules and the purpose all differ, and its results are interpreted by clinicians. It is not a variant you can "play" in the same way, and we mention it here only because the names are often confused.

Tower of Hanoi with cards — two different games

"Tower of Hanoi with cards" can mean two different games. One is the classic Lucas puzzle with ranked cards standing in for discs: the tower starts in order and you move it. The other is a nine-card patience, usually spelled Tower of Hanoy, which starts from a shuffled deal and asks you to build the tower. Decks plays the first: the classic ordered tower, not the shuffled nine-card deal.

Checked 5 October 2026; sources are in the references.

The classic stacked tower (the Decks version)

This is Lucas's puzzle with cards: the ace is the smallest disc and higher cards are larger discs. Take n cards of one suit and stack them on one place with the highest card at the bottom and the ace on top; the other places are empty. On each move, take the top card of any place and put it on an empty place or on a higher card. A lower card goes on a higher one, never the other way round. You win when the whole tower stands on any other place.

Because the start is always the same ordered tower, every game can be won, and the three-place minimum is exactly 2ⁿ − 1, so three cards take 7 moves and eight cards take 255. The iterative tip above works unchanged: move the ace on every odd-numbered move, always in the same direction, and make the only other legal move in between.

In Decks the tower comes in nine sizes: three to eight cards on three places, and nine, ten or twelve cards on four places. The app shows the minimum for each size, lets you undo moves freely and keeps a history of your solutions and their length. A step-by-step how to play with cards — separate guide next. Until then, the three-disc opening in the iterative tip above shows how a perfect game starts.

Tower of Hanoy, the nine-card patience

Tower of Hanoy is a patience for nine cards, usually Ace to 9 or 2 to 10. You shuffle them and deal three columns of three, face up, overlapping so every card is visible. Only the exposed card of a column can move, and only onto a higher card or into an empty column. You win by gathering all nine cards into one column in order, with the highest card at the buried end and the lowest card exposed.

The rules go back at least to Helen Coops's 100 Games of Solitaire (1939), as summarised by Wikipedia, which also cites George Hervey for the Ace-to-9 version. The spelling "Hanoy" is old and its origin is unclear; the game also turns up as Tower of Pisa, One-To-Nine or Tower Puzzle. Older books describe the overlapped columns from the other end, so you may read about moving the "bottom" card of a column; it's the same exposed card. Grid layouts in some apps build the column upwards instead of downwards.

Two things set it apart from the classic puzzle. First, the start is random, so 2ⁿ − 1 isn't a target: a lucky deal can be much shorter than the 511 moves nine discs would need, and the minimum depends on where the cards land. Second, solvability depends on the deal and the exact rules used. Some rules pages give a win rate or say every deal can be won; we couldn't find the method behind those claims, so we don't repeat them.

Decks does not include this shuffled patience.

Two Towers

Two Towers is a second Tower of Hanoi in Decks: a black tower and a red tower stand on separate places, each running from the highest card down to the ace, and you have to swap them. To make the swap possible, a card may go on a card of equal or higher rank, so a black 2 may sit on a red 2. A lower card on a higher one is still forbidden.

Without the equal-rank rule there would be no way to complete the swap, because neither tower could pass through the other. Free places matter even more here than in the single tower: with three places, three pairs take 25 moves; with four places, 13. Decks offers eight sizes of Two Towers on three or four places, each with its minimum shown. The full table is on the Tower of Hanoi game page.

Play at home with a real deck

All you need is one suit from an ordinary deck and a bit of table space. Take the ace, 2 and 3 for a first game, stack them in order, and move the tower using the card rule; seven moves is perfect.

1. From one suit, take n cards in sequence. Beginners: ace, 2 and 3. The ace counts as the lowest card.
2. Mark out three places on the table, or four for the harder mode.
3. Stack the cards on the left place with the highest at the bottom and the ace on top. Leave the other places empty.
4. Move only the top card of a place, onto an empty place or onto a higher card.
5. You win when the whole tower is on a different place. With three places, a perfect score is 2ⁿ − 1 moves.

A few practical tips:

• Keep count with a pencil tally or a counter app, so you can compare your total with the minimum.
• Add one card at a time. Each one roughly doubles the length, so going from four cards (15 moves) to six (63) is a big step.
• For the four-place mode, try nine cards and aim for 41 moves. Expect to miss the first few times.
• For a home version of Two Towers, take the ace to 3 of a black suit and the ace to 3 of a red suit, build two towers on separate places, keep the third place empty, and allow equal ranks to stack. Three pairs on three places take 25 moves at best.

To try the nine-card patience instead, take the ace to 9 of one suit (or 2 to 10), shuffle, and deal three overlapping columns of three, face up. Move exposed cards onto higher cards or into empty columns until one column holds all nine in order.

Where to play

For a classic Tower of Hanoi simulation in a browser, MathsIsFun and Cut the Knot are free and straightforward. For the nine-card patience, PySolFC is free on desktop, and solitaire.org runs it in a browser. To play a Tower of Hanoi game (or Towers of Hanoi game) with cards on iPhone, Decks is one option.

Disclosure: this list is published on deckgames.app, the website of Decks (developer Gleb Tkatchouk). We've included Decks as one option among several and haven't put it first. Everything below was checked on 5 October 2026; prices, ads and features can change, so check the listing before you install or buy. We noted which variant each one plays, the platform, and price and ads as stated on the page or store listing. We did not measure traffic or popularity, and the order is by platform, not a ranking.

On the web

The browser versions split cleanly by variant. MathsIsFun and Cut the Knot teach the classic disc puzzle; braincurls is the one we found that plays the ordered tower with cards. Solitaire.org and Novel Games play the shuffled nine-card patience under the Hanoi or Hanoy name, so check which one you've opened before you compare your move count with 2ⁿ − 1.

On phones

On iOS there are several small disc-puzzle apps, including Just Hanoi and Hanoi Tower Puzzle, neither of which had US ratings when we checked. Decks is a Hanoi game on iPhone that plays the tower with cards and adds a four-place mode and Two Towers. Decks is not available on Android; on Android the Atagan app is a free disc version that carries ads.

On desktop and on the table

If you want the nine-card patience on a computer, PySolFC is free and open source; SolSuite and Pretty Good Solitaire are paid collections that include it. For the physical classic, wooden sets with seven or nine rings are widely sold; the Creative Crafthouse listing above is one example, not a recommendation over others.

Where Decks fits (honest)

Decks is a card-game app for iPhone with 14 games: 9 solitaires and 5 puzzles. Tower of Hanoi is one of the puzzles, and Two Towers is a separate game in the app. How Decks compares, good and bad.

If that sounds like your kind of puzzle, you can find Decks on the App Store. It's free to download, with a daily game limit without Premium. If you'd rather play in a browser or with a real deck, the options above work just as well for learning the puzzle.

Tower of Hanoi in computer science and psychology

In computer science, the Tower of Hanoi problem is the textbook example of recursion: a problem solved by reducing it to a smaller copy of itself. In psychology, it's a standard task in research on problem-solving and planning, alongside its clinical cousin, the Tower of London.

Programming courses use it because the recursive solution is only a few lines long and the move count, 2ⁿ − 1, can be proved from the same reasoning. The puzzle also links to binary numbers and Gray codes: counting up in Gray code tells you which disc to move at each step. If you draw every legal arrangement as a point and connect arrangements one move apart, the picture approaches the Sierpiński triangle as discs are added.

Outside teaching, Wikipedia lists a backup rotation scheme for tapes based on the puzzle's pattern, and a study in which Argentine ants found short paths through a maze shaped like the puzzle's state graph. In 2025, Apple researchers used it, among other puzzles, to test how well large language models cope as problems get longer.

Psychologists have used the Tower of Hanoi for decades to study how people plan, and Zhang and Norman (1994) showed that the same puzzle becomes easier or harder depending on how it is represented. The Tower of London test, mentioned above, is used by clinicians to assess planning. None of this means that playing a puzzle game improves memory or protects against any condition, and we make no such claim for Decks or for any other app.

Frequently asked questions

What is the Tower of Hanoi problem? Moving a stack of n discs between pegs under the three rules above — usually with the minimum of 2ⁿ − 1 moves on three pegs. The same problem is a standard recursion exercise in computer science.

Is Tower of Hanoi the same as Tower of Hanoy solitaire? No. The Tower of Hanoi starts with an ordered tower that you move to another place. Tower of Hanoy is a nine-card patience that starts from a shuffled deal in three columns, and you build the ordered column yourself.

What is the minimum number of moves for the Tower of Hanoi? With three pegs, 2ⁿ − 1 for n discs: 7 for three, 15 for four, 255 for eight, 1,023 for ten. With four pegs it is much lower, for example 41 for nine discs.

Who invented the Tower of Hanoi? The French mathematician Édouard Lucas, who published it in 1883 under the name "N. Claus (de Siam)", an anagram of "Lucas d'Amiens".

Is the temple legend true? No. It's a story printed with the original 1883 game. There's no historical evidence for the temple or the 64 golden discs.

Is there a trick to solving it? With three pegs, yes: move the smallest disc on every other move, always in the same direction, and make the only other legal move in between. With four pegs there is no simple rule of this kind.

Is the Frame–Stewart method optimal for four pegs? Yes. Thierry Bousch proved it in 2014. For five or more pegs, the question is still generally treated as open.

Can I play Tower of Hanoi with a normal deck of cards? Yes. Take the ace, 2 and 3 of one suit, stack them with the ace on top, and move the tower to another place one card at a time, never putting a higher card on a lower one. Seven moves is perfect.

Does Decks include Tower of Hanoi? Yes. Decks for iPhone includes the classic tower with cards in nine sizes, a four-place mode and Two Towers. It doesn't include the shuffled nine-card patience.

Why do some sites say every deal is winnable? Those claims are about the nine-card patience, which starts from a shuffled deal, and we couldn't find the method behind them, so we don't repeat them. The classic tower is a different case: from its ordered start it can always be solved, in 2ⁿ − 1 moves with three places.

Is the Tower of Hanoi the same as the Tower of London? No. The Tower of London is a neuropsychological test of planning with coloured balls on pegs of different heights. It's related in spirit but has different pieces, rules and purpose.

References

All links were checked on 2026-10-05 unless noted.

1. Wikipedia, Tower of Hanoi: rules, origins, the legend, 2ⁿ − 1, Frame–Stewart and Bousch, linear, cyclic, magnetic and bicolor variants, applications. Checked 2026-10-05.
2. Wikipedia, Tower of Hanoy: the nine-card patience, after Coops (1939) and Hervey. Checked 2026-10-05.
3. Wikipedia, Tower of London test: Shallice (1982). Checked 2026-10-05.
4. The Puzzle Museum, The Tower of Hanoi: the original 1883 set and leaflet, "N. Claus (de Siam)". Checked 2026-10-05.
5. MacTutor History of Mathematics, Édouard Lucas. Checked 2026-10-05.
6. Wolfram MathWorld, Tower of Hanoi: mathematics of the puzzle; its four-peg status predates Bousch (2014). Checked 2026-10-05.
7. OEIS, A007664: Frame–Stewart move counts for four pegs. Checked 2026-10-05.
8. Bousch, T. (2014). La quatrième tour de Hanoï. Bulletin of the Belgian Mathematical Society – Simon Stevin, 21(5), 895–912. doi:10.36045/bbms/1420071861.
9. Frame, J. S. and Stewart, B. M. (1941). Solution to advanced problem 3819. American Mathematical Monthly, 48(3), 216–219. doi:10.2307/2304268.
10. Chaugule, P. V. (2015). A Recursive Solution to Bicolor Towers of Hanoi Problem. Recreational Mathematics Magazine, 4, 37–48.
11. Practical Gaming Center, Tower of Hanoi Solitaire rules. Checked 2026-10-05.
12. PySolFC, Tower of Hanoy rules; SolSuite, Tower of Hanoi; Pretty Good Solitaire, Tower of Hanoi. Checked 2026-10-05.
13. Decks, Tower of Hanoi game page: rules, sizes, minimum moves, Two Towers. Checked 2026-10-05.
14. Decks on the App Store: availability, ratings, daily game limit without Premium. Checked 2026-10-05.
15. Store listings and web pages in the where-to-play table, as linked there. Checked 2026-10-05.

Play the Tower of Hanoi game with cards in Decks: three to twelve cards, a four-place mode, and Two Towers. iOS only. Free to download; daily game limit without Premium.

Scan with your phone to install