Origins
The puzzle was introduced to the West by the FrenchSolution
The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimal number of moves required to solve a Tower of Hanoi puzzle is , where ''n'' is the number of disks.Iterative solution
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.Simpler statement of iterative solution
For 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.Equivalent iterative solution
Another way to generate the unique optimal iterative solution: Number the disks 1 through ''n'' (largest to smallest). * If ''n'' is odd, the first move is from peg A to peg C. * If ''n'' is even, the first move is from peg A to peg B. Now, add these constraints: * No odd disk may be placed directly on an odd disk. * No even disk may be placed directly on an even disk. * There will sometimes be two possible pegs: one will have disks, and the other will be empty. Place the disk on the non-empty peg. * Never move a disk twice in succession. Considering those constraints after the first move, there is only one legal move at every subsequent turn. The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.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. Thence, for the Towers of Hanoi: * label the pegs A, B, C, * let ''n'' be the total number of disks, * 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 obviously doesn't violate the rules. The full Tower of Hanoi solution then consists of moving ''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 withLogical 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 ''S''3). 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 simply 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 first use this procedure to 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. # If ''h'' > 1, then again use this procedure to move the ''h'' − 1 smaller disks from peg B to peg C. By means ofRecursive implementation
The followingNon-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 may be determined more directly from the(m & m - 1) % 3
to peg ((m , m - 1) + 1) % 3
, where the disks begin on peg 0 and finish on peg 1 or 2 according as whether the number of disks is even or odd. Another formulation is from peg (m - (m & -m)) % 3
to peg (m + (m & -m)) % 3
.
Furthermore, the disk to be moved is determined by the number of times the move count (''m'') can be divided by 2 (i.e. the number of zero bits at the right), counting the first move as 1 and identifying the disks by the numbers 0, 1, 2, etc. in order of increasing size. This permits a very fast non-recursive computer implementation to find the positions of the disks after m moves without reference to any previous move or distribution of disks.
The operation, which counts the number of consecutive zeros at the end of a binary number, gives a simple solution to the problem: the disks are numbered from zero, and at move ''m'', disk number Gray-code solution
The binary numeral system ofIntegerExponent ange[2^8_-_1_2.html"_;"title="^8_-_1.html"_;"title="ange[2^8_-_1">ange[2^8_-_1_2">^8_-_1.html"_;"title="ange[2^8_-_1">ange[2^8_-_1_2+_1
_gives_moves_for_the_8-disk_puzzle.
__Graphical_representation_
The_game_can_be_represented_by_an_ ange[2^8_-_1_2.html"_;"title="^8_-_1.html"_;"title="ange[2^8_-_1">ange[2^8_-_1_2">^8_-_1.html"_;"title="ange[2^8_-_1">ange[2^8_-_1_2+_1_gives_moves_for_the_8-disk_puzzle.__Graphical_representation_
The_game_can_be_represented_by_an_Graph_(discrete_mathematics)#Undirected_graph">undirected_graphGraphical representation
The game can be represented by an Graph (discrete mathematics)#Undirected graph">undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...Variations
Adjacent pegs
If all moves must be between adjacent pegs (i.e. given pegs A, B, C, one cannot move directly between pegs A and C), then moving a stack of ''n'' disks from peg A to peg C takes 3''n'' − 1 moves. The solution uses all 3n valid positions, always taking the unique move that does not undo the previous move. The position with all disks at peg B is reached halfway, i.e. after (3''n'' − 1) / 2 moves.Cyclic Hanoi
In Cyclic Hanoi, we are given three pegs (A, B, C), which are arranged as a circle with the clockwise and the counterclockwise directions being defined as A – B – C – A and A – C – B – A respectively. The moving direction of the disk must be clockwise. It suffices to represent the sequence of disks to be moved. The solution can be found using two mutually recursive procedures: To move ''n'' disks counterclockwise to the neighbouring target peg: # move ''n'' − 1 disks counterclockwise to the target peg # move disk #''n'' one step clockwise # move ''n'' − 1 disks clockwise to the start peg # move disk #''n'' one step clockwise # move ''n'' − 1 disks counterclockwise to the target peg To move ''n'' disks clockwise to the neighbouring target peg: # move ''n'' − 1 disks counterclockwise to a spare peg # move disk #''n'' one step clockwise # move ''n'' − 1 disks counterclockwise to the target peg Let C(n) and A(n) represent moving n disks clockwise and counterclockwise, then we can write down both formulas: C(n) = A(n-1) n A(n-1) and A(n) = A(n-1) n C(n-1) n A(n-1). Thus C(1) = 1 and A(1) = 1 1, C(2) = 1 1 2 1 1 and A(2) = 1 1 2 1 2 1 1. The solution for the Cyclic Hanoi has some interesting properties: 1)The move-patterns of transferring a tower of disks from a peg to another peg are symmetric with respect to the center points. 2)The smallest disk is the first and last disk to move. 3)Groups of the smallest disk moves alternate with single moves of other disks. 4)The number of disks moves specified by C(n) and A(n) are minimal.With four pegs and beyond
Although the three-peg version has a simple recursive solution long been known, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle) was not verified until 2014, by Bousch. However, in case of four or more pegs, the Frame–Stewart algorithm is known without proof of optimality since 1941. For the formal derivation of the exact number of minimal moves required to solve the problem by applying the Frame–Stewart algorithm (and other equivalent methods), see the following paper. For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper. The so-called Towers of Bucharest and Towers of Klagenfurt game configurations yieldFrame–Stewart algorithm
The Frame–Stewart algorithm is described below: * Let be the number of disks. * Let be the number of pegs. * Define to be the minimum number of moves required to transfer n disks using r pegs. The algorithm can be described recursively: # For some , , transfer the top disks to a single peg other than the start or destination pegs, taking moves. # Without disturbing the peg that now contains the top disks, transfer the remaining disks to the destination peg, using only the remaining pegs, taking moves. # Finally, transfer the top disks to the destination peg, taking moves. The entire process takes moves. Therefore, the count should be picked for which this quantity is minimum. In the 4-peg case, the optimal equals , where is theGeneral shortest paths and the number 466/885
A curious generalization of the original goal of the puzzle is to start from a given configuration of the disks where all disks are not necessarily on the same peg and to arrive in a minimal number of moves at another given configuration. In general, it can be quite difficult to compute a shortest sequence of moves to solve this problem. A solution was proposed by Andreas Hinz and is based on the observation that in a shortest sequence of moves, the largest disk that needs to be moved (obviously one may ignore all of the largest disks that will occupy the same peg in both the initial and final configurations) will move either exactly once or exactly twice. The mathematics related to this generalized problem becomes even more interesting when one considers the ''average'' number of moves in a shortest sequence of moves between two initial and final disk configurations that are chosen at random. Hinz and Chan Tat-Hung independently discovered (see also ) that the average number of moves in an n-disk Tower is given by the following exact formula: : For large enough ''n'', only the first and second terms do not converge to zero, so we get an asymptotic expression: , as . Thus intuitively, we could interpret the fraction of as representing the ratio of the labor one has to perform when going from a randomly chosen configuration to another randomly chosen configuration, relative to the difficulty of having to cross the "most difficult" path of length which involves moving all the disks from one peg to another. An alternative explanation for the appearance of the constant 466/885, as well as a new and somewhat improved algorithm for computing the shortest path, was given by Romik.Magnetic Hanoi
In Magnetic Tower of Hanoi, each disk has two distinct sides North and South (typically colored "red" and "blue"). Disks must not be placed with the similar poles together—magnets in each disk prevent this illegal move. Also, each disk must be flipped as it is moved.Bicolor Towers of Hanoi
This variation of the famous Tower of Hanoi puzzle was offered to grade 3–6 students at ''2ème Championnat de France des Jeux Mathématiques et Logiques'' held in July 1988. The rules of the puzzle are essentially the same: disks are transferred between pegs one at a time. At no time may a bigger disk be placed on top of a smaller one. The difference is that now for every size there are two disks: one black and one white. Also, there are now two towers of disks of alternating colors. The goal of the puzzle is to make the towers monochrome (same color). The biggest disks at the bottom of the towers are assumed to swap positions.Tower of Hanoy
A variation of the puzzle has been adapted as a solitaire game with nine playing cards under the name Tower of Hanoy. It is not known whether the altered spelling of the original name is deliberate or accidental.Applications
The Tower of Hanoi is frequently used in psychological research onIn popular culture
In the science fiction story "Now Inhale", bySee also
*Notes
External links
* {{mathworld, title=Tower of Hanoi, urlname=TowerofHanoi Mechanical puzzles Mathematical puzzles Articles with example Python (programming language) code