Toren van Hanoi online spelen

De puzzel bestaat uit drie pinnen en een stapel schijven die naar boven toe kleiner worden. De hele stapel moet van de linkerpin naar de rechterpin. Je verplaatst één schijf per zet, je pakt alleen de bovenste schijf van een pin, en een grotere schijf komt nooit op een kleinere te liggen. De middelste pin is de hulppin, waar schijven tijdelijk wachten.

In het spel heten de pinnen A, B en C, van links naar rechts; pin C is het doel, gemarkeerd met ‘doel’. Schijf 1 is de kleinste schijf, en de grootste schijf ligt onderop. Een zet tegen de regels weigert het spel met de reden erbij, zoals ‘Schijf 2 kan niet op schijf 1’, en het bord schudt even. Wie in het systeem minder beweging heeft ingesteld, ziet dat schudden niet.

Het is een denkspel voor één persoon, zonder toeval: er wordt niets gegooid of getrokken. Andere namen voor de pinnen zijn stokjes en staven; het tijdschrift Pythagoras schrijft stokjes.

Een schijf verplaats je in twee tikken: tik op een pin om de bovenste schijf op te pakken, en daarna op de pin waar hij heen moet. Slepen kan ook. Op een computer ga je met Tab naar een pin en kies je met het cijfer of de letter van een pin. Escape legt een opgepakte schijf terug, en de pijltjestoetsen springen van pin naar pin.

Boven het bord staan drie tellers. ‘Zetten’ telt de zetten op het bord, en ‘Minimum’ toont het kleinste aantal zetten vanaf het begin van dit spel. ‘Tijd’ loopt vanaf je eerste zet tot de toren compleet is. ‘Ongedaan maken’ werkt zo vaak als je wilt, maar elke teruggenomen zet wordt geteld.

‘Tip’ toont vanuit elke stand de volgende zet van een kortste weg naar het doel. De pin van vertrek en die van aankomst lichten op, met een regel als ‘Tip: zet schijf 2 van A naar C’, en ook tips worden geteld. Met ‘Oplossen’ maakt de oplosser het werk af vanaf waar de schijven nu liggen.

Tussen twee zetten wacht de oplosser 0,9 seconde op ‘Langzaam’ en 0,045 seconde op ‘Zeer snel’. Je kunt hem pauzeren of één zet tegelijk laten doen, en met ‘Zelf verder’ speel je vanaf die stand zelf verder.

Is de toren compleet, dan zie je je zetten naast het minimum, de tijd in tienden van een seconde en het aantal tips en teruggenomen zetten. ‘Resultaat kopiëren’ zet een regel met de link op je klembord. De link onthoudt het aantal schijven en pinnen, het begin, de snelheid en of er nummers op de schijven staan.

Met n schijven heb je minimaal 2^n - 1 zetten nodig: 7 bij 3 schijven, 31 bij 5 en 1.023 bij 10. Wie elke seconde een zet doet, is met 10 schijven al 17 minuten en 3 seconden bezig.

Waarom precies dat aantal? Om de grootste schijf te verplaatsen, moeten alle kleinere eerst naar de hulppin: zelf een toren van n - 1 schijven. Dan gaat de grootste schijf in één zet naar het doel, en daarna moet de kleinere toren er weer bovenop. Er geldt dus T(n) = 2T(n - 1) + 1, en met volledige inductie volgt daaruit 2^n - 1.

Zo leggen Plus magazine van de University of Cambridge en het hoofdstuk over recursie van Princeton University het uit. Lucas schreef het eenvoudiger: elke extra schijf verdubbelt het aantal zetten en telt er één bij op. Zijn tabel en de rij A000225 uit de OEIS staan ook bij de controle met bekende antwoorden.

Die verdubbeling maakt de groei exponentieel, en het aantal standen in de laatste kolom groeit nog sneller: per schijf keer drie. Exponentiële complexiteit hoort bij keuzedomein G van het examenprogramma informatica voor havo en vwo, zo staat in de handreiking van SLO. Die handreiking noemt de puzzel zelf nergens.

