Redigerer Tårnet i Hanoi (avsnitt)

==Løsninger på puslespillet==
[[Fil:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|thumb|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:

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

Dette er en [[rekursjon|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 (programmeringsspråk)|Pascal]], benytter den rekursive løsningen på puslespillet:

<syntaxhighlight lang="pascal">
 Procedure Hanoi(n: integer; A, C, B: char);
 Begin
    if (n=1) then
        writeln('Flytter disken fra ', A, ' til ', C)
    else begin
        Hanoi(n-1, A, B, C);
        writeln('Flytter disken fra ', A, ' til ', C);
        Hanoi(n-1, B, C, A);
    end;
 End;
</syntaxhighlight>
Og et eksempel i [[C (programmeringsspråk)|programmeringsspråket C]]:
<syntaxhighlight lang="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); 
 }
</syntaxhighlight>

===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 [[permutasjon]]er av pinnenes navn ([[symmetrisk gruppe|symmetrisk gruppe S<sub>3</sub>]]). 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 [[naturlig tall|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 [[differensekvasjon]]er, kalkuleres antall forflytninger av <big><math>2^h - 1</math></big>. Trinnene 1 og 3 krever <big><math>T_{h-1}</math></big> forflytninger, og trinn 2 krever én forflytning, som gir:
:<big><math>T_h = 2T_{h-1} + 1</math></big>.

===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ært tallsystem|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<sup>''n''</sup>−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]]:

<syntaxhighlight lang="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))))))))
</syntaxhighlight>

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

<syntaxhighlight lang="scheme">
> (conf #e6022e20 80 0 2)
(01111111100001201201221111201112012000)
</syntaxhighlight>

Kilde- og målpinnene for forflytning nr ''m'' kan også bli funnet gjennom en binær representasjon av ''m'' ved å bruke [[bitvis operasjon|bitvise operasjoner]]. I syntaksen til [[C (programmeringsspråk)|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:

<syntaxhighlight lang="scheme">
 ; 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)))))
</syntaxhighlight>

===Løsning med Gray-kode===
Det [[binært tallsystem|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:

 <syntaxhighlight lang="scheme">
 (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))))
 </syntaxhighlight>

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<sup>høyde</sup>-1. Alle forskjellige fordelinger av 3<sup>høyde</sup> antall fordelinger av skivene traverseres, inkludert den innledende og endelige fordelingen.

Dette kalles en [[Hamilton vei|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:

 <syntaxhighlight lang="scheme">
 (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))
 </syntaxhighlight>