De torens van Hanoi als screensaver
De screensaver GLHanoi uit de xscreensaver-collectie toont de zogenaamde torens van Hanoi, waarover ik eerder al eens schreef. Deze bekende puzzel werd in 1883 door de Franse wiskundige Édouard Lucas geïntroduceerd. Hij verwijst daarbij naar een legende over een Indische tempel die boven het centrum van de wereld staat. De tempel heeft een grote koepel waarin drie diamanten staven staan. Op één van deze staven heeft God in het begin van de wereld 64 gouden schijven bevestigd, de grootste vanonder en de kleinste bovenaan. Priesters verplaatsen deze schijven dag en nacht, slechts één per keer en nooit een grotere schijf op een kleinere. De puzzel is opgelost wanneer de toren van 64 schijven verplaatst is naar een andere staaf. Op dat moment zal volgens de legende de wereld eindigen.
Van deze puzzel bestaan eenvoudige recursieve oplossingen, die heel efficiënt kunnen berekend worden. De torens van Hanoi worden dan ook vaak in cursussen programmeren als oefening gebruikt. In plaats van 64 schijven wordt vaak een eenvoudiger variant bekeken, namelijk met drie schijven. Dit verandert eigenlijk niets aan de kern van het probleem, want een oplossing voor N-1 schijven is eenvoudig uit te breiden tot een oplossing voor N schijven.
De screensaver GLHanoi toont een geanimeerde oplossing van de puzzel. Screenshots van de puzzel in actie voor 3 en voor 9 schijven zijn hier te zien:
Post a Comment