Om Tornen i Hanoi | Regler, 2ⁿ−1 och legenden

Tre pinnar och en kon av skivor

Brädet har tre pinnar. Skivorna har alla olika storlek och träs på pinnarna. I början sitter hela satsen på en pinne, sorterad efter storlek, den största längst ned och den minsta överst, så traven bildar en kon. Målet är att flytta hela tornet till en annan pinne.

Trä-Tower of Hanoi-pussel med staplade skivor på tre pinnar — Trä-Tower of Hanoi-pussel. Foto: PranavAmbhore, CC BY-SA 3.0

De tre reglerna

1. Flytta bara en skiva i taget. 2. Ett drag tar den översta skivan från en trave och lägger den på en annan trave eller på en tom pinne. 3. En större skiva får aldrig ligga på en mindre. De tre reglerna är hela spelet. Med dem är varje tillåten ställning ett sätt att fördela skivorna på pinnarna medan varje pinne förblir sorterad.

Den kortaste lösningen är 2ⁿ − 1

Det minsta antalet drag som löser ett torn av n skivor är 2ⁿ − 1. En skiva tar 1 drag. Två skivor tar 3. Tre tar 7, fyra 15 och fem 31. Varje ny skiva fördubblar den förra lösningen och lägger till det enda drag som flyttar den största skivan: om n − 1 skivor tar T drag tar n skivor 2T + 1. Den rekursionen är exakt 2ⁿ − 1. Åtta skivor, det största tornet i PictorX-appen, tar 255 drag. Det finns ingen kortare tillåten väg.

Så fungerar rekursionen

För att flytta n skivor från startpinnen till målpinnen, med den återstående pinnen som hjälppinne: 1. Flytta de översta n − 1 skivorna från startpinnen till hjälppinnen. 2. Flytta den största skivan från startpinnen direkt till målpinnen. 3. Flytta de n − 1 skivorna från hjälppinnen till målpinnen, ovanpå den största skivan. Steg 2 är tillåtet eftersom den största skivan får ligga på vilken pinne som helst. Steg 1 och 3 är samma pussel, en skiva mindre. Anropet slutar vid en enda skiva, som flyttas en gång. Utvecklat ger det de 2ⁿ − 1 dragen, och inget steg lägger någonsin en större skiva på en mindre.

Jättelik utomhus-Tower of Hanoi vid Domaine de Chanteloup — Jättelik Tower of Hanoi vid Domaine de Chanteloup. Foto: Als33120, CC BY-SA 4.0

Legenden om de 64 gyllene skivorna

Den franske matematikern Édouard Lucas presenterade pusslet 1883. Till det berättade han en legend om ett indiskt tempel i Kashi Vishwanath, där präster flyttar en trave med 64 gyllene skivor enligt exakt samma regler. När det sista draget är gjort, säger legenden, går världen under. Sextiofyra skivor tar 2⁶⁴ − 1 drag: 18 446 744 073 709 551 615. Med ett felfritt drag i sekunden, dag och natt, blir det omkring 585 miljarder år. Prästerna kommer inte att bli klara.

Porträtt av matematikern Édouard Lucas — Édouard Lucas (1842-1891), som introducerade pusslet 1883. Public domain

Spela i PictorX

Öppna Tornen i Hanoi, så står det redan ett torn av fyra skivor på startpinnen. Femton drag är minimum. Dra den översta skivan till en annan pinne, eller klicka på en pinne och sedan på den du vill. Tangenterna 1, 2 och 3 gör samma sak. En större skiva på en mindre nekas. Skivor går från 1 till 8, så du kan jämföra 1, 3, 7, 15, 31, 63, 127 och 255 med formeln. Steg spelar upp ett drag i en kortaste lösning. Lös spelar upp resten. ”Titta på 3 skivor” visar den rekursiva strategin i rörelse. Ångra och Gör om går igenom dina drag. Spara en PNG, eller öppna brädet i PictorX-redigeraren.

Ofta ställda frågor

Vilka är reglerna för Tornen i Hanoi?

Flytta en skiva i taget. Ta den översta skivan från en pinne och lägg den på en annan pinne. Lägg aldrig en större skiva på en mindre. Hela tornet börjar på en pinne och måste sluta på en annan.

Hur många drag tar den kortaste lösningen?

2ⁿ − 1. En skiva är 1 drag, två skivor 3, tre 7, fyra 15 och fem 31. Varje tillagd skiva fördubblar den förra lösningen och lägger till ett drag.

Vem uppfann Tornen i Hanoi?

Den franske matematikern Édouard Lucas presenterade det 1883. Berättelsen om prästerna och de 64 gyllene skivorna i Kashi Vishwanath är legenden han knöt till pusslet.

Hur lång tid skulle 64 skivor ta?

2⁶⁴ − 1 drag, alltså 18 446 744 073 709 551 615. Med ett drag i sekunden blir det omkring 585 miljarder år.