A puzzle invented by E. Lucas in 1883. Given a stack of disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the towers of Hanoi puzzle asks for the minimum number of moves required to reverse the order of the stack (where moves are allowed only if they place smaller disks on top of larger disks). The problem is isomorphic to finding a Hamiltonian path on an -hypercube (Gardner 1957, 1959).

For disks, the number of moves required is given by the recurrence relation

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

Poole (1994) gives Mathematica routines for solving an arbitrary disk configuration in the fewest possible moves. The proof of minimality is achieved using the Lucas correspondence which relates Pascal's triangle to the Hanoi graph. Algorithms are known for transferring disks for four pegs, but none has been proved minimal. For additional references, see Poole (1994).

Binary Carry Sequence, Gray Code, Ryser Formula

References

Allouche, J.-P. and Shallit, J. "The Ring of -Regular Sequences." Theoret. Comput. Sci. 98, 163-197, 1992.

Bogomolny, A. "Towers of Hanoi." http://www.cut-the-knot.com/recurrence/hanoi.html.

Chartrand, G. "The Tower of Hanoi Puzzle." §6.3 in Introductory Graph Theory. New York: Dover, pp. 135-139, 1985.

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.

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 The Scientific American Book of Mathematical Puzzles & Diversions. New York: Simon and Schuster, pp. 55-62, 1959.

Kasner, E. and Newman, J. R. Mathematics and the Imagination. Redmond, WA: Tempus Books, pp. 169-171, 1989.

Kolar, M. "Towers of Hanoi." http://www.pangea.ca/kolar/javascript/Hanoi/Hanoi.html.

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." Mathematica notebook Hanoi.m.

Ruskey, F. "Towers of Hanoi." http://www.theory.csc.uvic.ca/~cos/inf/comb/SubsetInfo.html#Hanoi.

Schoutte, P. H. "De Ringen van Brahma." Eigen Haard 22, 274-276, 1884.

Sloane, N. J. A. Sequences A001511/M0127 in "An On-Line Version of the Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/eisonline.html.

Kraitchik, M. "The Tower of Hanoi." §3.12.4 in Mathematical Recreations. New York: W. W. Norton, pp. 91-93, 1942.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 111-112, 1991.