Torens van Hanoi
De Torens van Hanoi is een spel of puzzeltje.
Inhoud |
[bewerk] Het spel
Het spel bestaat uit een plankje met daarop drie stokjes. Bij aanvang van het spel is op een van de stokjes een pyramidevormige toren van schijven met een gat in het midden geplaatst. Elke schijf heeft een verschillende diameter en de schijven zijn zo geplaatst dat de kleinste bovenop en de grootste onderop ligt.
Het doel van het spel is om de complete toren van schijven te verplaatsen naar een ander stokje, waarbij de volgende regels in acht genomen dienen te worden:
- er mag slechts 1 schijf tegelijk worden verplaatst
- nooit mag een grotere schijf op een kleinere rusten
Om praktische redenen heeft de toren meestal 8 schijfjes, omdat dit aantal binnen een minuut of 6 op te lossen is. Iedere schijf meer verdubbelt de minimale oplostijd.
[bewerk] Analyse
Het is vrij makkelijk aan te tonen dat het aantal benodigde zetten hiervoor gelijk is aan 2N-1, waarbij N het aantal schijven is.
Het is een geliefd probleem in programmeercursussen, omdat het zeer elegant op recursieve wijze op te lossen is.
De oplosfunctie kan in pseudocode als volgt worden geformuleerd:
functie hanoi (aantal, bronstok, doelstok); {
- als (aantal gelijk is aan 1),
- plaats dan de schijf op bronstok naar doelstok;
- anders
- hanoi ((aantal-1), bronstok, derde stok);
- hanoi (1, bronstok, doelstok));
- hanoi (aantal -1, derde stok, doelstok);
}
Hieraan is ook meteen te zien dat de oplossing voor 1 schijf minimaal 1 zet vergt, en voor een grotere toren minimaal 1 + tweemaal die van de 1 schijf kleinere toren.
1 schijf -> 1 zet 2 schijven -> 2*1 + 1 = 3 zetten 3 schijven -> 2*3 + 1 = 7 zetten 4 schijven -> 2*7 + 1 = 15 zetten
Het aantal zetten is steeds het dubbele aantal van de vorige stapel + 1.
Bij met de hand oplossen geldt de volgende regel: bij het verplaatsen van een (sub)torentje naar een andere stok moet men de eerste zet naar die doelstok doen bij een oneven aantal schijven, en naar de derde stok bij een even aantal schijven. (Het 'subtorentje' is steeds het grootst mogelijk aan te geven torentje zonder ontbrekende schijven erin).
[bewerk] Oorsprong
Het spel is uitgevonden door de Franse wiskundige Edouard Lucas in 1883. Er is een legende over een hindoe-tempel waarvan de priesters, de Brahmanen, zich bezighouden met het verplaatsen van een toren van 64 gouden schijven. Volgens de legende komt de wereld tot een einde als het werk af is. Het is niet duidelijk of Lucas deze legende bedacht heeft of er alleen door is geïnspireerd.
Aannemend dat de priesters 1 schijf per seconde zouden verplaatsen, zou het ongeveer 264 - 1, is ongeveer 1.8×1019 seconden duren de puzzel af te maken. Dit komt overeen met ongeveer 580.000.000.000 jaar, ruwweg veertig maal langer dan de geschatte leeftijd van het universum.
[bewerk] Externe links
Geschiedenis:
- http://hanoitower.mkolar.org/HThistory.html
- http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
Javasimulatie:
