] >
Er zijn drie pinnen. We geven ze aan met de cijfers ‘’, ‘’ en ‘’. Verder bestaat de puzzel uit een aantal schijven. We kunnen met een woord waarin geen andere tekens dan de cijfers ‘’, ‘’ en ‘’ voorkomen een stand van de puzzel aangeven: het eerste cijfer geeft aan op welke pin de grootste schijf is, het volgende cijfer geeft de plaats van de op een na grootste schijf aan, etc. De stand in Figuur 1.2 noteren we dus met het woord ‘’. Het is een woord van 5 cijfers, want het is een puzzel met 5 schijven. Bij een zet wordt een schijf op een andere pin geplaatst. Voor het bijbehorende woord betekent dat dat een cijfer vervangen wordt door een ander cijfer. Dat kan alleen als:
Vanuit de stand zijn er drie zetten mogelijk:
De nieuwe standen zijn voor deze gevallen respectievelijk , en .
Let op hoe we deze woorden van cijfers gebruiken:
Vergelijk dit met uitspraken als:
Het is niet van belang of het spel van hout, van porselein of van goud is. Er zijn vele uitvoeringen mogelijk. Het kan zonder pinnen, het kan met lucifers van verschillende grootte in plaats van met schijven, of met schijven waarbij de kleinste juist steeds onder moet in plaats van andersom. De beschrijving met woorden van cijfers voor de standen en de mogelijke zetten is op al deze variaties van toepassing. Daarmee kan over het spel worden gecommuniceerd ongeacht welke uitvoering men voor ogen heeft. Ook is het nu eenvoudig om standen van het spel met 64 schijven aan te geven. Als je die met plaatjes aangeeft, zoals in Figuur 1.2 voor schijven, dan is het minder overzichtelijk en ook veel bewerkelijker.
Deze beschrijving van de Toren van Hanoi maakt het ook mogelijk om er met een computer over te communiceren. Deze moet daartoe wel eerst geprogrammeerd worden. De meeste programmeertalen kennen de datastructuur string, je zou hem ook ‘woord’ kunnen noemen. Je kunt strings van de symbolen ’1’, ’2’ en ’3’ gebruiken om standen van de puzzel mee aan te geven. Verder kun je zetten programmeren. Als alle schijven op één pin staan, dan zijn er twee zetten mogelijk. In alle andere gevallen zijn het er drie. Deze kun je op verschillende manieren beschrijven. Je kunt een zet beschrijven door een uitgangspositie te geven en ook een van de drie pinnen te geven die niet bij de zet betrokken is. Zo’n zet bestaat niet voor de stand ’111…111’ en de pin ’1’, en evenzo voor twee andere gevallen waarbij alle schijven op één pin staan. In alle andere gevallen is zo eenduidig een zet vastgelegd.
In de module hanoi.py bewaren we pythonfuncties in verband met de Toren van Hanoi. Die zijn dan beschikbaar via het commando from hanoi import *. De functie replace(i,word,char) geeft de string terug die wordt verkregen door in de string word het teken op plaats i te vervangen door het teken char. In Python kun je in strings niet rechtstreeks een teken door een ander teken vervangen: een string is immutable. De nieuwe string wordt verkregen door delen van de oude samen te voegen met het teken char ertussen. Dit samenvoegen (concatenatie van strings) geschiedt met +.
De functie nextposition(peg,position) geeft de positie die wordt verkregen uitgaande van de positie position met de zet waarbij de pin peg niet betrokken is.
De functie nextposition doet wat hij moet doen: