] >
We maken uitgaande van de graaf drie nieuwe grafen. We definiëren een graaf als volgt:
De graaf beschrijft de Toren van Hanoi met schijven. De hoekpunten van zijn de standen van de Toren van Hanoi waarbij de grootste schijf op pin zit. De ribben van geven de zetten aan waarbij de grootste schijf op pin blijft. We hebben dus een Toren van Hanoi met schijven, waarbij de grootste schijf op pin zit en niet verplaatst wordt. Evenzo hebben we grafen en , waarbij de grootste schijf vast zit op pin , respectievelijk pin . In elk van deze drie gevallen hebben we te maken met een uitvoering van de Toren van Hanoi met schijven. Maak je een graaf met als hoekpunten alle hoekpunten van deze drie grafen tezamen en als ribben alle ribben van deze drie grafen tezamen, dan heb je bijna de graaf : je hebt alle hoekpunten en van de ribben ontbreken alleen de ribben die een verplaatsing van de grootste schijf beschrijven:
In Figuur 1.10 staat de graaf en in Figuur 1.11 de graaf . Uit deze figuren is het wel duidelijk hoe het werkt.
Je begint met Figuur 1.12, waarin drie keer staat afgebeeld. Daaruit maak je de grafen , en zoals afgebeeld in Figuur 1.13. Elk van deze spiegel je zo dat resp. , en op hun plaats blijven. Je krijgt dan Figuur 1.14. Vervolgens voeg je de drie nog ontbrekende ribben toe. Dat geeft Figuur 1.15, de graaf . Uitgaande van maak je op dezelfde manier : zie Figuur 1.17.
| |
| |
| |
In kun je naar de ribben kijken die horen bij verplaatsingen van de kleinste schijf. Binnen zijn er dan deelgrafen met elk hoekpunten. Zie Figuur 1.16. Ga je in de graaf van linksonder (de stand ) naar het hoekpunt bovenin (de stand ), dan kun je de zetten aflezen, waarmee je van naar komt. Afwisselend wordt de kleinste schijf verplaatst en wordt de enige andere mogelijke zet gedaan. Het verplaatsen van de kleinste schijf gebeurt steeds van pin naar pin , van pin naar pin , of van pin naar pin . Het staat daarmee vast welke van de twee mogelijke zetten met de kleinste schijf wordt gedaan. Bij schijven gaat het verplaatsen van de kleinste schijf juist in de tegengestelde richting. Dat komt doordat de graaf is opgebouwd uit grafen die door spiegelen uit zijn verkregen. Duidelijk is dat de richting van het verplaatsen van de kleinste schijf wordt bepaald door het even of oneven zijn van het aantal schijven. Deze oplossing is een van de makkelijkste om te onthouden.
Een andere formulering van de oplossing krijg je door bij zetten te kijken naar de pin die er niet bij betrokken is. Laten we de zetten een ‘label’ geven: een als het een zet tussen de pinnen en is, een bij een zet tussen de pinnen en , een bij een zet tussen de pinnen en . Het label geeft dus aan dat de schijven op de bijbehorende pin niet verplaatst worden. Bij iedere stand is er hooguit één zet met een gegeven label. Er is er steeds precies één, behalve in drie gevallen: geen zet vanuit , geen zet vanuit en geen zet vanuit .
De oplossing van de Toren van Hanoi met schijven lees je af in Figuur 1.10, het plaatje van de graaf . Om bijvoorbeeld van in te komen doe je drie zetten: eerst zet , dan en tenslotte . We geven deze opeenvolging kort aan met . Van naar ga je met .
Voor de oplossing van de Toren van Hanoi met schijven ga je eerst van naar , dan doe je zet en kom je in en vervolgens ga je naar . Dat geeft de volgende opeenvolging van zetten: . De eerste drie zetten zijn die van van naar , dan zet en ten slotte de drie zetten van van naar .
Voor krijg je zo . Voor met even kom je van in met en voor oneven gaat dat met .
Voor de puzzel met drie schijven krijg je:
2 | 3 | 1 | 2 | 3 | 1 | 2 | |
111 | 113 | 123 | 122 | 322 | 321 | 331 | 333 |
In de tweede rij staan de opeenvolgende standen van de oplossing. In de eerste rij staat welke zet gedaan moet worden. In de eerste kolom staat de beginstand en in de laatste de eindstand. Alles is bepaald door de eenvoudige opeenvolging van pinnen in de eerste rij.
Wat we hierboven met de hand deden, kun je de computer laten doen. Zijn de drie typen van zetten geprogrammeerd, dan kun je iedere nieuwe stand op het scherm tonen. De opeenvolging van zetten is bekend.
We breiden de module hanoi.py uit met solution(number). Voor de Toren van Hanoi met number schijven worden de opeenvolgende standen van de oplossing met het commando print op het scherm getoond.
Voor krijg je: