Tornen i Hanoi
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-02) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Tornen i Hanoi (Tornet i Hanoi) är ett matematiskt problem som också finns i skepnad av spel eller patiens.
Problemet/spelet består av tre vertikala pinnar fästa på en platta. På den vänstra pinnen sitter n stycken platta cirkulära skivor med hål i. Dessa skivor är olika stora och sorterade i storleksordning med den största underst. Spelet går ut på att flytta över hela stapeln till högra pinnen likadant sorterad. Mellanpinnen är bara hjälppinne. Varje drag utgörs av att flytta en skiva till en annan pinne med restriktionen att man får inte lägga en större skiva på en mindre. På en tom pinne får man lägga vilken skiva som helst. Problemet är lösbart oavsett värdet på n (ett naturligt tal).
Den optimala lösningen (dvs minsta möjliga antalet drag) med n stycken skivor är 2n - 1 drag. Denna formel kan härledas med hjälp av en rekursiv differensekvation.
För ett godtyckligt antal (>3) pinnar, var det länge ett olöst problem, men löstes för 4 pinnar 2014 och för ett godtyckligt antal pinnar 2018. Det optimala antalet drag följer av Frame-Stewarts förmodan, en lösningsalgoritm som uppfanns av Frame och Stewart, oberoende av varandra 1941.
Det finns också en patiens inspirerad av detta problem (se även kortspel).