Tårnet i Hanoi

Modell av Tårnene i Hanoi med 8 skiver

En animert løsning på puslespillet Tårnet i Hanoi for T(4,3). Flytting av et tårn med 4 skiver krever minimum 15 flyttinger.

André Karwath (22. mars 2005)

Tårnet i Hanoi eller Tårnene i Hanoi (også kjent som Brahmas Tårn og Lucas tower) er et matematisk spill eller mekanisk puslespill. Det består av tre pinner (montert vertikalt på en rektangulær, horisontal plate) og en rekke runde skiver med et hull i midten. Skivene er av varierende bredde, og kan plasseres på en hvilken som helst av de tre pinnene. Puslespillet starter med alle skivene plassert over en pinne, ordnet etter størrelse, med den minste øverst, slik at de danner en konisk form.

Puslespillet går ut på å flytte alle skivene til en annen pinne, etter følgende regler:

• Bare én skive kan flyttes av gangen .
• Den øverste skiven flyttes fra en av pinnene til en annen pinne, på toppen av andre skiver som allerede kan være på den andre pinnen.
• Ingen skive kan plasseres over en mindre skive.

Puslespillets opprinnelse

Édouard Lucas (1842–1891)

Puslespillet sies å ha blitt oppfunnet av den franske matematikeren Édouard Lucas i 1883. Ifølge en vietnamesisk legende skal det ha eksistert et stort tempel med tre forfalne tårn som var omgitt av 64 gyldne skiver. Prestene i Hanoi sies å ha arbeidet ut fra en urgammel profeti, ved å flytte skivene i henhold til puslespillets regler. Puslespillet ble derfor også kjent som puslespillet i Brahmas Tårn. Ifølge legenden ville verdens ende inntreffe når puslespillet var løst. Det er uvisst om Édouard Lucas selv diktet opp legenden eller ble inspirert av den.

Dersom legenden var sann, og prestene flyttet en skive per sekund, ved å bruke det minste antall trekk, ville de ha brukt 2⁶⁴−1 sekunder eller omkring 600 milliarder år på å fullføre det. Det ville kreve 18,446,744,073,709,551,615 flyttinger av skivene for å løse puslespillet.

Legenden finnes i mange varianter. I noen fortellinger er tempelet et kloster og prestene er munker. Tempelet eller klosteret er blitt plassert ulike steder i verden, og i noen versjoner hevdes det at tårnet ble skapt ved verdens begynnelse, og at prestene bare foretok en forflytning per dag.

Påstanden om at puslespillet ble laget av Édouard Lucas er også omstridt. Enkelte har hevdet at det ble oppfunnet av en berømt pionér innenfor skive-baserte puslespill ved navn Harrison Heath, og at Lucas kopierte hans oppfinnelse.

Løsninger på puslespillet

Animasjon av en iterativ algoritme som løser 6-disk problemet

Den enkle løsningen

Når man flytter de minste skivene, beveger man dem alltid i samme retning (til høyre dersom antall skiver er et partall, og til venstre dersom det er et oddetall). Dersom det ikke er noen tårn i den valgte retningen, flyttes skiven til motsatt ende, for deretter å fortsette forflytningen i den korrekte retningen. Dersom man f.eks. starter med tre skiver, flyttes den minste skiven til den motsatte siden, og deretter til venstre etter dette. Når tiden kommer til å flytte skiven som ikke er minst, finnes det bare én lovlig forflytning. Dette vil løse puslespillet med færrest mulige forflytninger.

Rekursiv løsning

Puslespillet kan løses ved å dele oppgaven opp i en samling av mindre oppgaver, og deretter dele disse mindre oppgavene opp i enda mindre oppgaver, inntil problemet er løst.

• Pinnene kalles A, B, C
• Konstanten n er antall skiver
• Skivene nummereres fra 1 (den minste og øverste) til n (den største i bunnen)

For å flytte n skiver fra A til C:

1. Flytt n−1 skiver fra A til B. Dette etterlater skive #n alene på A
2. Flytt skive #n fra A til C
3. Flytt n−1 skiver fra B til C slik at de plasseres på skive #n

