title: Torens van Hanoi
text: 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 kegelvormige toren geplaatst van schijven met een gat in het midden. De schijven hebben verschillende diameters. Ze zijn zo geplaatst dat er geen grotere schijf op een kleinere schijf 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 ongeveer acht schijven, omdat een spel met dit aantal binnen enkele minuten op te lossen is. Iedere extra schijf verdubbelt de minimale oplostijd.
  
  Analyse
  
  Het is vrij gemakkelijk aan te tonen dat het probleem oplosbaar is, ongeacht het aantal schijven, en wel in  zetten voor een toren met  schijven.
  
  Het probleem is geliefd in programmeercursussen, omdat het zeer elegant op recursieve wijze op te lossen is.
  
  Recursie
  De oplossing is recursief te beschrijven. 
   Met 1 schijf: breng de schijf van pin A naar pin C.
   Met  schijven: los het probleem op door de bovenste  schijven naar pin B te brengen, met pin C als hulppin. Vervolgens wordt de -ste schijf naar pin C gebracht. Tot slot worden de eerste  schijven van pin B naar pin C gebracht, met pin A als hulppin.
  
  In pseudocode kan het bovenstaande procédé vertaald worden in een recursieve procedure.
  
   comment verplaats de n schijven van pin P naar pin R, met hulppin Q
   procedure Hanoi(n,P,Q,R)
   begin
     als n > 0 dan
     begin
       als n = 1 dan
         "plaats de schijf van P op R"
       anders
       begin
         Hanoi(n-1,P,R,Q) // toren van n-1 schijven naar hulppin Q
         Hanoi(1,P,Q,R) // laatste schijf van P naar R
         Hanoi(n-1,Q,P,R) // toren van de hulppin Q naar R
       end
     end
   end
  
  Hieraan is ook meteen te zien dat de oplossing voor 1 schijf minimaal 1 zet vergt, en dat een grotere toren kan worden opgelost in tweemaal het aantal zetten voor de toren met 1 schijf minder, plus 1.
  
  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 één meer dan het dubbele aantal voor de vorige stapel. Voor een toren van  schijven is het benodigde aantal zetten
  
  Handmatig oplossen
  Lost men de puzzel met de hand op, dan wordt er gemakkelijk een fout gemaakt, waardoor het oplossen langer duurt. Er is echter een eenvoudige manier om het wel goed te doen.
  
  Eerste zet
  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 de andere stok.
  
  Methode 1
  Doe om en om de volgende zetten, totdat de oplossing gevonden is:
  Verplaats een schijf (niet de kleinste) volgens de regels (er is nu slechts één mogelijkheid hiervoor).
  Verplaats de kleinste schijf naar de stok waar hij niet het meest recentelijk vandaan kwam. Anders gezegd, verplaats de kleinste schijf steeds van stok 1 naar stok 2, van 2 naar 3, van 3 naar 1 (of steeds andersom).
  
  Methode 2
  Geef de schijven om en om een andere kleur.
  Verplaats nooit twee keer dezelfde schijf.
  Leg nooit een schijf op een schijf die dezelfde kleur heeft.
  
  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 liggen 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 264 − 1, is ongeveer 1,84×1019 seconden duren de puzzel af te maken. Dit komt overeen met ruwweg 585 miljard jaar, ruwweg 43 maal zo lang als de geschatte leeftijd van het universum.
  
  Zie ook
   Hanoi
  
  Externe links
   Javasimulatie
   Hanoimania, meer dan 100 implementaties
  
  Mechanische puzzel
  Wiskundig vraagstuk
  Spel