![]() |
|
|
Iterative solutionAnimation of an iterative algorithm solving 6-disk problem A simple solution for the toy puzzle is to alternate moves between the smallest piece and a non-smallest piece. 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). 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. 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. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest moves.Pictures |
![]() Solution for 4 disks |
![]() Solution for 5 disks |
![]() Solution for 6 disks |
Video with solution for 8 disks |
Reviews![]() The puzzle was invented by the French mathematician Édouard Lucas in 1883. Numerous myths regarding the ancient and mystical nature of the puzzle popped up almost immediately. These myths are recounted in the monograph The Tower of Hanoi-Myths and Maths. ![]() 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. 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. ![]() According to the legend, when the last move of the puzzle is completed, the world will end. 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 264 − 1 seconds or roughly 585 billion years to finish, which is about 42 times the current age of the Universe. ![]() Nice graphics! Tower Of HanoiThis is precisely the nth Mersenne number! First, I had difficulties. But after several attempts, everything went very well. Simpler statement solutionFor an even number of disks:make the legal move between pegs A and B (in either direction), make the legal move between pegs A and C (in either direction), make the legal move between pegs B and C (in either direction), repeat until complete. For an odd number of disks: make the legal move between pegs A and C (in either direction), make the legal move between pegs A and B (in either direction), make the legal move between pegs B and C (in either direction), repeat until complete. In each case, a total of 2n − 1 moves are made. |