Tower of Hanoi: 8 Disks Need 255 Moves on Three Pegs

Where it lands

The fewest moves for a stack of n disks on three pegs is 2ⁿ − 1, so 8 disks take 255 moves and the legend's 64 disks take 18,446,744,073,709,551,615. Édouard Lucas gives that 64-disk count in Récréations mathématiques, volume 3 (1893), and puts the time at more than five billion centuries; at one move a second, our arithmetic gives about 585 billion years.

Sections on this sheet (5)

1. The puzzle
2. How long 64 disks take
3. Where the puzzle comes from
4. The legend's 64 disks
5. Four stools: the Reve's puzzle

In 1893, Édouard Lucas told of a temple tower of 64 golden disks that would take ages to move. Under the legend sits a practical question, the fewest moves a stack of disks needs, and Lucas already stated the rule that answers it: each added disk doubles the count, then adds one. The moves themselves, and the argument that no shorter route exists, are in the fold below, after the eight-disk puzzle in standard form.

In standard form: (Lucas, Récréations mathématiques, vol. 3, 1893, p. 55)

1. P1Premise 1:Eight disks of different sizes sit on peg A, largest at the bottom.
2. P2Premise 2:Move one disk at a time, always the top disk of a peg.
3. P3Premise 3:Never put a larger disk on a smaller one.
4. ? QQuestion:In what order do the 255 moves go, and why can't it be done in fewer?

Wide figure: scroll it sideways, or open it full size.

The puzzle

Lucas describes the original toy as eight wooden pieces, each pierced through the center and threaded onto one of three nails fixed to a small board. Your task is to move the whole tower to another peg under two rules, which the tables below give along with the start and finish positions.

Before you open the solution, decide how few moves the transfer needs and in what order the disks should travel.

Show the checked solution (1 of 2)

Checked solution

∴ Eight disks need 255 moves, and only one order of 255 moves works.

We checked it by exhaustive search. A breadth-first search, which tries every possible move from every position it reaches, visited all 6,561 ways to place 8 disks on three pegs, found 255 as the length of the shortest route to peg C, and found exactly one route of that length. A second search, written separately and run backward from the finished tower, agrees for every stack from 1 to 8 disks.

The method that produces those 255 moves works for any number of disks:

1. Move the top 7 disks from A to the spare peg B, using C as the spare.
2. Move disk 8 from A to C.
3. Move the 7 disks from B onto disk 8, using A as the spare.

Steps 1 and 3 are the same puzzle with one disk fewer, so each is solved in exactly the same way, all the way down to a single disk. If moves(n) stands for the count with n disks, then moves(n) = 2 × moves(n − 1) + 1. Starting from moves(1) = 1, the recurrence gives 1, 3, 7, 15, 31, 63, 127 and 255, which is 2ⁿ − 1; Lucas prints the same column, from 3 moves for two disks to 255 for eight.

Wide figure: scroll it sideways, or open it full size.

Move	Disk	From	To
1	1	A	C
2	2	A	B
3	1	C	B
4	3	A	C
5	1	B	A
6	2	B	C
7	1	A	C

Why no route can be shorter: disk 8 has to move at least once, and at the moment it leaves A, the other seven disks must all be sitting on the remaining peg, since none of them may rest beneath it or on top of it. Assembling them there is the complete seven-disk puzzle, and so is bringing them back on top of disk 8 afterward. That requires at least 2 × moves(7) + 1 moves, and the identical argument applies at every smaller size.

The decoy fails at its second move. With disk 1 already on B, disk 2 cannot join it, because it would land on a smaller disk. Parking seven disks on a single peg means stacking them in size order, and building that stack is itself the seven-disk puzzle.

Wide figure: scroll it sideways, or open it full size.

Lucas adds a shortcut that he credits to Raoul Olive, the inventor's nephew: the smallest disk moves on every other move, always traveling in the same direction around the pegs. On each of the remaining moves, exactly one legal move leaves the smallest disk alone, so the whole solution can be played without planning ahead.

