300px|thumb|Modell av Tårnene i Hanoi med 8 skiver 300px|thumb|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. 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 thumb|É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 264−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 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 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); exit(1);
n = strtol(argv, (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 S3). 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 . Trinnene 1 og 3 krever forflytninger, og trinn 2 krever én forflytning, som gir: .
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 #2n−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)))