Dette er en rekursiv algoritme: Ved utførelsen av trinn 1 og 3, anvendes samme algoritme på nytt for n−1. Hele prosessen avsluttes etter et begrenset antall trinn, fordi algoritmen etter et gitt antall forflytninger vil nå det siste trinnet gitt ved n = 1. Dette trinnet vil flytte en enkelt skive fra A til B.

Den rekursive løsningen på Tårnet i Hanoi, er et yndet og populært eksempel på rekursjon som ofte benyttes i undervisning innenfor programmering.

Følgende algoritme i programmeringsspråket Pascal, benytter den rekursive løsningen på puslespillet:

 Procedure Hanoi(n: integer; A, C, B: char);
 Begin
    if (n=1) then
        writeln('Flytter skiven fra ', A, ' til ', C)
    else begin
        Hanoi(n-1, A, B, C);
        writeln('Flytter skiven fra ', A, ' til ', C);
        Hanoi(n-1, B, C, A);
    end;
 End;

Og et eksempel i programmeringsspråket C:

 #include <stdio.h> 
 #include <stdlib.h> 
 #include <limits.h> 
 void hanoi(int n, int fra, int til, int mellomste) 
 { 
 if (n > 0) { 
   hanoi(n-1, fra, mellomste, til); 
   printf ("flytt %d --> %d\n", fra, til); 
   hanoi(n-1, til, mellomste, fra); 
   } 
 } 
 int main (int argc, char **argv) 
 { 
 long n; 
 if (argc != 2) { 
   fprintf(stderr, "anvendelse: %s N\n", argv[0]); exit(1); 
 } 
 n = strtol(argv[1], (char **)NULL, 10); 
 hanoi(n, 1, 3, 2); 
 exit(0); 
 }

Matematisk bevis på den rekursive løsningen

Man finner en løsning lettere ved å løse en mer generell oppgave: Hvordan flytte et tårn med h (h=høyde) skiver fra en start-pinne A (f=fra) til pinnen C (t=til). B er den gjenværende tredje pinnen hvor t≠f. Oppgaven er symmetrisk for permutasjoner av pinnenes navn (symmetrisk gruppe S₃). Hvis en løsning er kjent for å forflytte tårnet fra A til C, kan samme løsning benyttes fra enhver annen start-pinne og mål-pinne. Hvis det bare er én skive (eller ingen skiver), er oppgaven triviell. Hvis n=1, flyttes disken fra A til C. Hvis h>1, må den største skiven flyttes fra A til en annen pinne, og helst til C, et eller annet sted i sekvensen av forflytninger. Den eneste situasjonen som tillater denne forflytningen er når alle mindre h-1 skiver er på pinne B. Derfor må først alle n-1 mindre skiver flyttes fra A til B. Flytt deretter den største skiven og til slutt n-1 mindre skiver fra B til C. Tilstedeværelsen av den største skiven tvinger ikke frem noen forflytning av de n-1 mindre skivene og kan midlertidig ignoreres. Oppgaven er nå blitt redusert til å forflytte n-1 skiver, først fra A til B og deretter fra B til C. Den samme strategien kan brukes for å redusere h-1 til h-2, h-3, og så videre inntil h=1. Dette kalles rekursjon. Algoritmen identifiserer skivene etter stigende størrelse ved å nummerere dem med naturlige tall fra 0 til h-1, der 0 er den minste og h-1 den største skiven.

Følgende prosedyre flytter et tårn med h skiver fra pinne f til en pinne t, med r som den gjenværende tredje pinnen:

• Trinn 1: Hvis n>1, bruk først denne prosedyren til å forflytte de n-1 mindre skivene fra A til B.
• Trinn 2: Flytt den største skiven, skive n-1 fra A til C.
• Trinn 3: Hvis h>1 benytt denne prosedyren på nytt for å forflytte de h-1 mindre skivene fra B til C.

Matematisk induksjon beviser at prosedyren krever det minste antall mulige forflytninger, og at løsningen er den eneste med dette minimumstall av forflytninger. Ved hjelp av differensekvasjoner, kalkuleres antall forflytninger av $2^{h}-1$. Trinnene 1 og 3 krever $T_{h-1}$ forflytninger, og trinn 2 krever én forflytning, som gir:

$T_{h}=2T_{h-1}+1$.

Ikke-rekursiv løsning

