The Tower of Hanoi (also called the problem of Benares Temple, Tower of Brahma or Lucas's Tower, and sometimes pluralized as Towers, or simply the pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:
Only one disk may be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. No disk may be placed on top of a disk that is smaller than it. With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks. The puzzle game was named after the capital city of today's Vietnam.
Origins The puzzle was invented by the French mathematician Édouard Lucas, first presented in 1883 as a game discovered by "N. Claus (de Siam)" (an anagram of "Lucas d'Amiens"), and later published as a booklet in 1889 and in a posthumously-published volume of Lucas's Récréations mathématiques. Accompanying the game was an instruction booklet, describing the game's purported origins in Tonkin, and claiming that according to legend, Brahmins at a temple in Benares have been carrying out the movement of the "Sacred Tower of Brahma", consisting of 64 golden disks, according to the same rules as in the game, and that the completion of the tower would lead to the end of the world. Numerous variations on this legend exist, regarding the ancient and mystical nature of the puzzle. At a rate of one move per second, the minimum amount of time it would take to complete the 64 disks would be 264 − 1 seconds or 585 billion years, roughly 42 times the estimated current age of the universe. There are many variations on this legend. For instance, in some back stories, the temple is a monastery, and the priests are monks. The temple or monastery may be in various locales including Hanoi, 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 The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimum number of moves required to solve a Tower of Hanoi puzzle with n disks is 2n − 1.
Iterative solution
A simple solution for the toy puzzle is to alternate between 1) moving the top piece and 2) moving another piece. For 1, whenever we're moving the top, we always move it to the next position in the same direction. This is to the right if the starting number of pieces is even, or to the left if the starting number of pieces is odd. We imagine the towers to be on a circle, or that the image of the puzzle wraps around horizontally, so that moving to the left from the first tower brings us to the third, and moving to the right from the third tower brings us to the first. In other words, step 1, 3, 5, 7... will place the top from A > B > C > A ... (for an even number of pieces) or A > C > B > A ... repeat (for an odd number of pieces.) For 2, Whenever we move another piece, there is always only one legal move, since no piece may be moved onto the smallest, and of any combination of other pieces, only one will fit the other. Following steps 1, 2, 1, 2, ... correctly will complete the puzzle in the fewest moves.
Simpler statement of iterative solution
The iterative solution is equivalent to repeated execution of the following sequence of steps until the goal has been achieved:
Move one disk from peg A to peg B or vice versa, whichever move is legal. Move one disk from peg A to peg C or vice versa, whichever move is legal. Move one disk from peg B to peg C or vice versa, whichever move is legal. Following this approach, the stack will end up on peg B if the number of disks is odd and peg C if it is even. Changing the order will change the outcome:
Move one disk from peg A to peg C or vice versa, whichever move is legal. Move one disk from peg A to peg B or vice versa, whichever move is legal. Move one disk from peg B to peg C or vice versa, whichever move is legal. This way, stack will end up on peg B if the number of disks is even and peg C if it is odd.
Recursive solution
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. Each of these created sub-problems being "smaller" guarantees that the base case(s) will eventually be reached. For the Towers of Hanoi:
label the pegs A, B, C, let n be the total number of disks, and number the disks from 1 (smallest, topmost) to n (largest, bottom-most). Assuming 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:
Move m − 1 disks from the source to the spare peg, by the same general solving procedure. Rules are not violated, by assumption. This leaves the disk m as a top disk on the source peg. Move the disk m from the source to the target peg, which is guaranteed to be a valid move, by the assumptions — a simple step. Move the m − 1 disks that we have just placed on the spare, from the spare to the target peg by the same general solving procedure, so they are placed on top of the disk m without violating the rules. The base case is to move 0 disks (in steps 1 and 3), that is, do nothing—which does not violate the rules. The full Tower of Hanoi solution then moves n disks from the source peg A to the target peg C, using B as the spare peg. This approach can be given a rigorous mathematical proof with mathematical induction and is often used as an example of recursion when teaching programming.
Logical analysis of the recursive solution
… excerpt ends here. Continue reading the full article.
