The Tower of Hanoi Game

The objective of this game is to move all the discs from the left peg to the right peg in as few moves as possible. To move the discs, simply click and drag. Only one disc may be moved at a time. A disc may be placed on top of a larger disc, or on an empty peg, but NOT on top of a smaller disc.

Select AutoSolve to watch the computer solve the puzzle. The Speed scrollbar determines how fast the computer moves.

There is a HINT at the bottom of this page.

About the Tower of Hanoi Puzzle

This puzzle was originally designed and sold as a toy by the French mathematician Edouard Lucas in 1883. It was based on the mythical story of the Tower of Brahma.

It was said that in the Indian City of Benares, beneath a dome which marked the centre of the world, there was to be found a brass plate in which were set three diamond needles, "each a cubit high and as thick as the body of a bee." It was also said that God had placed sixty-four discs of pure gold on one of these needles at the time of Creation. Each disc was said to be of different size, and each was said to have been placed so that it rested on top of another disc of greater size, with the largest resting on the brass plate at the bottom and the smallest at the top. This was known as the Tower of Brahma.

Within the temple there were said to be priests whose job it was to transfer all the gold discs from their original needle to one of the others, without ever moving more than one disc at a time. No priest could ever place any disc on top of a smaller one, or anywhere else except on one of the needles.

When the task had been completed, and all sixty-four discs had been successfully transferred to another needle, it was suggested that the "tower, temple, and Brahmins alike will crumble into dust, and with a thunder-clap the world will vanish."

[Quotations from W.W.R. Ball, Mathematical and Recreational Essays - The Macmillan Co., NY 1939.]

Curiously, even if this prophecy were to be true, readers would still be able to rest assured that the world would be unlikely to end just yet.

If one were to assume that the priests worked on their task for 24 hours a day, and somehow managed to transfer the gold discs at the rate of one per second (without ever making a mistake), it would still take (2⁶⁴) -1 seconds before the world would come to its predicted end. (See HINT.) That might not initially sound like a very long time, but in fact it equates to some 18, 446, 744, 073, 709, 551, 615, seconds, which itself equates to nearly six hundred billion (600, 000, 000, 000) years; an extremely optimistic prophecy.

To put this time into some perspective, it is now widely perceived that it is only approximately 10, 000, 000, 000 years since time and space began with the Big Bang. The sun, a mere four and a half billion years old, is believed to have burned approximately half of its hydrogen supply into helium, and has can therefore expect to continue to shine for about another six billion years, by which time life on earth as we know it will long since have ceased to exist. As the concentration of helium at the Sun's core increases, so too will its luminosity. This, it is predicted, will lead to a quite devastating acceleration of greenhouse effect.

However, there are alternative scenarios. It is just possible that another star could pass near enough to Earth to move it out its current solar orbit. The chances of this happening before our Sun turns into a red giant are currently rated at about one in a hundred thousand, although the chances of human life surviving the ensuing fall in temperature are not good at all. The most optimistic outlook for long term human survival is put at odds of approximately one in three million. In this scenario, rather that being slung out into deep space, the Earth would find itself in a new habitable orbit around another star, a red dwarf. And in this case, life could conceivably last for trillions of years, or perhaps until the fabled priests of Benares have finally completed their task.

[Source for information pertaining to evolution of the universe: The Five Ages of the Universe by Fred Adams and Greg Laughlin.]

HINT

If the number of discs is even, try moving the first disc to the middle peg. If the number of discs is odd, try moving the first disc to the right peg.

In general, the minimum number of moves required to move n discs to the right peg (or even the middle peg) is 2⁰ + 2¹ + 2² + 2³ + ... + 2^(n-1). This can be expressed by the formula (2ⁿ) -1. [ This proof can be found in Mathematics Teacher, vol. 45, page 522, 1952. ] Thus 2 discs can be transferred to another peg in 3 moves, 3 in 8, 4 in 15, and so on.