Den rekursive algoritmen har mange regulariteter. Ved å telle antall forflytninger som starter med 1, vil ordinal-tallet til en skive under forflytning m, være antall ganger m kan divideres med 2. Enhver oddetalls-bevegelse er derfor tilknyttet den minste skiven. Den minste skiven traverserer pinnene f, t, r, f, t, r, etc. i en oddetalls-høyde for tårnet, og traverserer pinnene f, r, t, f, r, t, etc. I en partallshøyde av tårnet. Dette gir en algoritme, som er enklere å utføre manuelt enn den rekursive algoritmen: Flytt den minste skiven til den pinne som den ikke nettopp kommer fra. Flytt en annen skive på en lovlig måte (der vil bare være en mulighet) I den aller første forflytningen, går den minste skiven til pinne t, hvis h er et oddetall, og til pinne r hvis h er et partall.

Legg merke til at:

• Skiver med partalls-paritet som ordinaltall flytter seg i samme retning som den minste skiven.
• Skiver med oddetalls-paritet som ordinaltall flytter seg i motsatt retning.

Dersom h er et partall, er den gjenværende tredje pinne under suksessive forflytninger t, r, f, t, r, f, etc. Dersom h er et oddetall, er den gjenværende tredje pinne under suksessive forflytninger r, t, f, r, t, f, etc.

Dermed kan man foreta en middels optimal løsning uten noe mer informasjon enn posisjonene til hver skive:

• Undersøk den minste øverste skiven som ikke er skive 0, og finn dens eneste lovlige bevegelse (det finnes ingen slik skive ved første eller siste forflytning).
• Hvis denne forflytningen er skivens «naturlige» bevegelsesretning, har skiven ikke blitt forflyttet siden den siste forflytningen av skive 0, og bør forflyttes.
• Hvis dette ikke er skivens «naturlige» bevegelsesretning, flytt i stedet skive 0.

Binære løsninger

