Gratis Torens van Hanoi | De puzzel met drie pinnen

Hoe het werkt

Open deze pagina. Op de startpin liggen vier schijven. Vijftien zetten is het minimum.
Sleep de bovenste schijf naar een andere pin, of klik op een pin en dan op de pin die je wilt. Een grotere schijf op een kleinere wordt geweigerd.
Druk op Oplossen om een kortste oplossing te zien, of loop er met Stap doorheen. Sla daarna een PNG op.

Eén schijf, en nooit een grotere op een kleinere

Een zet pakt de bovenste schijf van een pin en legt die op een andere pin, of op een lege pin. Dat is de enige soort zet. De schijf die je neerlegt moet kleiner zijn dan de schijf waarop hij terechtkomt. Met die regels blijven de schijven op elke pin gesorteerd, de grootste onderaan.

2ⁿ − 1 zetten, en niet minder

Om n schijven te verplaatsen, zet je eerst de n − 1 schijven boven de grootste opzij, verplaats je de grootste schijf één keer en zet je daarna de n − 1 schijven erbovenop. Als n − 1 schijven T zetten kosten, kosten n schijven 2T + 1. Dat is 2ⁿ − 1: 1, 3, 7, 15, 31. Acht schijven, de hoogste toren hier, kosten 255 zetten.

Dezelfde puzzel, één schijf kleiner

Verplaats de bovenste n − 1 schijven naar de hulppin. Verplaats de grootste schijf naar het doel. Verplaats de n − 1 schijven van de hulppin naar het doel. Elk van die kleinere klussen is weer dezelfde puzzel. Stap en Oplossen spelen een kortste route af. Vanaf een perfecte toren is dat deze recursie. Vanaf een door elkaar gehaald bord is het nog steeds een kortste route, gevonden door de toegestane stellingen te doorzoeken.

Veelgestelde vragen

Wat zijn de regels van de Torens van Hanoi?

Verplaats één schijf tegelijk. Pak de bovenste schijf van een pin en leg die op een andere pin. Leg nooit een grotere schijf op een kleinere.

Hoeveel zetten kost de kortste oplossing?

2ⁿ − 1. Eén schijf is 1 zet, twee schijven 3, drie 7, vier 15 en vijf 31.

Wie heeft de Torens van Hanoi bedacht?

Édouard Lucas bracht de puzzel in 1883 uit. Het verhaal van priesters die 64 gouden schijven verplaatsen, is de legende die hij erbij vertelde.

Kan ik de oplossing bekijken?

Ja. Stap speelt één zet van een kortste oplossing af. Oplossen speelt de rest af. ‘Kijk naar 3 schijven’ speelt de klassieke recursieve strategie vanaf het begin af.