The ultimate tower of Hanoi algorithm

Video Description

There must be millions of people who have heard of the Tower of Hanoi puzzle and the simple algorithm that generates the simplest solution. But what happens when you are playing the game not with three pegs, as in the original puzzle, but with 4, 5, 6 etc. pegs? Hardly anybody seems to know that there are also really really beautiful solutions which are believed to be optimal but whose optimality has only been proved for four pegs. Even less people know that you can boil down all these optimal solutions into simple no-brainer recipes that allow you to effortless execute these solutions from scratch. Clearly a job for the Mathologer. Get ready to dazzle your computer science friends :) I also talk about 466/885, the Power of Hanoi constant and a number of other Hanoi facts off the beaten track. And the whole thing has a Dr Who hook which is also very cute. 00:00 Intro 01:58 Chapter 1: The doctor vs. the toymaker 14:27 Chapter 2: Hanoi constant 21:21 Chapter 3: The Reve's puzzle 28:04 A beautiful shortest solution for 10 discs and 4 pegs (discs and super-disks) 30:23 Chapter 4: Unprovable algorithm 35:43 A beautiful shortest solution for 10 discs and 5 pegs (discs, super-discs and super-super-discs) 37:17 Supporters Here are some references for you to check out: Andreas M. Hinz et al. - The Tower of Hanoi – Myths and Maths, 2nd edition (2018, Birkhäuser Basel) That's the book I mentioned in the video. The Dr Who episode (well the part that's not been lost) https://www.dailymotion.com/video/x119oe7 The 3Blue1Brown video that I mention https://youtu.be/2SUvWfNJSsM Thierry Bousch, La quatrième tour de Hanoi, http://tinyurl.com/4p3fudu7 That's the paper that pins down things for four pegs. Andreas M. Hinz, Dudeney and Frame-Stewart Numbers, A nice paper explaining the connection between Dudeneys's work and Frame-Stewart. Also worth reading for the historical details. http://tinyurl.com/t8xb2e5t A. van de Liefvoort, An Iterative Algorithm for the Reve's Puzzle, http://tinyurl.com/h5cxfy5u I found this one useful. Paul K. Stockmeyer, http://www.cs.wm.edu/~pkstoc/toh.html A couple of very nice papers including a huge bibliography. Ben Houston & Hassan Masum, Explorations in 4-peg Tower of Hanoi, tinyurl.com/mw95tnek This paper has some pictures of state graphs for the 4-peg puzzle. http://towersofhanoi.info/Animate.aspx Very fancy animation of mulit-peg tower of Hanoi. Sadly, it just comes across as a mess of moves for more than three pegs. Programmers, you really should rise to my challenge to animate the 4-peg algorithm the way I present it in this video. Here is the link to the wiki page for the Celestial toymaker Dr Who episode https://en.wikipedia.org/wiki/The_Celestial_Toymaker Makes very interesting reading. Especially the fact that most of this episode has been lost I find pretty amazing. That's also why I only show a still image from the relevant part of the episode and play some audio snippet. Music: Fresh Fallen Snow and Morning Mandolin both by Chris Haugen, Mumbai effect. All from the free YouTube audio library. Enjoy! Burkard