Editing Tower of Hanoi (section)

== 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>