Skivenes posisjoner kan bestemmes av den binære (base 2) representasjonen av bevegelses-nummeret move (første tilstand er move #0, med alle sifre lik 0, og siste tilstand er #2ⁿ−1, med alle sifre lik 1), ved å bruke følgende regler:

• Hver skive har et bit
• Det mest signifikante bit representerer den største skiven. Verdien 0 indikerer at den største skiven er på start-pinnen, mens 1 indikerer at den er på den siste pinnen.
• Bitstrengen leses fra venstre til høyre, og hvert bit kan brukes til å avgjøre posisjonen til den korresponderende skiven.
• Et bit med samme verdi som det forutgående betyr at den korresponderende skiven ligger på toppen av den forrige skiven på samme pinne.
  • (En sekvens med bare 1'ere eller 0'ere betyr at alle korresponderende skiver er på samme pinne).
• Et bit med en annen verdi enn den forrige betyr at den korresponderende skiven er i en posisjon til venstre eller høyre av den forrige. Hvorvidt det er venstre eller høyre avgjøres av følgende regel:
  • Forutsett at start-pinnen er til venstre og mål-pinnen er til høyre.
  • Forutsett også en wrapping, slik at høyre pinne regnes som værende til «venstre» for venstre pinne, og omvendt.
  • La n være antall større skiver på samme pinne som deres første større skive, og adder 1 hvis den største skiven er på den venstre pinnen. Hvis n er et partall, befinner skiven seg en pinne til venstre. Hvis n er et oddetall, befinner skiven seg en pinne til høyre.

Eksempel med et 8-skivers Hanoi-tårn:

• Move #0)
  • Den største skiven er 0. Derfor befinner den seg på den venstre start-pinnen.
  • Alle andre skiver er også 0. Derfor ligger de i en stakk over den. Alle skivene er derfor på start-pinnen.
• Move #2^8-1)
  • Den største skiven er 1, og er derfor på den høyre mål-pinnen.
  • Alle andre skiver er også 1. Derfor ligger de i en stakk over den. Alle skivene er derfor på mål-pinnen og puslespillet er fullført.
• Move #0b11011000)
  • Den største skiven er 1, og er derfor på den høyre mål-pinnen.
  • Skive 2 er også 1, og ligger derfor over den største skiven på den høyre pinnen.
  • Skive 3 er 0, og er derfor på en annen pinne. Fordi n er et oddetall, er den en pinne til høyre, dvs. på venstre pinne.
  • Skive 4 er 1, og er derfor på en annen pinne. Fordi n fortsatt er et partall, er den en pinne til venstre, dvs. på høyre pinne.
  • Skive 5 er også 1, og ligger derfor på toppen av den, på høyre pinne.
  • Skive 6 er 0, og er derfor på en annen pinne. Fordi n fortsatt er et partall, er skiven en pinne til venstre, dvs. på den midterste pinnen.
  • Skivene 7 og 8 er også 0, og ligger derfor på toppen av den, på den midterste pinnen.

Algoritmen ovenfor kan skrives slik i programmeringsspråket Scheme:

 (define (conf m h f t) ; m=move number, h=høyde på tårnet, 
  f=start-pinne, t=mål-pinne
  ; Identifiser pinnene med tallene 0, 1 og 2.
  (let loop ((prev-zero? #t) (mask (arithmetic-shift 1 (sub1 h)))
  (rotation (- t f)) (f f))
   (if (zero? mask) ()
    (let ((zero-bit? (zero? (bitwise-and mask m))) 
    (mask (arithmetic-shift mask -1)))
     (if (eq? prev-zero? zero-bit?) 
       (cons f (loop zero-bit? mask (- rotation) f))
          (let ((f (modulo (+ f rotation) 3)))
           (cons f (loop zero-bit? mask rotation f))))))))

Prosedyren produserer en liste over posisjonene til skivene ordnet etter en stadig mindre størrelse. Eksempel:

> (conf #e6022e20 80 0 2)
(01111111100001201201221111201112012000)

Kilde- og målpinnene for forflytning nr m kan også bli funnet gjennom en binær representasjon av m ved å bruke bitvise operasjoner. I syntaksen til programmeringspråket C er forflytning nr m fra pinne (m&m-1)%3 til pinne ((m|m-1)+1)%3, der hvor skivene starter på pinne 0 og avsluttes på pinne 1 eller 2, avhengig av om antall skiver er et partall eller oddetall. Skiven som flyttes identifiseres av antall ganger telleren m kan divideres med 2 (antall 0-bits til høyre), ved å telle første flytting som 1 og å nummerere skivene med tallene 0, 1, 2 etc etter stigende størrelse. Dette er en svært rask ikke-rekursiv algoritme for å finne skivenes posisjoner etter m forflytninger uten referanse til tidligere forflytninger eller skivenes fordeling:

 ; h : det totale antall skiver
 ; m : flytter telleren, som begynner med 1 for første forflytning
 ; f : start-pinne; pinnene er nummererte 0, 1 og 2.
 ; t : mål-pinne
 ; d : skive (nummererte 0, 1, 2, etc ordnet etter økende størrelse)
 ; Funksjonen =quotient= tar to heltall og beregner deres kvosient avrundet til heltallet som er nærmest null.
 ; (rot3 m) : rotasjon av den gjenværende tredje pinne under flytting m.
 ; (rotd d) : rotasjon av skive d.
 ; mcnt : antallet flyttinger av skive d etter totalt m flyttinger.
 ; from : pinnen en skive hentes fra under flytting m.
 ; onto : pinnen en skive legges på under flytting m.
 ; thrd : den tredje pinnen. (- 3 fra onto)
 ; disk : skiven som flyttes.
 ; conf : posisjonen til skive d etter totalt m flyttinger.
 
 (define (exp2 n        ) (expt   2 n))
 (define (mod2 n        ) (modulo n 2))
 (define (mod3 n        ) (modulo n 3))
 (define (pari n        ) (add1 (mod2 (add1 n))))
 (define (rotd   h d f t) (mod3 (* (- t f) (pari (- h d)))))
 (define (rot3   h   f t) (rotd h 0 f t))
 (define (mcnt m   d    ) (quotient (+ m (exp2 d)) (exp2 (add1 d))))
 (define (thrd m h   f t) (mod3 (- f (* m (rot3 h f t)))))
 (define (onto m h   f t) (mod3 (- (thrd m h f t) (rotd h (disk m) f t))))
 (define (from m h   f t) (mod3 (+ (thrd m h f t) (rotd h (disk m) f t))))
 (define (conf m h d f t) (mod3 (+ f (* (rotd h d f t) (mcnt m d)))))
 (define (disk m        ) (sub1 (bit-count (bitwise-xor m (sub1 m)))))

Løsning med Gray-kode

Det binære tallsystemet med Gray koder tilbyr en alternativ måte å løse puslespillet på. Gray-systemet representerer tall som en binær kombinasjon av 0'ere og 1'ere, men i stedet for å være et standardisert tallsystem, varierer hvert tall fra sin forgjenger med ét (og bare ét) enkelt bit.

Dersom en teller tilsvarer antall skiver i et Hanoi-tårm, vil et bit begynne på 0 og endres for hver forflytning av en skive, hvor det minst signifikante bit er den minste disken og det mest signifikante bit er den største. Når man teller antall forflytninger fra 1 og identifiserer skivene som forflyttes, ved å starte med 0 og sortere dem etter økende størrelse, er ordinaltallet for skivene som skal forflyttes under forflytning m identisk med antall ganger m kan divideres med 2.

Algoritmen identifiserer hvilken skiven som skal flyttes, men ikke hvor den skal flyttes. For den minste skiven er det alltid to muligheter. For andre skiver er det alltid én mulighet, bortsett fra når alle skivene er på samme pinne. Dersomd det siste er tilfelle skal alltid den minste skiven flyttes, eller puslespillet er løst.

Det finnes en regel som forteller hvor den minste skiven skal flyttes. La f være start-pinnen, t mål-pinnen og r den tredje pinnen. Dersom antall skiver er et oddetall er den minste skivens forflytning langs pinnene lik f→t→r→f→t→r. Dersom antall skiver er et partall, blir sekvensen lik f→r→t→f→r→t.

Lange løsninger

En modifikasjon av spillet er å flytte tårnet fra en pinne til en annen, ved å benytte så mange forflytninger som mulige uten å gjenta den samme fordelingen av skivene. En enkel algoritme i Scheme er slik:

 (define (long-move-tower h f t r)
  (if (positive? h)
   (let ((h (sub1 h)))
    (long-move-tower h f t r)
    (move-disk       h f r t)
    (long-move-tower h t f r)
    (move-disk       h r t f)
    (long-move-tower h f t r))))

Prosedyren (move-disk d f t r) flytter skive d fra pinne f til pinne t, ved å ignorere pinne r. Antall forflytninger av denne løsningen er 3^høyde-1. Alle forskjellige fordelinger av 3^høyde antall fordelinger av skivene traverseres, inkludert den innledende og endelige fordelingen.

Dette kalles en Hamiltonvei. Skiven som skal flyttes identifiseres med en ternær inkrementell Gray-kode på lignende måte som det som er forklart for den korteste løsningen. En ternær Gray-kode som innledes med alle sifre lik 0, og ender med alle sifre lik 2, lister opp alle suksessive fordelinger av skivene langs en Hamilton-vei fra pinne 0 til pinne 2 for et tårn med h skiver. Hver kode viser skivenes posisjon ordnet etter stadig mindre størrelse, når koden leses fra venstre mot høyre. Hvert siffer skifter innhold oftere enn de mer signifikante sifrene til venstre.

Dette er koden for Hanoi-tårnet:

 (define (number->p-ary-gray-code n h p) ; n h p --> n-th h digit p-ary gray-code
  (let ((2p (* 2 p)))
   (let loop ((n n) (h h) (gc ()))
    (if (zero? h) gc
     (let ((q (quotient n p)) (r (modulo n 2p)))
      (loop q (sub1 h) (cons (if (>= r p) (- 2p r 1) r) gc)))))))
 
 (define (p-ary-gray-code->number gc p) ; n-th p-ary gray-code --> n
  (let loop ((gc gc) (significance (expt p (sub1 (length gc)))))
   (if (null? gc) 0
    (let ((digit (car gc)) (gc (cdr gc)))
     (let ((n (loop gc (quotient significance p))))
      (+ (* digit significance)
       (if (odd? digit) (- significance n 1) n)))))))
 
 (define (number->hanoian-gray-code n h) (number->p-ary-gray-code n h 3))
 (define (hanoian-gray-code->number gc) (p-ary-gray-code->number gc 3))

Litteratur

• Ivan Moscovich: 1000 Play Thinks: Puzzles, Paradoxes, Illusions & Games, Workman Publishing Company, 1. oktober 2001, ISBN 0761118268, ISBN 978-0761118268