TOPICS
Search

Tower of Hanoi


TowersOfHanoi
Solution of the three-rod four-disk tower of Hanoi problem

The tower of Hanoi (commonly also known as the "towers of Hanoi"), is a puzzle invented by E. Lucas in 1883. It is also known as the Tower of Brahma puzzle and appeared as an intelligence test for apes in the film Rise of the Planet of the Apes (2011) under the name "Lucas Tower."

Given a stack of n disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the tower of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. The puzzle with n=4 pegs and n disks is sometimes known as Reve's puzzle.

The problem is isomorphic to finding a Hamiltonian path on an n-hypercube (Gardner 1957, 1959).

TowersofHanoiSolution

Given three rods and n disks, the sequence S_1={a_k} giving the number of the disk (i=1 to n) to be moved at the kth step is given by the remarkably simple recursive procedure of starting with the list S_1={1} for a single disk, and recursively computing

 S_n={S_(n-1),n,S_(n-1)}.
(1)

For the first few values of n, this gives the sequences shown in the following table. A solution of the three-rod four-disk problem is illustrated above.

nS_n
11
21, 2, 1
31, 2, 1, 3, 1, 2, 1
41, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

As the number of disks is increases (again for three rods), an infinite sequence is obtained, the first few terms of which are illustrated in the table above (OEIS A001511). Amazingly, this is exactly the binary carry sequence plus one. Even more amazingly, the number of disks moved after the kth step is the same as the element which needs to be added or deleted in the kth addend of the Ryser formula (Gardner 1988, Vardi 1991). A simple method for hand-solving uses disks painted with alternating colors. No two disks of the same color are ever placed atop each other, and no disk is moved twice in a row (P. Tokarczuk, pers. comm. Jun. 23, 2004).

As a result of the above procedure, the number of moves h_n required to solve the puzzle of n disks on three rods is given by the recurrence relation

 h_n=2h_(n-1)+1
(2)

with h_1=1. Solving gives

 h_n=2^n-1,
(3)

i.e., the Mersenne numbers.

For three rods, the proof that the above solution is minimal can be achieved using the Lucas correspondence which relates Pascal's triangle to the Hanoi graph. While algorithms are known for transferring disks on four rods, none has been proved minimal.

A Hanoi graph can be constructed whose graph vertices correspond to legal configurations of n towers, where the graph vertices are adjacent if the corresponding configurations can be obtained by a legal move. The puzzle itself can be solved using a binary Gray code.

Poole (1994) and Rangel-Mondragón give Wolfram Language routines for solving the Hanoi tower problem. Poole's algorithm works for an arbitrary disk configuration, and provides the solution in the fewest possible moves.

The minimal numbers of moves required to order n=1, 2, ... disk on four rods are given by 1, 3, 5, 9, 13, 17, 25, 33, ... (OEIS A007664). It is conjectured that this sequence is given by the recurrence

 s_n=s_(n-1)+2^x,
(4)

with s_1=1 and x the positive floor integer solution to

 n-1=1/2x(x+1),
(5)

i.e.,

 x=|_(sqrt(8n-7)-1)/2_|.
(6)

This would then given the explicit formula

 s_n=1+[n-1/2x(x-1)-1]2^x.
(7)

Wolfram (2022) analyzes the tower of Hanoi as a multicomputational process, including through the use of branchial graphs.


See also

Binary Carry Sequence, Gray Code, Pancake Sorting, Puz-Graph, Ryser Formula

Explore with Wolfram|Alpha

References

Allouche, J.-P. and Shallit, J. "The Ring of k-Regular Sequences." Theoret. Comput. Sci. 98, 163-197, 1992.Allouche, J.-P. "Note on the Cyclic Towers of Hanoi." Theor. Comput. Sci. 123, 3-7, 1994.Bogomolny, A. "Towers of Hanoi." http://www.cut-the-knot.org/recurrence/hanoi.shtml.Brousseau, A. "Tower of Hanoi with More Pegs." J. Recr. Math. 8, 169-176, 1972.Chartrand, G. "The Tower of Hanoi Puzzle." §6.3 in Introductory Graph Theory. New York: Dover, pp. 135-139, 1985.Daiev, V. "Problem 636: Greatest Divisors of Even Integers." Math. Mag. 40, 164-165, 1967.Dubrovsky, V. "Nesting Puzzles, Part I: Moving Oriental Towers." Quantum 6, 53-57 (Jan.) and 49-51 (Feb.), 1996.Flajolet, P.; Raoult, J.-C.; and Vuillemin, J. "The Number of Registers Required for Evaluating Arithmetic Expressions." Theoret. Comput. Sci. 9, 99-125, 1979.Frame, J. S. "Solution to Problem 3918." Amer. Math. Monthly 41, 216-217, 1941.Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957.Gardner, M. "The Icosian Game and the Tower of Hanoi." Ch. 6 in Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games. New York: Simon and Schuster, pp. 55-62, 1959.Kai, Y. and Chuan, X. "Preliminary Probe of 4-Peg Hanoi Tower." Acta Scient. Natur. Univers. Pekin. 40, 99-106, 2004.Kasner, E. and Newman, J. R. Mathematics and the Imagination. Redmond, WA: Tempus Books, pp. 169-171, 1989.Kolar, M. "Tower of Hanoi (TH) Puzzle." http://HanoiTower.mkolar.org/.Kraitchik, M. "The Tower of Hanoi." §3.12.4 in Mathematical Recreations. New York: W. W. Norton, pp. 91-93, 1942.Lucas, É. Récréations mathématiques, Vol. 3. Paris: Gauthier-Villars, 1891-1894. Reprinted Albert Blanchard, 1960.Poole, D. G. "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)." Math. Mag. 67, 323-344, 1994. Poole, D. G. "Towers of Hanoi Package." http://mathworld.wolfram.com/packages/Hanoi.m. Rangel-Mondragón, J. "Generalized Hanoi Tower." http://library.wolfram.com/infocenter/MathSource/4861/.Ruskey, F. "Towers of Hanoi." http://www.theory.csc.uvic.ca/~cos/inf/comb/SubsetInfo.html#Hanoi.Schoute, P. H. "De Ringen van Brahma." Eigen Haard 22, 274-276, 1884.Sloane, N. J. A. Sequences A001511/M0127, A007664/M2449, and A007665/M2414 in "The On-Line Encyclopedia of Integer Sequences."Stewart, B. M. "Problem 3918." Amer. Math. Monthly 39, 363, 1939.Stewart, B. M. "Solution to Problem 3918." Amer. Math. Monthly 41, 216-219, 1941.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 111-112, 1991.Wolfram, S. "Games and Puzzles as Multicomputational Systems." Jun. 8, 2022. https://writings.stephenwolfram.com/2022/06/games-and-puzzles-as-multicomputational-systems/.Wood, D. "Towers of Brahma and Hanoi Revisited." J. Recr. Math. 14, 17-24, 1981.

Referenced on Wolfram|Alpha

Tower of Hanoi

Cite this as:

Weisstein, Eric W. "Tower of Hanoi." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TowerofHanoi.html

Subject classifications