Tower of Hanoi

A model set of the Tower of Hanoi (with 8 disks)
An animated solution of the Tower of Hanoi puzzle for T(4,3).
Tower of Hanoi interactive display at the Universum museum in Mexico City

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower,[1] and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

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.

Origins

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the immutable rules of the Brahma, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle will be completed, the world will end.[2] 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 disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 585 billion years[3] or 18,446,744,073,709,551,615 turns to finish, or about 42 times the current age of the Universe.

There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. 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

The puzzle can be played with any number of disks, although many toy versions have around seven to nine of them. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n is the number of disks.[4]

Iterative solution

Animation of an iterative algorithm solving 6 disks problem

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 number of moves.[5]

Simpler statement of iterative solution

For an even number of disks:

For an odd number of disks:

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).

Now, add these constraints:

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.[6]

Recursive solution

Illustration of a recursive solution for the Towers of Hanoi puzzle with 4 disks.

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 thus created sub-problems being "smaller" guarantees the base case(s) will eventually be reached. Thence, for the Towers of Hanoi:

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 can be safely ignored; to move m discs from a source peg to a target peg using a spare peg, without violating the rules:

  1. move m−1 discs 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
  2. move the disc m from the source to the target peg, which is guaranteed to be a valid move, by the assumptions — a simple step
  3. move the m−1 discs that we've 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 disc m without violating the rules
  4. the base case being, to move 0 disks, do nothing.

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.

The above is a recursive algorithm. To carry out steps 1 and 3 apply the same algorithm again for m−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for m = 0, which means there's nothing to do. This approach can be given a rigorous mathematical formalism with the theory of dynamic programming,[7][8] 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 (h=height) disks from a starting peg A (f=from) onto a destination peg C (t=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 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. Subsequently 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 temporarily be 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:

By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal 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 .

Recursive Implementation

The following highlights an essential function of the recursive solution which may be otherwise misunderstood or overlooked. That is, with every level of recursion, the first recursive call inverts the Target and Auxiliary stacks, while in the second recursive call the Source and Auxiliary stacks are inverted.

A = [5,4,3,2,1]
B = []
C = []

def move(n, source, target, auxiliary):
    if n > 0:
        # move n-1 disks from source to auxiliary, so they are out of the way  
        move(n-1, source, auxiliary, target)

        # move the nth disk from source to target
        target.append(source.pop())

        # Display our progress
        print(A, B, C, '##############', sep='\n')  
        
        # move the n-1 disks that we left on auxiliary onto target
        move(n-1, auxiliary, target, source)

# initiate call from source A to target C with auxiliary B 
move(5, A, C, B)

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:

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:

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:

Binary solution

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, with all digits 1), using the following rules:

For example, in an 8-disk Hanoi:

