Tårnet i Hanoi

Puslespillets opprinnelse

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 idé om å lage et puslespill.

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.

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 3høyde-1. Alle forskjellige fordelinger av 3hø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))