| Tower Of Hanoi |
Article Index for Tower Of |
Website Links For Tower |
Information AboutTower Of Hanoi |
| CATEGORIES ABOUT TOWER OF HANOI | |
| mechanical puzzles | |
| articles with example haskell code | |
| articles with example scheme code | |
|
The Tower of Hanoi (also called '''Towers of Hanoi''') is a Mathematical Game or Puzzle . It consists of three pegs, and a number of discs of different sizes which can slide onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape. The object of the game is to move the entire stack to another peg, obeying the following rules:
ORIGINS The puzzle was invented by the French mathematician Edouard Lucas in 1883 . There is a legend about an India n temple which contains a large room with three time-worn posts in it surrounded by 64 golden discs. The priests of Brahma , acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle. 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. It is not clear whether Lucas invented this legend or was inspired by it. If the legend were true, and if the priests were able to move discs at a rate of 1 per second, using the smallest number of moves, it would take them 264 − 1 seconds or roughly 585 Billion years. The Universe is currently about 13.7 Billion Years Old . There are many variations on this legend. For instance, in some tellings, the temple is a Monastery and the priests are Monk s. 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 . 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. SOLUTION Most toy versions of the puzzle have 8 discs. The game seems impossible to many novices, yet is solvable with a simple Algorithm : Recursive algorithm
To move n discs from peg A to peg B: # move n−1 discs from A to C. This leaves disc #n alone on peg A # move disc #n from A to B # move n−1 discs from C to B so they sit on disc #n The above is a Recursive Algorithm : to carry out steps 1 and 3, apply the same algorithm again for ''n''−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for ''n'' = 1. This step, moving a single disc from peg A to peg B, is trivial. The Tower of Hanoi is a problem often used to teach beginning programming, in particular as an example of a simple recursive algorithm. It is also an example of an Exponential Time algorithm — for all but the smallest number of discs, it will take an impractically huge amount of time, even on the fastest computers in the world. There is no way to improve on this, because the minimum number of moves required to solve the puzzle is exponential in the number of discs. Using Recurrence Relation s, we can compute the exact number of moves that this solution requires, which is , where is the number of discs. This result is obtained by noting that steps 1 and 3 take time and step 2 takes constant time, giving . A simple and elegant implementation in Haskell (a recursive, Functional programming language) is as follows: hanoi n = hanoi' n 1 2 3 hanoi' 0 _ _ _ = {Link without Title} hanoi' n f i t = (hanoi' (n-1) f t i) ++ (f, t) : (hanoi' (n-1) i f t) where ''n'' is the number of discs; this program returns a list of all the moves required. Explanation of the algorithm A more human-readable version of the same algorithm follows: # move disc 1 to peg B # move disc 2 to peg C # move disc 1 from B to C, so it sits on 2 You now have 2 discs stacked correctly on peg C, peg B is empty again # move disc 3 to peg B # repeat the first 3 steps above to move 1 & 2 to sit on top of 3 Each time you re-build the tower from disc ''i'' up to 1, move disc ''i+1'' from peg A, the starting stack, and move the working tower again. Therefore, We can observe and say that number of moves required to move n number of plates will be (2 to the power n) − 1. Practical algorithm Alternately move disc 1 and one of the larger discs. If two of the larger discs are available, always move the smaller one onto the larger. When you move an odd-numbered disc, always move it one peg clockwise; when you move an even-numbered disc, always move it one peg counterclockwise. An even easier way to remember this solution is to notice that the smallest disk gets every second move, and always moves in the same direction. In between smallest disk moves, there is only one legal move that does not involve moving the smallest disk again. In spite of the simplicity of the algorithms, the shortest way to solve the problem with ''n'' discs takes 2''n''−1 moves. It is not known in general how many moves are required to solve the puzzle when there are more than 3 pegs. Thus it is not practical by sequential advancement to determine the position on three pegs of a large set of disks after some arbitrary large number of advancements. Binary solutions Disk positions may be determined more directly from the Binary (base 2) representation of the move number (the initial state being move #0, with all digits 0, and the final state being #2''n''−1, with all digits 1), using the following rules:
For example, in an 8-disc Hanoi:
One could thus easily compute the positions of disks in a set of eighty disks after some Mole of advancements, if the margin were but large enough to contain it. |
|
|