The source and destination pegs for the mth move can also be found elegantly from the binary representation of m using bitwise operations. To use the syntax of the C programming language, move m is from peg (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 count trailing zeros is moved the minimum possible distance to the right (circling back around to the left as needed).[9]

Gray code solution

The binary numeral system of Gray codes gives an alternative way of solving the puzzle. In the Gray system, numbers are expressed in a binary combination of 0s and 1s, but rather than being a standard positional numeral system, Gray code operates on the premise that each value differs from its predecessor by only one (and exactly one) bit changed. The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems.

If one counts in Gray code of a bit size equal to the number of disks in a particular Tower of Hanoi, begins at zero, and counts up, then the bit changed each move corresponds to the disk to move, where the least-significant-bit is the smallest disk and the most-significant-bit is the largest.

Counting moves from 1 and identifying the disks by numbers starting from 0 in order of increasing size, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2.

This technique identifies which disk to move, but not where to move it to. For the smallest disk there are always two possibilities. For the other disks there is always one possibility, except when all disks are on the same peg, but in that case either it is the smallest disk that must be moved or the objective has already been achieved. Luckily, there is a rule which does say where to move the smallest disk to. Let f be the starting peg, t the destination peg and r the remaining third peg. If the number of disks is odd, the smallest disk cycles along the pegs in the order f→t→r→f→t→r, etc. If the number of disks is even, this must be reversed: f→r→t→f→r→t etc.[10]

The position of the bit change in the Gray code solution gives the size of the disk moved at each step: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (sequence A001511 in the OEIS),[11] a sequence also known as the ruler function, or one more than the power of 2 within the move number. In the Wolfram Language, IntegerExponent[Range[2^8-1], 2] + 1 gives moves for the 8 disk puzzle.

Graphical representation

The game can be represented by an undirected graph, the nodes representing distributions of disks and the edges representing moves. For one disk, the graph is a triangle:

The graph for two disks is three triangles arranged in a larger triangle:

The nodes at the vertices of the outermost triangle represent distributions with all disks on the same peg.

For h+1 disks, take the graph of h disks and replace each small triangle with the graph for two disks.

For three disks the graph is:

The sides of the outermost triangle represent the shortest ways of moving a tower from one peg to another one. The edge in the middle of the sides of the largest triangle represents a move of the largest disk. The edge in the middle of the sides of each next smaller triangle represents a move of each next smaller disk. The sides of the smallest triangles represent moves of the smallest disk.

The game graph of level 7 shows the relatedness to the Sierpiński triangle.

In general, for a puzzle with n disks, there are 3n nodes in the graph; every node has three edges to other nodes, except the three corner nodes, which have two: it is always possible to move the smallest disk to one of the two other pegs; and it is possible to move one disk between those two pegs except in the situation where all disks are stacked on one peg. The corner nodes represent the three cases where all the disks are stacked on one peg. The diagram for n + 1 disks is obtained by taking three copies of the n-disk diagram—each one representing all the states and moves of the smaller disks for one particular position of the new largest disk—and joining them at the corners with three new edges, representing the only three opportunities to move the largest disk. The resulting figure thus has 3n+1 nodes and still has three corners remaining with only two edges.

As more disks are added, the graph representation of the game will resemble a fractal figure, the Sierpiński triangle. It is clear that the great majority of positions in the puzzle will never be reached when using the shortest possible solution; indeed, if the priests of the legend are using the longest possible solution (without re-visiting any position), it will take them 364 − 1 moves, or more than 1023 years.

The longest non-repetitive way for three disks can be visualized by erasing the unused edges:

Incidentally, this longest non-repetitive path can be obtained by forbidding all moves from a to b.

The Hamiltonian cycle for three disks is:

The graphs clearly show that:

This gives Nh to be 2, 12, 1872, 6563711232, .... (sequence A125295 in the OEIS)

Applications

The Tower of Hanoi is frequently used in psychological research on problem solving. There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions.

Zhang and Norman (Cognitive Science, 18, 87-122, 1994) used several isomorphic (equivalent) representations of the game to study the impact of representational effect in task design. They demonstrated an impact on user performance by changing the way that the rules of the game are represented, using variations in the physical design of the game components. This knowledge has impacted on the development of the TURF framework for the representation of Human Computer Interaction

The Tower of Hanoi is also used as a Backup rotation scheme when performing computer data Backups where multiple tapes/media are involved.

As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x hanoi. There is also a sample algorithm written in Prolog.

The Tower of Hanoi is also used as a test by neuropsychologists trying to evaluate frontal lobe deficits.

In 2010, researchers published the results of an experiment that found that the ant species Linepithema humile were successfully able to solve the 3-disk version of the Tower of Hanoi problem through non-linear dynamics and pheromone signals.[12]

General 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 Hat-Tung independently discovered [13][14] (see also [15]:Chapter 1, p. 14) that the average number of moves in an n-disk Tower is given by the following exact formula:

Note that 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.[16]

Variations

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 disc must be clockwise.[17] It suffices to represent the sequence of discs to be moved. The solution can be found using two mutually recursive procedures:

To move n discs counterclockwise to the neighbouring target peg:

  1. move n − 1 discs counterclockwise to the target peg
  2. move disc #n one step clockwise
  3. move n − 1 discs clockwise to the start peg
  4. move disc #n one step clockwise
  5. move n − 1 discs counterclockwise to the target peg

To move n discs clockwise to the neighbouring target peg:

  1. move n − 1 discs counterclockwise to a spare peg
  2. move disc #n one step clockwise
  3. move n − 1 discs counterclockwise to the target peg

Let C(n) and A(n) represent moving n discs 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 discs from a peg to another peg are symmetric with respect to the center points.

2)The smallest disc is the first and last disc to move.

3)Groups of the smallest disc moves alternate with single moves of other discs.

4)The number of discs 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 as outlined above which has long been known, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle) has not been verified until 2014, and in the case of more than four pegs the optimal solution is still an open problem, even if a proof that the Frame-Stewart algorithm is optimal is proposed by Demontis in 2016.[18]