The first move sets the direction: with an even number of disks, such as 8, disk 1 goes first to the spare peg B, and with an odd number, such as 3, it goes straight to C. In the 255-move solution, disk 1 moves 128 times, disk 8 moves only once, and each disk moves half as often as the next smaller one.

The 1893 text also remarks that the game mirrors counting in binary numbers. One way to see this in the 255 moves: number the moves from 1, and the disk moved on move m is one more than the number of times m can be halved exactly. Move 1 shifts disk 1, move 2 shifts disk 2, move 4 shifts disk 3, and move 128, the exact midpoint, shifts disk 8.

How long 64 disks take

The count more than doubles with each disk, so the time grows fast. At one move a second, 8 disks take 255 seconds, or 4 minutes 15 seconds, which matches Lucas's “plus de quatre minutes,” more than four minutes, while the 1885 English version simply says four minutes. A tower of 20 disks would keep you busy for about 12 days without a break, and a tower of 32 disks would outlast a human lifetime at roughly 136 years.

Wide figure: scroll it sideways, or open it full size.

For 64 disks, the count is 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves, and therefore the same number of seconds. Dividing by a year of 365.25 days, or 31,557,600 seconds, gives about 585 billion years. In centuries, that is about 5.8 billion, consistent with Lucas's “plus de cinq milliards de siècles,” more than five billion centuries.

Lucas connects the same number to two other amusements. The number turns up again, he notes, in the theory of the baguenaudier, a ring puzzle, when it has 64 rings, and it equals the total of grains in the familiar chessboard reward story, where one grain on the first square doubles on each following square through the sixty-fourth.

Where the puzzle comes from

The earliest text we read is an English article by Lucas, “Calculating-Machines,” in The Popular Science Monthly, volume 26 (November 1884 to April 1885). It reports that the game “was published toward the end of last year,” gives the same rules and the same column of move counts up to 255, and describes the temple story as “an ancient Indian legend.”

Its version of the legend is shorter than the one in Lucas's 1893 book, told below: the sacred tower of Brahma has sixty-four stories “of fine gold set with diamonds,” with no diamond needles and no named informant.

The tower appears there inside a discussion of binary weights. Pawns weighing 1, 2, 4 grammes and so on, up to 512, can together weigh any whole number of grammes up to 1,023, and, after one sentence on the ring puzzle, the article turns from that binary abacus to the game.

The same three-panel engraving appears as figure 15 on page 56 of Lucas's 1893 volume. There, the game is credited to “le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian.” Lucas calls it a genuine Annamite puzzle that its maker did not bring back from Tonkin, “quoi qu'en dise le prospectus,” whatever the leaflet claims.

The legend's 64 disks

Lucas's 1893 book tells the legend at second hand. In that telling, a friend, “le mandarin N. Claus (de Siam),” reports seeing three diamond needles in the great temple of Benares, beneath the dome that marks the center of the world. On one of those needles, at the beginning of time, God placed 64 disks of pure gold, with the largest resting on the brass plate below.

Illustration

Priests take turns day and night, moving the tower from the first needle to the third while following the rules that Brahma imposed. When the work is finished, the story concludes, “la tour et les brahmes tomberont, et ce sera la fin des mondes !” In English: the tower and the Brahmins will fall, and the worlds will end. Lucas presents all of this as N. Claus's report, and the pages give no older source for the legend.

The section's last lines add a twist. Lucas writes that foreign manufacturers had recently seized on “our friend's” game and its legend, and he then states that the whole thing was “imaginé,” imagined, some time earlier at No. 56 rue Monge in Paris.

One number differs between the two texts. The 1885 English article says the 64-disk tower “will occupy five million centuries,” while the 1893 French book says more than five billion. Our arithmetic gives about 5.8 billion centuries, so the 1893 figure is the one consistent with the count of moves.

Four stools: the Reve's puzzle

In 1907, Henry Dudeney opened The Canterbury Puzzles with the same task played on four stools. His Reve places eight cheeses “of graduating sizes” on the stool at one end, and the goal is to move them all to the stool at the other end “by the moving of one cheese at a time,” “without ever putting any cheese on one that is smaller than itself.”

