This step, moving a single disc from peg A to peg B, is trivial. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n−1. move n−1 discs from B to C so they sit on disc n.number the discs from 1 (smallest, topmost) to n (largest, bottommost).label the pegs A, B, C-these labels may move at different steps.The following procedure demonstrates this approach. Recursive solutionĪ key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above. With this extra constraint, and the obvious rule of never undoing your last move, there is only one move at every turn. Now, add the constraint that no odd disk may be placed directly on an odd disk, and no even disk may be placed directly on an even disk. If n is odd, the first move is from the Start to the Finish peg, and if n is even the first move is from the Start to the Using peg. Equivalent Iterative SolutionĪnother way to generate the unique optimal iterative solution, is to number the disks 1 through n, largest to smallest. In each case, a total of 2 n-1 moves are made.
make the legal move between pegs B and C.make the legal move between pegs A and C.make the legal move between pegs A and B.It should perhaps be noted that this can be rewritten as a strikingly elegant set of rules: Simpler statement of iterative solutionĪlternating between the smallest and the next-smallest disks, follow the steps for the appropriate case: Doing this will complete the puzzle using the fewest number of moves to do so. 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). The following solution is a simple solution for the toy puzzle.Īlternate moves between the smallest piece and a non-smallest piece. The number of moves required to solve a Tower of Hanoi puzzle is 2 n -1, where n is the number of disks. The game seems impossible to many novices, yet is solvable with a simple algorithm. The puzzle can be played with any number of disks, although many toy versions have around seven to nine 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 or 18,446,744,073,709,551,615 turns to finish. It is not clear whether Lucas invented this legend or was inspired by it. 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 rules of the puzzle, since that time. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The puzzle was first publicized in the West by the French mathematician Édouard Lucas in 1883. 5 General shortest paths and the number 466/885.2.5 Logical analysis of the recursive solution.2.2 Simpler statement of iterative solution.
0 kommentar(er)