Even in the case of more than four pegs there are simple but slow algorithms that find the optimal solution in each particular case of a certain number of disks and pegs. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves and use breadth first search to find one (or all) shortest path(s) moving a tower from one peg onto another one. However, even smartly implemented on the fastest computer now available, this algorithm provides no way of effectively computing solutions for large numbers of disks; the program would require more time and memory than available. Hence, even having an algorithm, it remains unknown how many moves an optimal solution requires and how many optimal solutions exist for 1000 disks and 10 pegs.

Though it is not known exactly how many moves must be made, there are some asymptotic results.

There is also a "presumed-optimal solution" given by the Frame-Stewart algorithm, discovered independently by Frame and Stewart in 1941.[19] The related open Frame-Stewart conjecture claims that the Frame-Stewart algorithm always gives an optimal solution. For the case of four pegs it was proven by Bousch [20] in 2014 that the Frame-Stewart algorithm is optimal.

For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper.[21]

Frame–Stewart algorithm

The Frame–Stewart algorithm, giving an optimal for four (and conjecturally for even more) pegs, is described below:

The algorithm can be described recursively:

  1. For some , , transfer the top disks to a single peg other than the start or destination pegs, taking moves.
  2. 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.
  3. 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 a four-peg scenario, the ideal is equal to .[22] For example, in the UPenn CIS 194 course on Haskell, the first assignment page<ref "name=UPenn CIS 194 Towers of Hanoi Problem Set">"UPenn CIS 194 Introduction to Haskell Assignment 1" (PDF). Retrieved January 31, 2016. </ref> lists the optimal solution for the 15-disk and 4-peg case as 129 steps, which is obtained for the above value of k.

This algorithm (with the above choice for ) is presumed to be optimal for any number of pegs.

Robert Swartz has an implementation of the Frame–Stewart algorithm that displays up to 50 discs and 10 pegs: http://www.mathapplets.net

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.

Initial Configuration of Bicolor Towers of Hanoi (n=4)

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.[23]

Final Configuration of Bicolor Towers of Hanoi (n=4)

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.

In the science fiction story "Now Inhale", by Eric Frank Russell,[24] a human is held prisoner on a planet where the local custom is to make the prisoner play a game until it is won or lost before his execution. The protagonist knows that a rescue ship might take a year or more to arrive, so he chooses to play Towers of Hanoi with 64 disks. (This story makes reference to the legend about the Buddhist monks playing the game until the end of the world.)

In the 1966 Doctor Who story The Celestial Toymaker, the eponymous villain forces the Doctor to play a ten-piece 1,023-move Tower of Hanoi game entitled The Trilogic Game with the pieces forming a pyramid shape when stacked.

In 2007, the concept of the Towers Of Hanoi problem was used in Professor Layton and the Diabolical Box in puzzles 6, 83, and 84, but the discs had been changed to pancakes. The puzzle was based around a dilemma where the chef of a restaurant had to move a pile of pancakes from one plate to the other with the basic principles of the original puzzle (i.e. three plates that the pancakes could be moved onto, not being able to put a larger pancake onto a smaller one, etc.)

In the film Rise of the Planet of the Apes (2011), this puzzle, called in the film the "Lucas Tower", is used as a test to study the intelligence of apes.

The puzzle is featured regularly in adventure and puzzle games. Since it is easy to implement, and easily recognised, it is well-suited to use as a puzzle in a larger graphical game (e.g. Star Wars: Knights of the Old Republic and Mass Effect[25]). Some implementations use straight disks, but others disguise the puzzle in some other form. There is an arcade version by Sega/Andamiro.[26]

A 15-disk version of the puzzle appears in the game Sunless Sea as a lock to a tomb. The player has the option to click through each move of the puzzle in order to solve it, but the game notes that it will take 32767 moves to complete. If an especially dedicated player does click through to the end of the puzzle, it is revealed completing the puzzle does not unlock the door. The real solution is to use dynamite to destroy the door and puzzle entirely.

The problem is featured as part of a reward challenge in a 2011 episode of the American version of the Survivor TV series. Both players (Ozzy Lusth and Benjamin "Coach" Wade) struggled to understand how to solve the puzzle and are aided by their fellow tribe members.

In materials science

3D AFM topographic image of multilayered palladium nanosheet on silicon wafer, with Tower of Hanoi-like structure.[27]

In 2014, scientists synthesized multilayered palladium nanosheets with the Tower of Hanoi like structure.[27]

See also

