What is the famous Tower of Hanoi problem?

Answer 1

If you love puzzles, mathematics, or computer programming then the "Tower of Hanoi" problem is brain teaser designed just for you.

At first glance, the Tower of Hanoi problem appears to be a simple matter of trial and error. The problem consists of three wooden pegs. The center wooden peg contains 8 discs of varying size. The discs decrease in diameter from the bottom to top. For example, the bottom disc could be 8 inches in diameter and the disc on top of it could be 7 inches in diameter, continuing to the 8th disk, a 1 inch disc on the very top. At the beginning of the problem, the two remaining pegs do not contain any discs.

The goal of the Towers of Hanoi problem is to move all the discs from the center peg to one outside peg. Sounds easy, right? There are two rules that you must follow. Rule #1 is that you can move only one disc at a time. Rule #2 is that you can not place a larger disc on top of a smaller disc. This is the reason why there are three pegs in the problem as opposed to just two pegs.

The puzzle may be based on an Indian legend (Towers of Brahma) where (someplace in antiquity) there is a room with three posts having 64 disks. Brahmin priests are tasked with moving the disks from one post to another. When the task is done, the world will end. Based on moving the disks at one disk per second, this would take about 585 billion years. (18,446,744,073,709,551,615 moves)

Other variations of the legend exist.

---

The minimum number of moves for three pegs and n disks = (2^n) - 1, so for 8 disks, the number of moves should be 255. The first 3 moves are A1, B3, A3, followed by C1, A2, B1, A1.