Move m − 1 disks from the source to the spare peg, by the same general solving procedure.number the disks from 1 (smallest, topmost) to n (largest, bottom-most).Īssuming all n disks are distributed in valid arrangements among the pegs assuming there are m top disks on a source peg, and all the rest of the disks are larger than m, so they can be safely ignored to move m disks from a source peg to a target peg using a spare peg, without violating the rules:.Each of thus created sub-problems being "smaller" guarantees that the base case(s) will eventually be reached. The key to solving a problem recursively is to recognize that it can be broken down into a collection of smaller sub-problems, to each of which that same general solving procedure that we are seeking applies, and the total solution is then found in some simple way from those sub-problems' solutions. Illustration of a recursive solution for the Towers of Hanoi puzzle with 4 disks
The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above. Place the disk on the non-empty peg.Ĭonsidering those constraints after the first move, there is only one legal move at every subsequent turn. There will sometimes be two possible pegs: one will have disks, and the other will be empty.No even disk may be placed directly on an even disk.No odd disk may be placed directly on an odd disk.If n is even, the first move is from peg A to peg B.If n is odd, the first move is from peg A to peg C.Number the disks 1 through n (largest to smallest). Equivalent iterative solutionĪnother way to generate the unique optimal iterative solution: In each case, a total of 2 n − 1 moves are made. make the legal move between pegs B and C (in either direction),.make the legal move between pegs A and C (in either direction),.make the legal move between pegs A and B (in either direction),.Doing this will complete the puzzle in the fewest moves. When the turn is to move the non-smallest piece, there is only one legal move. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). Iterative solutionĪnimation of an iterative algorithm solving 6-disk problemĪ simple solution for the toy puzzle is to alternate moves between the smallest piece and a non-smallest piece. This is precisely the nth Mersenne number. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2 n − 1, where n is the number of disks. The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. In some versions other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day. The temple or monastery may be said to be in different parts of the world-including Hanoi, Vietnam-and may be associated with any religion. For instance, in some tellings the temple is a monastery, and the priests are monks. There are many variations on this legend. If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves it would take them 2 64 − 1 seconds or roughly 585 billion years to finish, which is about 42 times the current age of the universe. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time.
There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Numerous myths regarding the ancient and mystical nature of the puzzle popped up almost immediately. The puzzle was invented by the French mathematician Édouard Lucas in 1883.