Dudeney's wording never states that only the top cheese may be lifted. In a pile where no cheese rests on a smaller one, any other choice would mean pulling a cheese out from underneath another, so we read his rule as the same top-disk rule used above.

Wide figure: scroll it sideways, or open it full size.

A fourth stool gives one more parking place. A tempting guess is that it cuts the work roughly in half, to about 128 moves. Like Knights and Knaves, this puzzle is small enough that every case can be checked: there are only 65,536 ways to place 8 cheeses on four stools.

Try it first: With four stools, what is the smallest number of moves for 8 cheeses?

Show the checked solution (2 of 2)

Checked solution

∴ Eight cheeses on four stools need 33 moves, not 128.

We checked it by exhaustive search over all 65,536 positions, and again with the separate backward search. Both give 33 moves, which matches Dudeney's published answer: “The 8 cheeses can be removed in 33 moves.” The search also counts 11,698 different shortest routes, whereas three pegs with 8 disks allow only one.

The plan that reaches 33 is the one now known as the Frame–Stewart method. First, park a pile of the smallest cheeses using all four stools; next, move the remaining cheeses with the three stools still available, which is the ordinary three-peg puzzle; finally, bring the parked pile back on top. For 8 cheeses, parking either 4 or 5 gives 33. Dudeney describes the same kind of plan for 10 cheeses, building piles of 6 and 3 for a total of 49 moves.

Wide figure: scroll it sideways, or open it full size.

Disks	Three pegs	Four pegs, by search	Four pegs, Frame–Stewart	Shortest routes, four pegs
1	1	1	1	1
2	3	3	3	2
3	7	5	5	2
4	15	9	9	22
5	31	13	13	40
6	63	17	17	18
7	127	25	25	2,468
8	255	33	33	11,698

Dudeney's other two answers, 49 moves for 10 cheeses and 321 for 21, also equal the Frame–Stewart values, but our search does not reach that far, so the CSV marks those two rows as not checked exhaustively. The searched rows cover 1 to 8 disks only, and this page makes no claim about larger towers on four pegs.

Push back:

The strongest objection is that a search up to 8 disks proves nothing general. The three-peg formula rests on the argument that the largest disk must move, and the search adds nothing to that argument; with four pegs the case is weaker still, because the table stops at 8, so it looks like an answer while it is only a sample. That objection is fair. It is why we claim only what the search covers: for four pegs and larger towers, this page states no general result.

• River crossing puzzle: Another puzzle where one thing moves at a time, and a search lists every shortest way.
• Gravity train: Another number you can work out on paper: how long a fall through the Earth takes.

Sources

1. Édouard Lucas, Récréations mathématiques, vol. 3 (Paris: Gauthier-Villars et fils, 1893), second recreation, “La Tour d’Hanoï” and “Les Brahmes tombent !”, pp. 55–59. https://archive.org/details/rcrationsmat03lucauoft Read: pages 55–59 in French, with the page numbers and figure 15 checked on the scanned pages.
2. Édouard Lucas, “Calculating-Machines,” The Popular Science Monthly, vol. 26 (New York: D. Appleton, November 1884 to April 1885). https://archive.org/details/popularsciencemo26newyuoft Read: the passages on binary weights and the Tower of Hanoi, in the scanned text; the figure as reproduced on Wikimedia Commons.
3. Henry Ernest Dudeney, The Canterbury Puzzles and Other Curious Problems (1907), no. 1, “The Reve’s Puzzle,” with its solution. Project Gutenberg eBook #27635. https://www.gutenberg.org/ebooks/27635 Read: puzzle no. 1 and its solution, full text.
4. B. M. Stewart and J. S. Frame, “3918,” The American Mathematical Monthly 48, no. 3 (March 1941): 216. doi:10.2307/2304268. https://doi.org/10.2307/2304268 Read: bibliographic record only.

Downloads: Minimum moves, three and four pegs (CSV) (file notes: source, version and license (JSON)) · The 64-disk count and time (JSON) (file notes: source, version and license (JSON)) · The 7 moves for 3 disks (JSON) (file notes: source, version and license (JSON))

Cite this page