De kortste oplossing met 5 schijven telt 31 zetten en begint met de kleinste schijf van A naar C. Bij een oneven aantal schijven gaat schijf 1 eerst naar het doel, bij een even aantal schijven eerst naar de hulppin B.

Achter die lijst zit een vast ritme. De kleinste schijf is bij elke oneven zet aan de beurt en draait altijd dezelfde kant op. Bij 5 schijven is de volgorde A, C, B, A en zo verder, bij 4 schijven A, B, C, A. Lucas schrijft deze regel in Récréations mathématiques toe aan zijn neef Raoul Olive, een leerling van het lycée Charlemagne.

In de eerste 8 zetten van de tabel bewegen de schijven 1, 2, 1, 3, 1, 2, 1 en 4. Het nummer is telkens één meer dan het aantal nullen waarop het zetnummer binair eindigt. De OEIS kent die rij als A001511, de ruler function. Zo beweegt schijf k precies 2^(n-k) keer: bij 5 schijven de kleinste 16 keer en de grootste 1 keer.

Kort samengevat werkt de iteratieve oplossing zo. Verplaats bij elke oneven zet de kleinste schijf één pin verder, altijd in dezelfde richting. Met een oneven aantal schijven gaat hij eerst naar C en dan naar B, met een even aantal eerst naar B en dan naar C. Doe bij elke even zet de enige andere zet die mag. Van de bovenste schijven op de twee pinnen zonder de kleinste kan alleen de kleinere op de grotere, of op een lege pin.

Wie zo doorgaat, verplaatst de hele toren in het minimale aantal zetten, 2^n - 1, zonder ooit een zet te verspillen. Met 3 schijven zijn dat 7 zetten: A naar C, A naar B, C naar B, A naar C, B naar A, B naar C en A naar C. Voor elk ander aantal schijven toont het spel zo'n lijst onder ‘De oplossing zet voor zet’, met de volgende zet gemarkeerd zolang je die volgt.

Recursie betekent dat je een probleem oplost met een kleinere versie van hetzelfde probleem. Het werkboek van de Open Universiteit voor de cursus IB1502 noemt de torens van Hanoi een wiskundige puzzel die ‘geldt als standaardvoorbeeld voor recursie’. De reden: hij laat zich op elegante wijze recursief oplossen.

In dat werkboek heten de pinnen bronstok, hulpstok en doelstok. De recursieve oplossing staat er in woorden, een soort pseudocode in drie stappen.

1. Verplaats de bovenste n - 1 schijven van de bronstok naar de hulpstok, met de doelstok als hulppin.
2. Verplaats de grootste schijf van de bronstok naar de doelstok.
3. Verplaats de n - 1 schijven van de hulpstok naar de doelstok, met de bronstok als hulppin.

Stap 1 en stap 3 zijn dezelfde opgave met een schijf minder, en vallen dus weer uiteen in drie stappen, tot er één schijf over is. Zo'n algoritme roept zichzelf steeds aan met een kleinere toren. In de handreiking van SLO voor informatica op havo en vwo hoort recursie bij subdomein B1, Algoritmen.

Dezelfde redenering werkt voor varianten. Het wiskundetijdschrift Pythagoras gaf in juni 2009 een puzzel met 4 schijven waarin geen schijf rechtstreeks tussen A en C mag, dus elke schijf via B moet. Elke extra schijf verdrievoudigt dan het aantal zetten en telt er twee bij op, blijkt uit de oplossing in het septembernummer: 80 zetten voor 4 schijven.

Op drie pinnen kunnen n schijven op 3^n manieren liggen: 81 standen bij 4 schijven, 59.049 bij 10. Kies je bij de opties ‘Een willekeurige stand’, dan legt het spel na een tik op ‘Maak een willekeurige stand’ elke schijf op een willekeurige pin, kleinere schijven altijd bovenop.

