Torens van Hanoi

De Torens van Hanoi is een spel of puzzel met een aantal schijven. Het spel bestaat uit een plankje met daarop drie stokjes. Bij aanvang van het spel is op een van de stokjes een piramidevormige 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:

1. er mag slechts 1 schijf tegelijk worden verplaatst
2. nooit mag een grotere schijf op een kleinere rusten

Om praktische redenen heeft de toren meestal 8 schijfjes, omdat een spel met dit aantal binnen een minuut of 6 op te lossen is. Iedere extra schijf verdubbelt de minimale oplostijd.

Analyse

Het is vrij gemakkelijk om aan te tonen dat het aantal benodigde zetten hiervoor gelijk is aan 2ⁿ-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.

Handmatig oplossen

Lost men de puzzel met de hand op, dan wordt er makkelijk een fout gemaakt, waardoor het oplossen langer duurt. Er is echter een eenvoudige manier om het wel goed te doen. Allereerst geldt natuurlijk:

• Verplaats nooit dezelfde schijf twee keer achter elkaar (uiteraard zinloos)
• Leg nooit een grotere schijf op een kleinere schijf (de spelregels verbieden het)

Nu geven we de schijven om en om verschillende kleuren, bijvoorbeeld rood, blauw, rood, blauw, enz. en we houden ons aan de volgende regel:

• Leg nooit twee schijven met dezelfde kleur op elkaar.

Volgens deze regels is er op elk moment maar een zet mogelijk - de juiste zet. Voor de eerste zet geldt:

• Is er een oneven aantal schijven, leg dan de eerste schijf op de stok waarop je uiteindelijk wilt eindigen. Is er een even aantal schijven, leg dan de eerste schijf op een andere stok.

Oorsprong

Het spel is uitgevonden door de Franse wiskundige Édouard Lucas in 1883. Er is een legende over een hindoe-tempel in de Indiase stad Benares onder keizer Fo Hi, waarvan de priesters, de Brahmanen, zich bezighouden met het verplaatsen van een toren van 64 gouden schijven. De schijven lagen op drie naalden van diamant, een el lang en zo dik als het lichaam van een bij. 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 2⁶⁴ - 1, is ongeveer 1,84×10¹⁹ seconden duren de puzzel af te maken. Dit komt overeen met 877.413.626.032,61 jaar, ruwweg 64 maal zo lang als de geschatte leeftijd van het universum.

Externe links

• Javasimulatie
• Hanoimania, meer dan 100 implementaties