Notes

  1. ↑ Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 0-465-04540-5.
  2. ↑ Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. p. 137. ISBN 0-03-084693-5.
  3. ↑ Moscovich, Ivan (2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN 0-7611-1826-8.
  4. ↑ Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. p. 197. ISBN 0-8218-4814-3.
  5. ↑ Troshkin, M. "Doomsday Comes: A Nonrecursive Analysis of the Recursive Towers-of-Hanoi Problem". Focus (in Russian). 95 (2): 10–14.
  6. ↑ Mayer, Herbert; Perkins, Don (1984). "Towers of Hanoi Revisited". SIGPLAN Notices: 80–84. doi:10.1145/948566.948573.
  7. ↑ Sniedovich, Moshe (2002). "OR/MS Games: 2. The Towers of Hanoi Problem,". INFORMS Transactions on Education. 3 (1): 34–51.
  8. ↑ Sniedovich, Moshe (2010). Dynamic Programming: Foundations and Principles. Taylor & Francis. ISBN 978-0-8247-4099-3.
  9. ↑ Warren, Henry S. (2003). "Section 5-4: Counting Trailing 0's.". Hacker's delight (1st ed.). Boston MA: Addison-Wesley. ISBN 0-201-91465-4.
  10. ↑ Miller, Charles D. (2000). "Ch. 4: Binary Numbers and the Standard Gray Code". Mathematical Ideas (9 ed.). Addison Wesley Longman. ISBN 0321076079.
  11. ↑ Gros, L. (1872). Théorie du Baguenodier. Lyon: Aimé Vingtrinier.
  12. ↑ Reid, C.R.; Sumpter, D.J.; Beekman, M. (January 2011). "Optimisation in a natural system: Argentine ants solve the Towers of Hanoi". J. Exp. Biol. 214 (Pt 1): 50–8. doi:10.1242/jeb.048173. PMID 21147968.
  13. ↑ Hinz, A. (1989). "The Tower of Hanoi". L'Enseignement Mathématique. 35: 289–321. doi:10.5169/seals-57378.
  14. ↑ Chan, T. (1988). "A statistical analysis of the towers of Hanoi problem". Internat. J. Comput. Math. 28: 57–65. doi:10.1080/00207168908803728.
  15. ↑ Stewart, Ian (2004). Another Fine Math You've Got Me Into... Courier Dover. ISBN 0-7167-2342-5.
  16. ↑ Romik, D. (2006). "Shortest paths in the Tower of Hanoi graph and finite automata". SIAM Journal on Discrete Mathematics. 20 (3): 610–622. doi:10.1137/050628660.
  17. ↑ Gedeon, T. D. (1996). "The Cyclic Towers of Hanoi: An Iterative Solution Produced by Transformation". The Computer Journal. 39 (4). doi:10.1093/comjnl/39.4.353.
  18. ↑ Demontis, Roberto. "What is the least number of moves needed to solve the k peg Towers of Hanoi problem?" (PDF). Retrieved 27 September 2016.
  19. ↑ Stewart, B.M.; Frame, J.S. (March 1941). "Solution to advanced problem 3819". American Mathematical Monthly. 48 (3): 216–9. doi:10.2307/2304268. JSTOR 2304268.
  20. ↑ Bousch, T. (2014). "La quatrieme tour de Hanoi". Bull. Belg. Math. Soc. Simon Stevin. 21: 895–912.
  21. ↑ Stockmeyer, Paul (1994). "Variations on the Four-Post Tower of Hanoi Puzzle" (Postscript). Congressus Numerantium. 102: 3–12.
  22. ↑ "University of Toronto CSC148 Slog". April 5, 2014. Retrieved July 22, 2015.
  23. ↑ http://rmm.ludus-opuscula.org/PDF_Files/Chaugule_BicolorHanoi_37_48(4_2015)_low.pdf
  24. ↑ Russell, Eric Frank (April 1959). "Now Inhale". Astounding Science Fiction.
  25. ↑ "Tower of Hanoi (video game concept)". giantbomb.com. Retrieved 2010-12-05.
  26. ↑ http://www.segaarcade.com/towerofhanoi
  27. 1 2 Yin, Xi; Liu, Xinhong; Pan, Yung-Tin; Walsh, Kathleen A.; Yang, Hong (November 4, 2014). "Hanoi Tower-like Multilayered Ultrathin Palladium Nanosheets". Nano Letters. doi:10.1021/nl503879a.
Wikimedia Commons has media related to Tower of Hanoi.

This article is issued from Wikipedia - version of the 11/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.