Editing Tower of Hanoi (section)

=== 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'').