View source for Tower of Hanoi

{{Short description|Mathematical puzzle game}}
{{about|the mathematical disk game|the card game|Tower of Hanoy|the Vietnamese skyscraper|Landmark 72}}
<!--"Hanoy" here is the actual spelling used in the card game title, not a typo-->

[[File:Tower of Hanoi.jpeg|300px|thumb|A model set of the Tower of Hanoi (with 8 disks)]]
[[File:Tower of Hanoi 4.gif|300px|thumb|An animated solution of the '''Tower of Hanoi''' puzzle for ''T''(4, 3)]]
[[File:UniversumUNAM34.JPG|thumb|300px|Tower of Hanoi interactive display at Mexico City's [[Universum (UNAM)|Universum Museum]]]]
The '''Tower of Hanoi''' (also called '''The problem of Benares Temple''',<ref name=oeis>{{Cite web|title=A000225 - OEIS|url=https://oeis.org/A000225|access-date=2021-09-03|website=oeis.org}}</ref> '''Tower of Brahma''' or '''Lucas' Tower''',<ref>{{cite book |last=Hofstadter |first=Douglas R. |title=Metamagical Themas : Questing for the Essence of Mind and Pattern |url=https://archive.org/details/metamagicalthema0000hofs |url-access=registration |year=1985 |publisher=Basic Books |location=New York |isbn=978-0-465-04540-2}}</ref> and sometimes pluralized as '''Towers''', or simply '''pyramid puzzle'''<ref>{{cite journal |journal=The Mathematics Teacher |date=1963 |volume=56 |page=84 |url=https://books.google.com/books?id=edoVAAAAIAAJ&q=tower+hanoi+pyramid+puzzle |access-date=9 March 2021 |publisher=National Council of Teachers of Mathematics |doi=10.5951/MT.56.2.0084 |issn=0025-5769|title=A device for demonstrating some elementary properties of integers |last=Cohn |first=Ernst M. |issue=2 }}</ref>) is a [[mathematical game]] or [[puzzle]] consisting of three rods and a number of disks of various [[diameter]]s, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a [[conical]] shape. The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules:<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Tower of Hanoi |url=https://mathworld.wolfram.com/ |access-date=2023-10-20 |website=mathworld.wolfram.com |language=en}}</ref>

# Only one disk may be moved at a time.
# Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
# No disk may be placed on top of a disk that is smaller than it.

With three disks, the puzzle can be solved in seven moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is {{nowrap|2<sup>''n''</sup> − 1}}, where ''n'' is the number of disks.

== Origins ==
The puzzle was invented by the French [[mathematician]] [[Édouard Lucas]], first presented in 1883 as a game discovered by "N. Claus (de Siam)" (an anagram of "Lucas d'Amiens"),<ref name="hinz13">{{cite book | title=The Tower of Hanoi – Myths and Maths|title-link= The Tower of Hanoi – Myths and Maths | isbn= 978-3034802369| last1= Hinz| first1= Andreas M.| last2= Klavžar| first2= Sandi| last3= Milutinović| first3= Uroš| last4= Petr| first4= Ciril| date= 2013-01-31|publisher= Springer }}</ref><ref name="stockmeyer05">{{cite web |last1=Stockmeyer |first1=Paul K. |title=The Tower of Hanoi: A Bibliography |url=https://www.cs.wm.edu/~pkstoc/biblio2.pdf |access-date=2024-02-21}}</ref><ref name="parville83">{{cite news |last1=de Parville |first1=Henri |title=Revue des Sciences |url=https://gallica.bnf.fr/ark:/12148/bpt6k462461g/f2.item.zoom |access-date=2024-02-21 |work=Journal des débats |date=1883-12-27}}</ref> and later published as a booklet in 1889<ref>{{cite book | first = Édouard | last = Lucas | author-link = Édouard Lucas | title = Jeux scientifiques pour servir à l'histoire, à l'enseignement et à la pratique du calcul et du dessin | publisher = Chambon et Baye | date = 1889| language = fr | location = Paris | url = https://gallica.bnf.fr/ark:/12148/bpt6k3943s/f272 | access-date = 2024-01-27}}</ref> and in a posthumously-published volume of Lucas' ''Récréations mathématiques''.<ref>{{ cite book | first = Édouard | last = Lucas | author-link = Édouard Lucas | title =  Récréations mathématiques | volume = 3 | year = 1892 | language = fr | publisher = Librairie Albert Blanchard, 1979 | page = 58 |  url = https://gallica.bnf.fr/ark:/12148/bpt6k3945d/f64}}</ref> Accompanying the game was an instruction booklet, describing the game's purported origins in [[Tonkin]], and claiming that according to legend [[Brahmins]] at a temple in [[Benares]] have been carrying out the movement of the "Sacred Tower of [[Brahma]]", consisting of sixty-four golden disks, according to the same rules as in the game, and that the completion of the tower would lead to the end of the world.<ref name="stockmeyerinst">{{cite web |last1=Stockmeyer |first1=Paul K. |title=Tower of Hanoi instructions in English, page 1 |url=https://www.cs.wm.edu/~pkstoc/page_1.html|access-date=2024-02-21}}</ref> Numerous variations on this legend exist, regarding the ancient and mystical nature of the puzzle.<ref name="hinz13" />

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 2<sup>64</sup>&nbsp;−&nbsp;1 seconds or roughly 585 [[1,000,000,000|billion]] years to finish,<ref>{{cite book |last=Moscovich |first=Ivan |author-link=Ivan Moscovich |title=1000 playthinks: puzzles, paradoxes, illusions & games |publisher=Workman |year=2001 |isbn=978-0-7611-1826-8 }}</ref> which is about 42 times the estimated current [[age of the universe]].

There are many variations on this legend. For instance, in some back stories, the temple is a [[monastery]], and the priests are [[monk]]s. The temple or monastery may be in various locales including [[Hanoi]], 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 7 to 9 of them. The minimal number of moves required to solve a Tower of Hanoi puzzle with ''n'' disks is {{nowrap|2<sup>''n''</sup> − 1}}.<ref>{{cite book |last=Petković |first=Miodrag |title=Famous Puzzles of Great Mathematicians |year=2009 |publisher=AMS Bookstore |isbn=978-0-8218-4814-2 |page=197}}</ref>

=== Iterative solution ===
[[File:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|thumb|Animation of an iterative algorithm-solving 6-disk 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 moves.<ref>{{cite journal |last=Troshkin |first=M. |title=Doomsday Comes: A Nonrecursive Analysis of the Recursive Towers-of-Hanoi Problem |journal=Focus |volume=95 |issue=2 |pages=10–14 |language=ru }}</ref>

==== Simpler statement of iterative solution ====
{{More citations needed section|date=January 2024}}
The iterative solution is equivalent to repeated execution of the following sequence of steps until the goal has been achieved:
* Move one disk from peg A to peg B or vice versa, whichever move is legal.
* Move one disk from peg A to peg C or vice versa, whichever move is legal.
* Move one disk from peg B to peg C or vice versa, whichever move is legal.
Following this approach, the stack will end up on peg B if the number of disks is odd and peg C if it is even.

=== Recursive solution ===
{{More citations needed section|date=January 2024}}
[[File:Tower of Hanoi recursion SMIL.svg|thumb|link={{filepath:Tower_of_Hanoi_recursion_SMIL.svg}}|Illustration of a recursive solution for the Towers of Hanoi puzzle with 4 disks. In [{{filepath:Tower_of_Hanoi_recursion_SMIL.svg}} the SVG file,] click a grey button to expand or collapse it]]
The key to solving a problem [[recursive]]ly 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{{Citation needed|date=January 2024}}, 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. For the Towers of Hanoi:
* label the pegs A, B, C,
* let ''n'' be the total number of disks, and
* 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 disk 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 does not violate the rules.

The full Tower of Hanoi solution then moves ''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 with [[mathematical induction]] and is often used as an example of recursion when teaching programming.

==== Logical analysis of the recursive solution ====
{{More citations needed section|date=January 2024}}
<!-- TODO:  This section needs copy-editing for tone, professionalism and clarity: edited/bolded .-->
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|symmetric group ''S''<sub>3</sub>]]). 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 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 [[mathematical induction]], it is easily proven that the above procedure requires the minimum number of moves possible and that the produced solution is the only one with this minimal number of moves. Using [[recurrence relation]]s, the exact number of moves that this solution requires can be calculated by: <math>2^h - 1</math>. This result is obtained by noting that steps 1 and 3 take <math>T_{h-1}</math> moves, and step 2 takes one move, giving <math>T_h = 2T_{h-1} + 1</math>.

==== Non-recursive solution ====
{{More citations needed section|date=January 2024}}
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 for an ''n''-disk puzzle can be determined directly from the [[Binary numeral system|binary]] representation of the move number, ''m''. For example, all the details for move ''m''=216 of an 8-disk Tower of Hanoi can be computed without any iteration or recursion, and without reference to any previous moves or distribution of disks. Conversely, given a legal disk distribution, the move number to achieve that distribution can be computed.

Let the disks be labeled ''n'', ''n''-1,…,1, in decreasing size. Let the pegs '''A''', '''B''', and '''C''' be labeled 0, 1, and 2 respectively, with 0 always being the starting peg and 2 always being the ending peg. Further, let the bases for the pegs upon which the disks are stacked be labeled ''n''+1, ''n''+2, and ''n''+3, for pegs 0, 1, and 2 respectively.

The disk positions after move ''m'' can be mapped from the binary representation of ''m'' by the following rules:<ref>T.R. Walsh, ''The Towers of Hanoi revisited: moving the rings by counting the moves'', Information Processing Letters, 1982, Vol.15, 64-67. Netherlands.</ref>

* There is 1 binary digit (bit) in ''m'' for each disk.

* The bitstring for ''m'' is read from left to right, and each bit can be used to map the location of the corresponding disk, from disk ''n'' to disk 1.
* The most significant (leftmost) bit represents the largest disk, disk ''n''. A value of 0 indicates that the largest disk is on the starting peg 0 ('''A'''), while a 1 indicates that it is on the final peg 2 ('''C''').
* After any move:

# Each disk is stacked on another disk, or an empty base, in opposite [[Parity (mathematics)|parity]] order. That is to say: 5>4>3 (3 over 4 over 5) is valid; 5>4>2 (with 2 over 4) is invalid.
# Exactly 1 of the top labels (disk number or empty base) is even (for even ''n;'' otherwise exactly 1 is odd).
# A bit with the same value as the previous digit means that the corresponding disk is stacked on top of the previous disk. That is to say: a contiguous sequence of 1s or 0s means that the corresponding disks are all on the same peg.

* A bit with a different value than the previous one means that the corresponding disk is on another peg and not on the previous stack. Given 1) above, only 1 choice of the remaining 2 pegs is a legal placement. Note that after the placement of the first set of disks, every “placement round” starts and ends with 1 of the potential pegs having even parity, the other having odd.

For example, in 8-disk Tower of Hanoi:

* Move 0 = 00000000.
** The largest disk (leftmost) bit is 0, so it is on the starting peg (0).
** All other disks are 0 as well, so they are stacked on top of it. Hence all disks are on the starting peg, in the puzzle's initial configuration.
* Move 255<sub>10</sub> (2<sup>8</sup> − 1) = 11111111.
** The largest disk bit is 1, so it is on the final peg (2).
** All other disks are 1 as well, so they are stacked on top of it. Hence all disks are on the final peg and the puzzle is solved.
* Move 216<sub>10</sub> = 11011000.
** The largest disk bit is 1, so disk 8 is on the final peg (2). Note that it sits on base number 11 (11>8).
** Disk 7 is also 1, so it is stacked on top of disk 8 (11>8>7).
** Disk 6 is 0, so it is on another peg. Peg 1 is empty but its base number is 10.  The 6 disk cannot sit on the 10 base (both are even).  Therefore disk 6 is placed on peg 0 (9>6).
** Disk 5 is 1, so it is on another peg. Since peg 2 is now topped with 7, it cannot go there. Therefore disk 5 is placed on peg 1 (10>5).
** Disk 4 is also 1, so it is stacked on top of disk 5 (10>5>4).
** Disk 3 is 0, so it is on another peg. Since peg 2 is topped with 7, it cannot go there. Disk 3 is placed on peg 0 (9>6>3).
** Disks 2 and 1 are also 0, so they are stacked on top of disk 3 (9>3>2>1).

The source and destination pegs for the ''m''th move (excluding move 0) can be found elegantly from the binary representation of ''m'' using [[Bitwise operation|bitwise operations]]. To use the syntax of the [[C programming language]], move ''m'' is:

from peg<code>(m & m - 1) % 3</code> to peg <code>((m | m - 1) + 1) % 3</code>.

Another formulation for this is:

from peg <code>(m - (m & -m)) % 3</code> to peg <code>(m + (m & -m)) % 3</code>. 

These hold for odd ''n'' puzzles.  For even ''n'' puzzles, the output references to pegs 1 and 2 need to be reversed.

Furthermore, the single disk to be moved for any specific move is determined by the number of times the move count (''m'') can be divided by 2 (i.e. the number consecutive zero bits at the right of ''m''), and then adding 1.  In the example above for move 216, with 3 right hand 0s, disk 4 (3 + 1) is moved from peg 2 to peg 1.

=== Gray-code solution ===
{{More citations needed section|date=January 2024}}
The binary numeral system of [[Gray code]]s 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]], the Gray code operates on the premise that each value differs from its predecessor by only one bit changed.

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 that 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.<ref>{{cite book |first=Charles D. |last=Miller |title=Mathematical Ideas |chapter=Ch. 4: Binary Numbers and the Standard Gray Code |edition=9 |publisher=Addison Wesley Longman |year=2000 |isbn=978-0-321-07607-6 |url-status=dead |archive-url=https://web.archive.org/web/20040821062630/http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower |archive-date=2004-08-21 |url=http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html }}</ref>

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, ... {{OEIS|id=A001511}},<ref>{{Cite book|title=Théorie du Baguenodier|last=Gros|first=L.|publisher=Aimé Vingtrinier|year=1872|location=Lyon}}</ref> a sequence also known as the [[ruler function]], or one more than the power of 2 within the move number. In the [[Wolfram Language]], <code>IntegerExponent[Range[2^8 - 1], 2] + 1</code> gives moves for the 8-disk puzzle.

== Graphical representation ==
{{main|Hanoi graph}}

The game can be represented by an [[Graph (discrete mathematics)#Undirected graph|undirected graph]], the nodes representing distributions of disks and the edges representing moves. For one disk, the graph is a triangle:

[[file:tower_of_hanoi_graph.svg|lang=en-simple|120px|center]]

The graph for two disks is three triangles connected to form the corners of a larger triangle.

A second letter is added to represent the larger disk. Clearly, it cannot initially be moved.

The topmost small triangle now represents the one-move possibilities with two disks:

[[file:tower_of_hanoi_graph.svg|lang=tw|200px|center]]

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:

[[file:tower_of_hanoi_graph.svg|lang=en|400px|center]]
[[File:Hanoi-Graph-7.svg|thumb|right|The game graph of level 7 shows the relatedness to the [[Sierpiński triangle]].]]
* call the pegs a, b, and c
* list disk positions from left to right in order of increasing size

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.

In general, for a puzzle with ''n'' disks, there are [[Power of three|3<sup>''n''</sup>]] 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''&nbsp;+&nbsp;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 3<sup>''n''+1</sup> 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 3<sup>64</sup>&nbsp;−&nbsp;1 moves, or more than 10<sup>23</sup> years.

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

[[file:tower_of_hanoi_graph.svg|lang=pa|400px|center]]

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

The [[Hamiltonian cycle]] for three disks is:

[[file:tower_of_hanoi_graph.svg|lang=cy|400px|center]]

The graphs clearly show that:
* From every arbitrary distribution of disks, there is exactly one shortest way to move all disks onto one of the three pegs.
* Between every pair of arbitrary distributions of disks there are one or two different shortest paths.
* From every arbitrary distribution of disks, there are one or two different longest non-self-crossing paths to move all disks to one of the three pegs.
* Between every pair of arbitrary distributions of disks there are one or two different longest non-self-crossing paths.
* Let ''N''<sub>''h''</sub> be the number of non-self-crossing paths for moving a tower of ''h'' disks from one peg to another one. Then:
** ''N''<sub>1</sub> = 2
** ''N''<sub>''h''+1</sub> = (''N''<sub>''h''</sub>)<sup>2</sup> + (''N''<sub>''h''</sub>)<sup>3</sup>
This gives ''N''<sub>''h''</sub> to be 2, 12, 1872, 6563711232, ... {{OEIS|id=A125295}}

== Variations ==
=== Linear Hanoi ===
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<sup>''n''</sup> − 1 moves. The solution uses all 3<sup>n</sup> 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<sup>''n''</sup> − 1) / 2 moves.<ref>{{Cite web |title=Question Corner -- Generalizing the Towers of Hanoi Problem |url=https://www.math.toronto.edu/mathnet/questionCorner/genhanoi.html |access-date=2023-07-28 |website=math.toronto.edu}}</ref><ref>{{Cite book |last1=Hinz |first1=Andreas M. |title=The Tower of Hanoi – Myths and Maths |last2=Klavzar |first2=Sandi |last3=Milutinovic |first3=Uros |last4=Petr |first4=Ciril |last5=Stewart |first5=Ian |publisher=[[Springer Science+Business Media]] |year=2013 |isbn=9783034802369 |edition=1st |location=Basel |pages=241–259 |language=en}}</ref>

=== 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.<ref>{{cite journal |first=T. D. |last=Gedeon |title=The Cyclic Towers of Hanoi: An Iterative Solution Produced by Transformation |journal=The Computer Journal |volume=39 |issue=4 |year=1996 |doi=10.1093/comjnl/39.4.353 |pages=353–356}}</ref> 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:
{|
| || {{nowrap|1=C(n) = A(n−1) n A(n−1)}} || and || {{nowrap|1=A(n) = A(n−1) n C(n−1) n A(n−1).}}
|-
| style="padding:1ex 3ex;"|
|-
| 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:

# The move-patterns of transferring a tower of disks from a peg to another peg are symmetric with respect to the center points.
# The smallest disk is the first and last disk to move.
# Groups of the smallest disk moves alternate with single moves of other disks.
# 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.<ref>{{cite journal |first= T.|last=Bousch|title=La quatrieme tour de Hanoi|journal=Bull. Belg. Math. Soc. Simon Stevin|volume= 21|year=2014|issue=5|pages=895–912 |doi=10.36045/bbms/1420071861|s2cid=14243013|url= https://pdfs.semanticscholar.org/fb87/0a772baf96a2e11901122a2b04c3dd25596d.pdf|archive-url= https://web.archive.org/web/20170921001150/https://pdfs.semanticscholar.org/fb87/0a772baf96a2e11901122a2b04c3dd25596d.pdf|url-status= dead|archive-date= 2017-09-21}}</ref>

However, in case of four or more pegs, the Frame–Stewart algorithm is known without proof of optimality since 1941.<ref>{{cite journal |first1=B. M. |last1=Stewart |first2=J. S. |last2=Frame |title=Solution to advanced problem 3819 |journal=American Mathematical Monthly |volume=48 |issue=3 |pages=216–9 |doi=10.2307/2304268 |date=March 1941 |jstor=2304268}}</ref>

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.<ref>{{cite journal |first1=Sandi |last1=Klavzar |first2=Uro |last2=Milutinovi |first3=Ciril |last3=Petrb |title=Variations on the Four-Post Tower of Hanoi Puzzle |journal=Congressus Numerantium |volume=102 |year=2002|url=https://core.ac.uk/download/pdf/81954097.pdf |format=Postscript}}</ref>

For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper.<ref>{{cite journal |first=Paul |last=Stockmeyer |title=Variations on the Four-Post Tower of Hanoi Puzzle |journal=Congressus Numerantium |volume=102 |year=1994 |pages=3–12 |url=http://www.cs.wm.edu/~pkstoc/boca.ps |format=Postscript}}</ref>

The so-called Towers of Bucharest and Towers of Klagenfurt game configurations yield [[Ternary numeral system|ternary]] and [[pentary]] Gray codes.<ref name="Herter-Rote_2016"/>

==== Frame–Stewart algorithm ====
The Frame–Stewart algorithm is described below:
* Let <math>n</math> be the number of disks.
* Let <math>r</math> be the number of pegs.
* Define <math>T(n,r)</math> to be the minimum number of moves required to transfer n disks using r pegs.
The algorithm can be described recursively:
# For some <math>k</math>, <math>1 \leq k < n</math>, transfer the top <math>k</math> disks to a single peg other than the start or destination pegs, taking <math>T(k,r)</math> moves.
# Without disturbing the peg that now contains the top <math>k</math> disks, transfer the remaining <math>n-k</math> disks to the destination peg, using only the remaining <math>r-1</math> pegs, taking <math>T(n-k,r-1)</math> moves.
# Finally, transfer the top <math>k</math> disks to the destination peg, taking <math>T(k,r)</math> moves.
The entire process takes <math>2T(k,r)+T(n-k,r-1)</math> moves. Therefore, the count <math>k</math> should be picked for which this quantity is minimum. In the 4-peg case, the optimal <math>k</math> equals <math>n - \left\lfloor\sqrt{2n+1}\right\rceil + 1</math>, where <math>\left\lfloor\cdot\right\rceil</math> is the [[nearest integer function]].<ref name="Berkey Colortran">{{cite web | url=https://berkeycolortran.wordpress.com/2014/04/05/week-12-update/ | title=University of Toronto CSC148 Slog | date=April 5, 2014 | access-date=July 22, 2015}}</ref> For example, in the UPenn CIS 194 course on Haskell, the first assignment page<ref "name=UPenn CIS">{{cite web | url=http://www.seas.upenn.edu/~cis194/spring13/hw/01-intro.pdf | title=UPenn CIS 194 Introduction to Haskell Assignment 1 | access-date=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 is presumed to be optimal for any number of pegs; its number of moves is 2<sup>[[Big O notation|Θ]](''n''<sup>1/(''r''−2)</sup>)</sup> (for fixed ''r'').

=== 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 Tat-Hung independently discovered<ref>{{cite journal |first=A. |last=Hinz |title=The Tower of Hanoi |journal=L'Enseignement Mathématique |volume=35 |year=1989 |pages=289–321 |doi=10.5169/seals-57378 }}</ref><ref>{{cite journal |first=T. |last=Chan |title=A statistical analysis of the towers of Hanoi problem |journal=Internat. J. Comput. Math. |volume=28 |issue=1–4 |year=1988 |pages=57–65 |doi=10.1080/00207168908803728}}</ref> (see also
<ref>{{cite book |last=Stewart |first=Ian |title=Another Fine Math You've Got Me Into... |publisher=Courier Dover |year=2004 |isbn=978-0-7167-2342-4 }}</ref>{{rp|Chapter 1, p.&nbsp;14}}) that the average number of moves in an n-disk Tower is given by the following exact formula:

:<math> \frac{466}{885}\cdot 2^n - \frac{1}{3} - \frac{3}{5}\cdot \left(\frac{1}{3}\right)^n +
\left(\frac{12}{59} + \frac{18}{1003}\sqrt{17}\right)\left(\frac{5+\sqrt{17}}{18}\right)^n +
\left(\frac{12}{59} - \frac{18}{1003}\sqrt{17}\right)\left(\frac{5-\sqrt{17}}{18}\right)^n.</math>

For large enough ''n'', only the first and second terms do not converge to zero, so we get an [[asymptotic analysis|asymptotic expression]]: <math>466/885\cdot 2^n - 1/3 + o(1)</math>, as <math>n \to \infty</math>. Thus intuitively, we could interpret the fraction of <math>466/885\approx 52.6\%</math> 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 <math>2^n - 1</math> 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.<ref>{{cite journal |first=D. |last=Romik |title=Shortest paths in the Tower of Hanoi graph and finite automata |journal=[[SIAM Journal on Discrete Mathematics]] |volume=20 |issue=3 |year=2006 |pages=610–622 |doi=10.1137/050628660|arxiv=math/0310109 |s2cid=8342396 }}</ref>

=== Magnetic Hanoi ===
{{Main|Magnetic Tower of 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.
[[File:BTOHIC.jpg|thumb|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.<ref>{{Cite journal|url=http://rmm.ludus-opuscula.org/PDF_Files/Chaugule_BicolorHanoi_37_48(4_2015)_low.pdf|journal=Recreational Mathematics Magazine|issue= 4|pages=37–48|title=A Recursive Solution to Bicolor Towers of Hanoi Problem|date=2015|issn=2182-1976
|author=Prasad Vithal Chaugule}}</ref>

[[File:BTOHFC.jpg|thumb|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.

===Tower of Hanoy===
<!--"Hanoy" here is the actual spelling used in the card game title, not a typo-->
A variation of the puzzle has been adapted as a [[Solitaire (game)|solitaire game]] with nine playing cards under the name [[Tower of Hanoy]].<ref>{{Cite book|last=Arnold|first=Peter|url=https://books.google.com/books?id=M7C5-R0pGEQC&q=%22tower+of+hanoy%22&pg=PA70|title=Card Games for One|date=2003-05-28|publisher=Sterling Publishing Company|isbn=978-0-600-60727-4|language=en}}</ref><ref>{{Cite book|last=Hedges|first=Sid G.|url=https://books.google.com/books?id=Jd1PDwAAQBAJ&q=%22tower+of+hanoy%22&pg=PT141|title=Everybody's Book of Hobbies|date=2018-03-06|publisher=Read Books Ltd|isbn=978-1-5287-8344-6|language=en}}</ref> It is not known whether the altered spelling of the original name is deliberate or accidental.<ref>{{Cite web|title=Tower Of Hanoy Patience (AKA Tower Of Hanoi Patience)|url=http://bbcmicro.co.uk//game.php?id=3366&h=h|access-date=2020-10-17|website=bbcmicro.co.uk|language=en}}</ref>

== Applications ==
[[File:Palladium nanosheet on silicon wafer.jpg|thumb|3D AFM topographic image of multilayered palladium nanosheet on silicon wafer, with Tower of Hanoi-like structure.<ref name="Nano">{{cite journal|last1=Yin|first1=Xi|last2=Liu|first2=Xinhong|last3=Pan|first3=Yung-Tin|last4=Walsh|first4=Kathleen A.|last5=Yang|first5=Hong|title=Hanoi Tower-like Multilayered Ultrathin Palladium Nanosheets|journal=Nano Letters|date=November 4, 2014|doi=10.1021/nl503879a|pmid=25369350|volume=14|issue=12|pages=7188–94|bibcode=2014NanoL..14.7188Y}}</ref>]]
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 Test|Tower of London]] for neuropsychological diagnosis and treatment of disorders of [[executive function]].<ref>{{Cite journal |date=1982-06-25 |title=Specific impairments of planning |url=https://royalsocietypublishing.org/doi/10.1098/rstb.1982.0082 |journal=Philosophical Transactions of the Royal Society of London. B, Biological Sciences |language=en |volume=298 |issue=1089 |pages=199–209 |doi=10.1098/rstb.1982.0082 |pmid=6125971 |issn=0080-4622 |last1=Shallice |first1=T. |bibcode=1982RSPTB.298..199S }}</ref>

Zhang and Norman<ref>{{cite journal|doi=10.1016/0364-0213(94)90021-3|url=http://wexler.free.fr/library/files/zhang%20%281994%29%20representations%20in%20distributed%20cognitive%20tasks.pdf|title=Representations in distributed cognitive tasks|journal=Cognitive Science|volume=18|pages=87–122|year=1994|last=Zhang|first=J}}</ref> 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<ref>{{Cite journal|doi=10.1016/j.jbi.2011.08.005|pmid=21867774|title=TURF: Toward a unified framework of EHR usability|journal=Journal of Biomedical Informatics|volume=44|issue=6|pages=1056–67|year=2011|last1=Zhang|first1=Jiajie|last2=Walji|first2=Muhammad F.|doi-access=free}}</ref> 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.<ref>{{Cite report |url=https://doi.org/10.21236/ada218927 |title=Tower-Noticing Triggers Strategy-Change in the Tower of Hanoi: A Soar Model |last1=Ruiz |first1=Dirk |last2=Newell |first2=Allen |date=1989-06-01 |publisher=Defense Technical Information Center |location=Fort Belvoir, VA|doi=10.21236/ada218927 }}</ref>

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]].{{citation needed |date=September 2023}}

The Tower of Hanoi is also used as a test by neuropsychologists trying to evaluate [[frontal lobe]] deficits.<ref>{{Cite journal | url=https://ajp.psychiatryonline.org/doi/pdf/10.1176/ajp.156.5.777 | doi=10.1176/ajp.156.5.777| pmid=10327915| year=1999| last1=Beers| first1=S. R.| title=Neuropsychological study of frontal lobe function in psychotropic-naive children with obsessive-compulsive disorder| journal=The American Journal of Psychiatry| volume=156| issue=5| pages=777–9| last2=Rosenberg| first2=D. R.| last3=Dick| first3=E. L.| last4=Williams| first4=T.| last5=O'Hearn| first5=K. M.| last6=Birmaher| first6=B.| last7=Ryan| first7=C. M.| s2cid=21359382}}</ref>

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.<ref>{{cite journal |last1=Reid |first1=C.R. |last2=Sumpter |first2=D.J. |last3=Beekman |first3=M. |title=Optimisation in a natural system: Argentine ants solve the Towers of Hanoi |journal=J. Exp. Biol. |volume=214 |issue=Pt 1 |pages=50–8 |date=January 2011 |pmid=21147968 |doi=10.1242/jeb.048173 |bibcode=2011JExpB.214...50R |citeseerx=10.1.1.231.9201 |s2cid=18819977 }}</ref>

In 2014, scientists synthesized multilayered [[palladium]] nanosheets with a Tower of Hanoi-like structure.<ref name="Nano"/>

== In popular culture ==
In the science fiction story "Now Inhale", by [[Eric Frank Russell]], 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.<ref>{{cite magazine |journal=Astounding Science Fiction |date=April 1959 |first=Eric Frank |last=Russell |title=Now Inhale |volume = 63 |issue = 2 |department=Novelettes |pages=31–77 |url=https://archive.org/details/Astounding_v63n02_1959-04_EXciter-LennyS/page/n30/mode/1up}}
* Reprinted: {{cite book| editor-last=Katze |editor-first=Rick |title=Major Ingredients: The Selected Short Stories of Eric Frank Russell |date=2000 |pages=399–417 |chapter=Now Inhale |last=Russell |first=Eric Frank |location=Framingham, Mass. |publisher=NESFA Press |isbn=978-1-886778-10-8 |ref=none}}</ref><ref name="Self-Similar Groups">{{cite book |last1=Bonanome |first1=Marianna C. |last2=Dean |first2=Margaret H. |last3=Dean |first3=Judith Putnam |title=A Sampling of Remarkable Groups: Thompson's, Self-similar, Lamplighter, and Baumslag-Solitar |date=2018 |publisher=Springer |location=Cham, Switzerland |doi=10.1007/978-3-030-01978-5_3 |page=96 |chapter=Self-Similar Groups|series=Compact Textbooks in Mathematics |isbn=978-3-030-01976-1 }}</ref><ref>{{cite journal |last=Birtwistle |first=Graham |title=The coroutines of Hanoi |journal=ACM SIGPLAN Notices |date=January 1985 |volume=20 |issue=1 |pages=9–10 |doi=10.1145/988284.988286 |s2cid=7310661 }}</ref>

In the 1966 ''[[Doctor Who]]'' story ''[[The Celestial Toymaker]]'', the [[eponym]]ous 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.<ref name="Self-Similar Groups"/><ref>{{cite web |title=The Fourth Dimension: The Celestial Toymaker |url=https://www.bbc.co.uk/programmes/articles/3DHlYgfSdY2RlXkS2KwjtKK/the-fourth-dimension |website=Doctor Who |publisher=BBC One |access-date=April 2, 2021}}</ref>

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 disks 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 2011 film ''[[Rise of the Planet of the Apes]]'', this puzzle, called in the film the "Lucas Tower", is used as a test to study the [[intelligence of apes]].<ref name="Self-Similar Groups"/>

The puzzle is featured regularly in [[adventure game|adventure]] and [[computer puzzle game|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 (video game)|Star Wars: Knights of the Old Republic]]'' and ''[[Mass Effect (video game)|Mass Effect]]'').<ref>{{cite web |url=http://www.giantbomb.com/tower-of-hanoi/92-5744/ |title=Tower of Hanoi (video game concept) |publisher=Giantbomb.com |access-date=2010-12-05}}</ref> Some implementations use straight disks, but others disguise the puzzle in some other form. There is an arcade version by [[Sega]].<ref>{{cite web|url=http://www.segaarcade.com/towerofhanoi |title=Tower of Hanoi / Andamiro |publisher=Sega Amusements |access-date=2012-02-26 |url-status=dead |archive-url=https://web.archive.org/web/20120301060428/http://www.segaarcade.com/towerofhanoi |archive-date=2012-03-01 }}</ref>

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 [[32,767]] moves to complete. If an especially dedicated player does click through to the end of the puzzle, it is revealed that completing the puzzle does not unlock the door.

This was first used as a challenge in ''Survivor'' Thailand in 2002 but rather than rings, the pieces were made to resemble a temple. Sook Jai threw the challenge to get rid of Jed even though Shii-Ann knew full well how to complete the puzzle.
The problem is featured as part of a reward challenge in a [[Survivor: South Pacific#Episode 1: "I Need Redemption"|2011 episode of the American version of the ''Survivor'' TV series]]. Both players ([[Ozzy Lusth]] and [[Coach (Survivor contestant)|Benjamin "Coach" Wade]]) struggled to understand how to solve the puzzle and are aided by their fellow tribe members.

In ''[[Genshin Impact]]'', this puzzle is shown in Faruzan's hangout quest, "Early Learning Mechanism", where she mentions seeing it as a mechanism and uses it to make a toy prototype for children. She calls it [[pagoda]] stacks.

== See also ==
{{Puzzles |Types}}
* [[ABACABA pattern]]
* [[Backup rotation scheme]], a TOH application
* [[Baguenaudier]]
* [[Recursion (computer science)]]
* "[[The Nine Billion Names of God]]", 1953 Arthur C. Clark short story with a similar premise to the game's framing story
{{Clear}}

== Notes ==
{{reflist|refs=
<ref name="Herter-Rote_2016">{{cite journal |title=Loopless Gray Code Enumeration and the Tower of Bucharest |first1=Felix |last1=Herter |first2=Günter |last2=Rote |publication-place=Berlin, Germany |orig-date=2018-08-09, 2017-12, 2017-08-09, 2016-04-22 |date=2018-11-14 |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |issn=0304-3975 |volume=748 |arxiv=1604.06707<!-- 24 pages --> |s2cid=4014870 |doi=10.1016/j.tcs.2017.11.017 |pages=40–54 |url=https://page.mi.fu-berlin.de/rote/Papers/pdf/Loopless+Gray+code+enumeration+and+the+Tower+of+Bucharest.pdf<!-- 18 pages --> |access-date=2020-12-16 |url-status=live |archive-url=https://web.archive.org/web/20201216150701/https://page.mi.fu-berlin.de/rote/Papers/pdf/Loopless+Gray+code+enumeration+and+the+Tower+of+Bucharest.pdf |archive-date=2020-12-16}} [https://web.archive.org/web/20201216230211/https://arxiv.org/pdf/1604.06707.pdf] (15/18/19/24 pages)</ref>
}}

== External links ==
{{Commons category|Tower of Hanoi}}
* {{mathworld|title=Tower of Hanoi|urlname=TowerofHanoi}}

[[Category:1883 introductions]]
[[Category:1889 documents]]
[[Category:19th-century inventions]]
[[Category:French inventions]]
[[Category:Mechanical puzzles]]
[[Category:Mathematical puzzles]]
[[Category:Articles with example C code]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Divide-and-conquer algorithms]]