Elke verdeling is even waarschijnlijk, behalve dat de grootste schijf nooit al op het doel begint. Met 4 schijven kost zo'n begin daardoor minstens 8 en hoogstens 15 zetten, gemiddeld 12,7. Over alle 81 standen samen is het gemiddelde 10, twee derde van 15. Die gemiddelden telde deze site zelf, door elke stand door te rekenen.

Bij een willekeurige beginstand heet de middelste teller ‘Minimum vanaf start’, en tip, oplosser en zettenlijst gaan uit van die stand. De stand gaat mee in de link, zodat iemand anders precies hetzelfde begin krijgt. Een vierde pin maakt er 4^n standen van, al 65.536 bij 8 schijven. Voor een tip doorzoekt het spel ze allemaal, en daarom stopt die variant bij 8 schijven.

Teken je elke stand als een punt en elke zet als een lijntje, dan lijkt de figuur met elke extra schijf meer op de driehoek van Sierpinski. Dat beschrijft Plus magazine, en het boek The Tower of Hanoi: Myths and Maths van Andreas Hinz, Sandi Klavžar en Ciril Petr werkt het wiskundig uit.

De Franse wiskundige Édouard Lucas bracht de puzzel in 1883 uit als ‘la Tour d'Hanoï, véritable casse-tête annamite’. Hij gebruikte de schuilnaam ‘professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian’. Zo staat het in het Journal des Débats van 27 december 1883, aangehaald door Allardice en Fraser.

N. Claus de Siam is een anagram van Lucas d'Amiens, en Li-Sou-Stian van Saint Louis, het lycée waar Lucas lesgaf, legt MacTutor van de University of St Andrews uit. Het spel had 8 houten schijven; in deel 3 van zijn Récréations mathématiques (1893) noemt Lucas ze ‘huit pions en bois’.

Bij de puzzel hoorde vanaf het begin een verhaal. In de grote tempel van Benares in India verplaatsen priesters, de brahmanen, een toren van 64 puur gouden schijven tussen drie diamanten naalden. Ook zij nemen één schijf tegelijk, en een grotere ligt nooit op een kleinere. Zijn ze klaar, dan storten de toren en de brahmanen in, en vergaat de wereld.

Die legende verzon Lucas zelf. Volgens hem kwam het spel niet uit Tonkin, wat de folder ook beweerde. Spel en legende waren bedacht op nummer 56 van de rue Monge in Parijs. Henri de Parville vertelde het verhaal na in het tijdschrift La Nature, zoals W. W. Rouse Ball in Mathematical Recreations and Essays vermeldt.

In zijn Récréations mathématiques verzamelde Lucas meer spellen. Al in 1883 beschreef hij het potloodspel kamertje verhuren als ‘le jeu de l'École Polytechnique’, en in 1889 bracht hij het uit als La Pipopipette.

Psychologen gebruiken torentaken om plannen en probleemoplossen te bestuderen. In Plus magazine staat dat je mensen bij zo'n taak kunt zien denken. Tim Shallice beschreef in 1982 een planningstaak in zijn artikel Specific impairments of planning, over stoornissen in het plannen.

Jeremy Sullivan, Cynthia Riccio en Candace Castillo bespreken in een meta-analyse uit 2009 torentaken als maat voor executieve functies, de vaardigheden waarmee je doelen plant en je gedrag stuurt. Een studie van de Erasmus Universiteit Rotterdam noemt de Toren van Londen een veelgebruikt instrument voor planningsvaardigheid.

Dit spel is een puzzel en geen meetinstrument. De tellers houden geen score bij die klinisch iets betekent, en zeggen niets over intelligentie, ADHD of een andere eigenschap. Een andere klassieker uit het psychologielab staat hier ook als spel: de Stroop-test, met kleurwoorden in plaats van schijven.