Hanoin torni

Hanoin torni

Hanoin torni (myös Hanoin tornit) on yksinkertainen matemaattinen peli. Se koostuu kolmesta tangosta sekä levyistä, joita voi siirtää tangosta toiseen. Alkutilanteessa levyt on pinottu päällekkäin yhteen tangoista kokojärjestyksessä suurimman levyn ollessa alimmaisena. Tarkoitus on siirtää pino toiseen tankoon kolmatta apuna käyttäen samaan järjestykseen siten, että

• vain yhtä levyä saa siirtää kerrallaan
• suurempi levy ei koskaan saa olla pienemmän päällä.

Alkuperä

Pelin keksi ranskalainen matemaatikko Édouard Lucas vuonna 1883. Se perustuu vanhaan legendaan hindutemppelistä, jonka papeilla tai munkeilla on ratkaistavanaan 64 kultaisesta levystä koostuva Hanoin torni. Kun he saavat työnsä päätökseen, koittaa maailmanloppu. Ei tiedetä, keksikö Lucas tämän tarinan itse vai kehittikö hän pelin sen pohjalta.

64-levyisen Hanoin tornin ratkaiseminen vaatii vähintään 2⁶⁴ − 1 = 18 446 744 073 709 551 615 siirtoa. Luku on sama, joka saadaan myös jyvien lukumääräksi probleemassa shakkipelin keksijän palkkiosta. Jos legendan papit kykenisivät siirtämään yhden levyn joka sekunti ja jos he osaisivat ratkaista pelin vähimmäismäärällä siirtoja, maailmanloppu koittaisi 2⁶⁴ − 1 sekunnin eli noin 585 miljardin vuoden kuluttua. Maailmankaikkeuden arvioidaan nykyään olevan noin 13,7 miljardin vuoden ikäinen.

Ratkaisu

Peli on ratkaistavissa helpolla algoritmilla:

• kutsutaan tankoja nimillä A, B ja C
• olkoon n pelissä olevien levyjen lukumäärä
• numeroidaan levyt alkaen luvusta 1 (pienin, ylinnä) n:ään asti (suurin, alinna)

Jotta levyt saadaan siirrettyä tangosta A tankoon B:

1. siirretään n − 1 levyä tangosta A tankoon C. Nyt levy n on yksin tangossa A.
2. siirretään levy n A:sta B:hen
3. siirretään n − 1 levyä tangosta C tankoon B levyn n päälle.

Kyseessä on rekursiivinen algoritmi: sen suorittaminen vaatii saman algoritmin suorittamista yhtä pienemmässä tapauksessa eli n − 1 levyllä (kohdissa 1 ja 3). Jossakin vaiheessa päädytään tilanteeseen, jossa n = 1. Käytännössä sekaantumisen riski on suuri jo melko pienten tornien tapauksissa. Yleisin levyjen lukumäärä on kahdeksan.

Algoritmin perusteella on ilmeistä, että pelin ratkaisemiseksi tehtävän työn määrä likipitäen kaksinkertaistuu aina kun peliin lisätään yksi levy. Jos n levystä koostuvan tornin ratkaisemiseen tarvittava siirtojen määrä on k, tarvitaan n + 1 levylle 2k + 1 siirtoa: kahdesti k siirtoa (vaiheet 1 ja 3) plus vielä yksi siirto (vaihe 2). Tähän perustuen voidaan osoittaa, että n levystä koostuvan tornin ratkaisemiseen tarvitaan vähintään $2^{n}-1$ siirtoa.

Ratkaisu käytännössä

Ratkaisu kolmelle levylle

Ratkaisu neljälle levylle

Oikean siirtojärjestyksen voi muistaa yksinkertaisella tavalla; tämä tosin vähentää pelaamisen jännittävyyttä tuntuvasti. Olettakaamme, että levyt ovat alkutilanteessa vasemmanpuoleisessa tangossa ja tavoitteena on siirtää ne oikeanpuoleiseen. Jos pelissä on parillinen määrä levyjä, aloita siirtämällä pienin levy keskelle. Mikäli levyjen määrä on pariton, siirrä pienin levy oikeanpuolimmaiseen tankoon. Tämän jälkeen siirretään vuorotellen pienintä levyä (numeroa 1) ja jotakin muista levyistä. Pienintä levyä siirretään aina täsmälleen joka toisella siirrolla, ja se noudattaa säännöllistä liikerataa. Jos pelissä on parillinen määrä levyjä, pienin levy liikkuu koko ajan seuraavasti: vasemmalta keskelle, keskeltä oikealle, oikealta vasemmalle ja niin edelleen. Vastaavasti parittomassa tapauksessa on toimittava päinvastoin: oikealta keskelle, keskeltä vasemmalle, vasemmalta oikealle ja niin edelleen – mutta vain joka toisella siirrolla. Näiden pienimmän levyn suorittamien siirtojen välissä on aina vain yksi laillinen tapa siirtää suurempia levyjä. Toistamalla tätä strategiaa peli ratkeaa automaattisesti.

Ratkaisemiseen tarvittavien siirtojen vähimmäismäärän ongelmaa ei ole toistaiseksi osattu ratkaista pelille, jossa tankoja on neljä tai enemmän. Hanoin tornia käytetään usein psykologisena tutkimusmenetelmänä ongelmanratkaisukyvyn mittaamisessa. Ratkaisun rekursiivisen luonteen vuoksi se on myös yleinen esimerkki ohjelmoinnin opetuksessa.

Katso myös

• Rekursio

Aiheesta muualla

• Hanoin torni JavaScript-kielellä toteutettuna