The Tower of Hanoi aka TOH (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 , 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 .
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
As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (height) disks from a starting peg f = A (from) onto a destination peg t = C (to), B being the remaining third peg and assuming t ≠ f. First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg A to peg C, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h = 1, then move the disk from peg A to peg C. If h > 1, then somewhere along the sequence of moves, the largest disk must be moved from peg A to another peg, preferably to peg C. The only situation that allows this move is when all smaller h − 1 disks are on peg B. Hence, first all h − 1 smaller disks must go from A to B. Then move the largest disk and finally move the h − 1 smaller disks from peg B to peg C. The presence of the largest disk does not impede any move of the h − 1 smaller disks and can be temporarily ignored. Now the problem is reduced to moving h − 1 disks from one peg to another one, first from A to B and subsequently from B to C, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h − 1 problem to h − 2, h − 3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows.
Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one, and disk h − 1 the largest one.
The following is a procedure for moving a tower of h disks from a peg A onto a peg C, with B being the remaining third peg: If h > 1, then move the h − 1 smaller disks from peg A to peg B. Now the largest disk, i.e. disk h can be moved from peg A to peg C. Then move the h − 1 smaller disks from peg B to peg C.
By mathematical induction, it is easily proven that the above procedure requires the minimum number of moves possible and that the produced solution is the only one with this minimum number of moves. Using recurrence relations, the exact number of moves that this solution requires can be calculated by: . This result is obtained by noting that steps 1 and 3 take moves, and step 2 takes one move, giving .
Non-recursive solution
The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm, has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs f, t, r, f, t, r, etc. for odd height of the tower and traverses the pegs f, r, t, f, r, t, etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm.
In alternate moves: Move the smallest disk to the peg it has not recently come from. Move another disk legally (there will be only one possibility). For the very first move, the smallest disk goes to peg t if h is odd and to peg r if h is even.
Also observe that: Disks whose ordinals have even parity move in the same sense as the smallest disk. Disks whose ordinals have odd parity move in opposite sense. If h is even, the remaining third peg during successive moves is t, r, f, t, r, f, etc. If h is odd, the remaining third peg during successive moves is r, t, f, r, t, f, etc.
With this knowledge, a set of disks in the middle of an optimal solution can be recovered with no more state information than the positions of each disk: Call the moves detailed above a disk's "natural" move. Examine the smallest top disk that is not disk 0, and note what its only (legal) move would be: if there is no such disk, then we are either at the first or last move. If that move is the disk's "natural" move, then the disk has not been moved since the last disk 0 move, and that move should be taken. If that move is not the disk's "natural" move, then move disk 0.
Binary solution Disk positions for an n-disk puzzle can be determined directly from the binary representation of the move number, m. For example, all the details for move m=216 of an 8-disk Tower of Hanoi can be computed without any iteration or recursion, and without reference to any previous moves or distribution of disks. Conversely, given a legal disk distribution, the move number to achieve that distribution can be computed.
Let the disks be labeled n, n-1,…,1, in decreasing size. Let the pegs A, B, and C be labeled 0, 1, and 2 respectively, with 0 always being the starting peg and 2 always being the ending peg. Further, let the bases for the pegs upon which the disks are stacked be labeled n+1, n+2, and n+3, for pegs 0, 1, and 2 respectively.
The disk positions after move m can be mapped from the binary representation of m by the following rules:T.R. Walsh, The Towers of Hanoi revisited: moving the rings by counting the moves, Information Processing Letters, 1982, Vol.15, 64-67. Netherlands.
There is 1 binary digit (bit) in m for each disk.
The bitstring for m is read from left to right, and each bit can be used to map the location of the corresponding disk, from disk n to disk 1.