The Tower of Hanoi or Towers of Hanoi (also known as The Towers of Bramha) 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 neatly stacked in 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 rules:
The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a legend about a Vietnamese or Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. It is not clear whether Lucas invented this legend or was inspired by it. The Tower of Hanoi is a problem often used to teach beginning programming, in particular, as an example of a simple recursive algorithm.
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 600 billion years (operation taking place is ) .
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.
The Flag Tower of Hanoi may have served as the inspiration for the name.
Alternate moves between the smallest piece and a non- smallest piece. When moving the smallest piece, always move it in the same direction (either to the left or to the right, but be consistent). If there is no tower in the chosen direction, move it to the opposite end. When the turn is to move the non-smallest piece, there is only one legal move.
The following is a procedure for moving a tower of h disks from a peg f onto a peg t, with r 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 .
Implementations in many other languages may be found at the Hanoimania! website.
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.
So if the number of disks is even the solution will start:
Also observe that:
For example, in an 8-disk Hanoi:
The above algorithm can be coded in Scheme as follows:
This procedure produces a list of the positions of the disks in order of decreasing size. Example:
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, the mth move 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. 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:
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.
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.
(define (long-move-tower h f t r)
(if (positive? h)
(let ((h (sub1 h)))
(long-move-tower h f t r)
(move-disk h f r t)
(long-move-tower h t f r)
(move-disk h r t f)
(long-move-tower h f t r))))
Where procedure (move-disk d f t r) moves disk d from peg f onto peg t, ignoring peg r. The number of moves of this uniquely defined solution is 3height-1 and all 3height different distributions of disks are traversed (when including the starting and final distribution). This is called a Hamilton path. For this solution the disk to be moved can be found with a ternary gray code in a similar way as explained for the shortest solution. In fact there is a ternary Gray code starting with all digits 0 and ending with all digits equal 2, that lists the successive distributions of disks of a Hamilton path from peg 0 to peg 2 for a tower of h disks, each code showing the positions of the disks in decreasing order of size when read from left to right. This Gray code is uniquely defined by imposing the extra condition that each digit is switched more often than each more significant digit on the left. This is the code needed for the Tower of Hanoi.
(define (number->p-ary-gray-code n h p) ; n h p --> n-th h digit p-ary gray-code
(let ((2p (* 2 p)))
(let loop ((n n) (h h) (gc ()))
(if (zero? h) gc
(let ((q (quotient n p)) (r (modulo n 2p)))
(loop q (sub1 h) (cons (if (>= r p) (- 2p r 1) r) gc)))))))
(define (p-ary-gray-code->number gc p) ; n-th p-ary gray-code --> n
(let loop ((gc gc) (significance (expt p (sub1 (length gc)))))
(if (null? gc) 0
(let ((digit (car gc)) (gc (cdr gc)))
(let ((n (loop gc (quotient significance p))))
(+ (* digit significance)
(if (odd? digit) (- significance n 1) n)))))))
(define (number->hanoian-gray-code n h) (number->p-ary-gray-code n h 3))
(define (hanoian-gray-code->number gc) (p-ary-gray-code->number gc 3))
The disk to be moved is determined by the number of times the move counter can be divided by 3. Where the disk is to be moved to can easily be determined too. For every triplet of moves, move the smallest disk twice in succession in the same direction, followed by a move of one of the larger disks (only one direction possible) Between every triplet of moves reverse the direction of the smallest disk. The very first move of the smallest disk is to be made from the starting peg onto the remaining third peg. Also observe that the unused peg of each move alternates between the starting and destination peg. These statements are easily proven by mathematical induction.
(define (exp3 n ) (expt 3 n))
(define (mod3 n ) (modulo n 3))
(define (mod4 n ) (modulo n 4))
(define (mcnt m d ) (+ (* 2 (quotient m (exp3 (add1 d)))) (mod3 (quotient m (exp3 d)))))
(define (thrd m h f t) (if (odd? m) t f))
(define (onto m h f t) (posi m h (disk m) f t))
(define (from m h f t) (- 3 (onto m h f t) (thrd m h f t)))
(define (posi m h d f t) (vector-ref (vector f (- 3 f t) t (- 3 f t)) (mod4 (mcnt m d))))
(define (disk m) (if (zero? (mod3 m)) (add1 (disk (quotient m 3))) 0))
Another modification is to move a tower from a peg back to the same peg while traversing all distributions of disks. (circular Hamilton path) There are exactly two solutions, but they mirror each other in the sense that there is in fact one path that can be traversed in both directions. Obviously, the length of the path is 3height. A simple algorithm for the circular Hamilton path is:
(define (circular-hamilton-move-tower h a b c) ; h=height. a, b and c are the three pegs.
(if (positive? h) ; start with a tower at peg a, move tower to peg b, then to peg c and finally return to peg a.
(let ((h-1 (sub1 h)))
(hamilton-start h-1 a c b) ; The largest disk is moved three times.
(move-disk h-1 a b c) ; Between these moves the longest non selfcrossing path is used in order to move the
(long-move-tower h-1 c a b) ; partial tower consisting of the h-1 smaller disks from one peg onto another one.
(move-disk h-1 b c a) ; Together the procedures hamilton-start and hamilton-finish make such a longest
(long-move-tower h-1 a b c) ; non selfcrossing path too. The moves made by hamiton-finish followed by
(move-disk h-1 c a b) ; those of hamilton-start form a longest non selfcrossing path for the same
(hamilton-finish h-1 b a c)))); partial tower from peg b to peg c.
(define (hamilton-start h a b c)
(if (positive? h)
(let ((h-1 (sub1 h)))
(hamilton-start h-1 a c b)
(move-disk h-1 a b c)
(long-move-tower h-1 c b a))))
(define (hamilton-finish h a b c)
(if (positive? h)
(let ((h-1 (sub1 h)))
(long-move-tower h-1 a c b)
(move-disk h-1 a b c)
(hamilton-finish h-1 c b a))))
The graph for 2 disks is 3 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 2 disks.
For 3 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 branch in the middle of the sides of the largest triangle represents a move of the largest disk. The branch 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.
In general, for a puzzle with n disks, there are 3n nodes in the graph; every node has three branches to other nodes, except the three corner nodes, which have two: it is always possible to move the smallest disk to the 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 branches, 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 branches.
As more disks are added, the graph representation of the game will resemble the Fractal figure, 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 branches:
The circular Hamiltonian path for three disks is:
/ ; call the pegs a, b and c
acc / bcc ; list disk positions from left to right in order of increasing size
abc / bac
bbc __ /__ aac
/ cbc cac
bba / aab
cba __aba bab/__ cab
caa / aca bcb cbb
/ / /
aaa /__ __ / __ / __ __ bbb
baa bca cca ccb acb abb
The graphs clearly show that:
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 memory test by neuropsychologists trying to evaluate amnesia.
The fact that the problem with four or more pegs is an open problem does not imply that no algorithm exists for finding (all of) the optimal solutions. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves (of length 1) and use Dijkstra's algorithm to find one (or all) shortest paths 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" that can be recursively applied to find a solution - see Paul Stockmeyer's survey paper for an explanation and some variants of the four-peg problem.
Although it agrees with computer experiments for small numbers of disks, there is not yet a general proof that this presumed-optimal solution is in fact optimal. However, results in 2004 showed that the presumed-optimal solution must be of the same order of magnitude as the optimal solution.
The algorithm can be described recursively:
The entire process takes moves. Therefore, the count should be picked for which this quantity is minimum.
This algorithm (with the above choice for ) is presumed to be optimal, and no counterexamples are known.
A 2007 U.S. patent application purportedly discloses multistack Tower of Hanoi puzzles [Feb. 1, 2007, Serial No.11/701,454] with two or more stacks and twice as many pegs as stacks. After beginning on a particular peg, each stack displaces and is displaced by a different colored stack on another peg when the puzzle is solved. Disks of one color also have another peg that excludes all other colors, so that there are three pegs available for each color disk, two that are shared with other colors and one that is not shared. On the shared pegs, a disk may not be placed on a different colored disk of the same size, a possibility that does not arise in the standard puzzle.
The simplest multistack game (2 x 4) has two stacks and four pegs, and it requires 3[T(n)] moves to solve where T(n) is the number of moves needed to solve a single stack classic of n disks. The game proceeds in seesaw fashion with longer and longer series of moves that alternate between colors. It concludes in reverse seesaw fashion with shorter and shorter such series of moves. Starting with the second series of three moves, these alternate series of moves double in length for the first half of the game, and the lengths are halved as the game concludes. The solution involves nesting an algorithm suitable for Tower of Hanoi into an algorithm that indicates when to switch between colors. When there are k stacks of n disks apiece in a game, and k > 2, it requires k[T(n)] + T(n-1) moves to relocate them.
The addition of a centrally located universal peg open to disks from all stacks converts these multistack Tower of Hanoi puzzles to multistack Reve's puzzles as described in the preceding section. In these games each stack may move among four pegs, the same combination of three in the 2 x 4 game plus the central universal peg. The simplest game of this kind (2 x 5) has two stacks and five pegs. A solution conjectured to be optimal interlocks the optimal solution of the 2 x 4 puzzle with the presumed optimal solution to Reve's puzzle. It takes R(n) + 2R(n-1) + 2 moves, where R(n) is the number of moves in the presumed optimal Reve's solution for a stack of n disks.
In the movie Stranger than Fiction, a miniature Towers of Hanoi puzzle can be seen on the cluttered desk of Professor Jules Hilbert.
There is a band named Towers of Hanoi