Tower of Hanoi internetu, nemokamai

Tower of Hanoi — vienas garsiausių logikos galvosūkių istorijoje, apgaubtas įdomia legenda ir turtingu kultūros paveldu. Nepaisant paprastos konstrukcijos — trys strypai ir skirtingo skersmens diskų rinkinys — šis žaidimas išsiskiria logikos gilumu ir jį lydinčio mito patrauklumu. Sukurtas XIX amžiuje, Tower of Hanoi greitai išpopuliarėjo tarp galvosūkių mėgėjų ir matematikų visame pasaulyje.

Jo istorija verta dėmesio ne tik dėl elegantiškų taisyklių, bet ir dėl įtakos, kurią žaidimas padarė įvairių šalių kultūroms, švietimo praktikoms ir net moksliniams tyrimams. Šiame straipsnyje mes išsamiai apžvelgsime Tower of Hanoi kilmę, atseksime jo formos ir reikšmės raidą, pasidalinsime mažiau žinomais faktais, o tada pereisime prie žaidimo taisyklių ir strategijų aprašymo. Galiausiai sužinosite, kodėl šis galvosūkis užkariavo daugelio kartų protus ir kodėl jis vis dar laikomas intelektinio rafinuotumo etalonu.

Tower of Hanoi istorija

Kilmė ir autorius

Tower of Hanoi galvosūkį sukūrė Prancūzijoje 1883 m., ir jis greitai tapo žinomas dėl neįprasto paprastos formos ir elegantiškos matematinės idėjos derinio. Jo autorius buvo prancūzų matematikas Édouard Lucas — mokslininkas, išgarsėjęs tyrimais skaičių teorijos srityje bei mokslo populiarinimu per vadinamąją «rekreacinę matematiką».

Tačiau Lucas nusprendė pristatyti žaidimą visuomenei ne savo vardu, o sugalvotu personažu «profesorius N. Claus iš Siamo» — paslaptingu veikėju, kuris, neva, atvežė senovinį galvosūkį iš Tonkino (šiaurinės dabartinio Vietnamo dalies). Ši mistifikacija, papildyta užuomina apie egzotišką kilmę, suteikė galvosūkiui romantišką aureolę ir padarė jį itin patrauklų XIX amžiaus Europos auditorijai, kuri buvo susižavėjusi «rytietiškomis» legendomis ir retenybėmis.

Laikui bėgant, įžvalgūs tyrėjai pastebėjo paslėptą žodžių žaismą. Pasirodo, vardas N. Claus (de Siam) yra anagrama iš Lucas d’Amiens, o aprašymuose minėta «Li-Sou-Stian kolegija» sukeitus raides virsta tikruoju Lycée Saint Louis pavadinimu Paryžiuje, kur Lucas dirbo mokytoju. Taigi kruopščiai sukurta legenda pasirodė esanti sumanus galvosūkis, kuriame pats autorius paliko savo parašą.

Pirmasis, viešai atskleidęs šią mistifikaciją, buvo prancūzų mokslo populiarintojas Gaston Tissandier. Savo publikacijose jis parodė, kad už «kinų mandarinų» įvaizdžio slypi pats Lucas, taip atskleisdamas tikrąją žaidimo kilmę. Ši istorija dar labiau sustiprino Tower of Hanoi reputaciją ne tik kaip įdomaus galvosūkio, bet ir kaip kultūrinio fenomeno, kuriame logika glaudžiai persipina su simboliais ir aliuzijomis.

Pirmasis žaidimo leidimas

Iš pradžių galvosūkis Prancūzijoje buvo išleistas pavadinimu La Tour d’Hanoï (vertimas — «Hanojaus bokštas») ir buvo lydimas spausdintos instrukcijos, kurioje populiaria forma buvo paaiškinta jo mitinė kilmė. Komplektą sudarė medinis pagrindas su trimis vertikaliais strypais ir aštuoni skirtingo dydžio skylėti diskai. Būtent Édouard Lucas pasirinko aštuonis diskus: toks kiekis atrodė pakankamai sudėtingas, kad žaidimas išliktų įdomus, bet tuo pačiu ir išsprendžiamas.

Kiekvienas rinkinys buvo papildytas maža brošiūra, kurioje buvo pasakojama legenda apie bokštą iš auksinių diskų. Šis meninis elementas suteikė galvosūkiui ypatingą mistinę prasmę ir pavertė jį kažkuo daugiau nei tik matematine užduotimi. Dėl sėkmingo paprastos konstrukcijos ir ryškios legendos derinio, žaidimas iškart išsiskyrė tarp kitų pramogų ir sulaukė didelio visuomenės susidomėjimo.

1884–1885 m. Tower of Hanoi aprašymai ir iliustracijos pradėjo rodytis populiariuose žurnaluose. Pavyzdžiui, prancūzų leidinys La Nature paskelbė legendos apie «Brahmos bokštą» variantą, pristatydamas naują galvosūkį kaip rytietiško mito dalį. Tais pačiais metais amerikiečių žurnale Popular Science Monthly buvo išspausdinta pastaba su graviūra, kurioje pavaizduotas uždavinio sprendimo procesas. Šios publikacijos suvaidino svarbų vaidmenį platinant žaidimą už Prancūzijos ribų: apie jį sužinojo Europoje ir JAV, o tai sustiprino Tower of Hanoi statusą kaip klasikinio galvosūkio, verto tiek mokslininkų, tiek plačiosios visuomenės dėmesio.

Brahmos bokšto legenda

Pagrindinis galvosūkio sėkmės elementas buvo legenda, sukurta paties Lucaso arba, galbūt, įkvėpta senų pasakojimų. Šioje istorijoje veiksmas vyksta Indijos dievo Brahmos šventykloje (kartais pasakojimuose — vienuolyne), kur vienuoliai ar žyniai užsiima amžinu darbu: perkelia 64 diskus, užmautus ant trijų deimantinių stulpų. Pasak padavimo, šie diskai buvo pagaminti iš gryno aukso ir paties dievo pastatyti pasaulio sukūrimo akimirką. Užduotis buvo griežta ir nepalenkiama — perkelti tik po vieną diską ir niekada nedėti didesnio ant mažesnio.

Pasak mito, kai visi 64 diskai bus perkelti nuo vieno stulpo ant kito, pasaulis turės baigti savo egzistavimą. Įvairiose legendos versijose veiksmo vieta yra lokalizuojama tai Vietname, Hanojuje, tai Indijoje, Benareso šventykloje. Dėl to žaidimas vadinamas tiek «Hanojaus bokštu», tiek «Brahmos bokštu». Kartais pasakojama, kad vienuoliai atlieka tik vieną ėjimą per dieną, kitur — kad jų darbas nėra ribojamas laike.

Tačiau net jei įsivaizduotume patį greičiausią scenarijų — vienas ėjimas kas sekundę — žmonijai neva nereikėtų nerimauti: užduoties įvykdymui reikia 2^64 – 1 perkėlimo, tai yra apie 585 milijardus metų. Šis laikotarpis dešimtis kartų viršija Visatos amžių, kurį žino šiuolaikinis mokslas. Taigi legenda ne tik suteikė galvosūkiui dramatišką atspalvį, bet ir turėjo subtilaus humoro: ji pabrėžė, kad užduotis yra itin sudėtinga, bet kartu suteikė matematikams ir galvosūkių mėgėjams galimybę «apskaičiuoti pasaulio pabaigą» gražios pasakos rėmuose.

Paplitimas ir raida

Žaidimas Tower of Hanoi greitai išpopuliarėjo Europoje. XIX a. pabaigoje jis buvo žinomas ne tik Prancūzijoje, bet ir Anglijoje bei Šiaurės Amerikoje. 1889 m. Édouard Lucas išleido atskirą knygelę su galvosūkio aprašymu, o po jo mirties 1891 m. uždavinys buvo įtrauktas į pomirtinį tomą jo garsiojo veikalo «Récréations mathématiques». Dėl šio leidinio Tower of Hanoi galutinai įsitvirtino kaip rekreacinės matematikos klasikinio paveldo dalis.

Maždaug tuo pačiu metu galvosūkis pradėjo plisti įvairiais pavadinimais: «Brahmos bokštas», «Lucaso bokštas» ir kitais, priklausomai nuo šalies ir leidėjo. Įvairių šalių žaislų gamintojai išleido savo rinkinių versijas, nes Lucas neužpatentavo išradimo, todėl konstrukciją buvo galima laisvai kopijuoti. Anglijoje XX a. pradžioje, pavyzdžiui, pasirodė leidiniai pavadinimu The Brahma Puzzle. Yra žinomų išlikusių egzempliorių, išleistų Londone apie 1910–1920 m. kompanijos R. Journet, kurių dėžutėse buvo spausdintas tekstas apie žynius ir 64 auksinius diskus.

Jungtinėse Valstijose Tower of Hanoi tapo populiarių «mokslinių žaislų» asortimento dalimi ir greitai rado savo vietą šalia kitų žinomų loginių pramogų. Konstrukcijos paprastumas — trys strypai ir diskų rinkinys — leido lengvai atkurti žaidimą, o legendos variacijos padarė jį dar patrauklesnį. Pirmosiomis XX a. dešimtmečiais galvosūkis paplito tūkstančiais egzempliorių ir užėmė vietą tarp tokių klasikų kaip 15 dėlionė, o vėliau ir Rubiko kubas (nors, žinoma, Tower of Hanoi atsirado gerokai anksčiau už kubą).

Taisyklių pastovumas ir mokslinė reikšmė

Nuo Tower of Hanoi atsiradimo jo taisyklės beveik nepasikeitė. Pagrindinis principas — perkelti diskus tik po vieną ir niekada nedėti didesnio ant mažesnio — liko visiškai toks pat, kokį jį 1883 m. suformulavo Édouard Lucas. Taisyklių nekintamumas liudija pradinės konstrukcijos tobulumą.

Tačiau laikui bėgant žaidimo reikšmė pasikeitė: jis nustojo būti tik rafinuota pramoga ir tapo įrankiu įvairiose mokslo srityse. Matematikai atkreipė dėmesį į minimalaus ėjimų skaičiaus dėsningumą: seką 1, 3, 7, 15, 31 ir t. t. Pasirodė, kad ši progresija susijusi su binominėmis priklausomybėmis ir dvejetaine skaičiavimo sistema, o pati uždavinio struktūra aiškiai parodė loginių žaidimų ryšį su matematikos teoriniais pagrindais.

Informatikoje Tower of Hanoi tapo klasikiniu rekursijos pavyzdžiu — metodu, kai uždavinys padalijamas į kelis panašius mažesnio dydžio sub-uždavinius. XX a. antroje pusėje galvosūkis buvo įtrauktas į programavimo kursų programas: studentai jo pavyzdžiu mokėsi rašyti rekursinius algoritmus ir matė, kaip elegantiškas sudėtingo uždavinio suskaidymas dalimis lemia paprastą ir išraiškingą sprendimą.

Vėliau žaidimas buvo pradėtas naudoti ir psichologijoje. Taip vadinamasis «Tower of Hanoi testas» taikomas vertinant žmogaus kognityvinius gebėjimus, jo sugebėjimą planuoti veiksmus ir įsiminti žingsnių seką. Tokie uždaviniai naudojami diagnozuojant galvos smegenų traumų padarinius, tiriant su amžiumi susijusius kognityvinius sutrikimus ir nagrinėjant smegenų kaktinių skilčių veiklą.

Dėl to Tower of Hanoi gerokai peržengė XIX a. salono pramogos ribas. Šiandien jis suvokiamas kaip universalus įrankis — edukacinis, mokslinis ir diagnostinis. Paprasta forma su trimis strypais ir diskų rinkiniu tapo pagrindu ištisai tyrimų eilei, o pats žaidimas išsaugojo savo patrauklumą tiek loginių galvosūkių mėgėjams, tiek matematikos, informatikos ir psichologijos profesionalams.

Populiarumo geografija

Pavadinimas Tower of Hanoi tiesiogiai nurodo į Vietnamo sostinę Hanojų, nors pats galvosūkis neturi tikrų rytietiškų šaknų ir buvo visiškai sukurtas Prancūzijoje XIX a. pabaigoje. Vis dėlto egzotiškas legendos atspalvis pasirodė itin sėkmingas: jis suteikė žaidimui paslaptingumo ir prisidėjo prie jo plataus paplitimo. Būtent todėl įvairiose šalyse jis įsitvirtino pavadinimu, susietu su Hanojumi: anglakalbėje erdvėje — Tower of Hanoi, Prancūzijoje — Tour d’Hanoï, Vokietijoje — Türme von Hanoi ir t. t.

Sovietų Sąjungoje galvosūkis tapo žinomas ne vėliau kaip 7-ajame dešimtmetyje: jis buvo įtrauktas į pramoginių uždavinių rinkinius ir rekreacinės matematikos knygas. Kelioms mokinių kartoms Tower of Hanoi tapo pažįstama klasika, o vėliau gavo kompiuterines adaptacijas.

Įdomu, kad Vietname, nors nėra istorinių liudijimų apie panašų senovinį galvosūkį, žaidimas taip pat paplito ir yra žinomas vertime. Taigi jis sugrįžo į šalį, kurios pavadinimas buvo panaudotas legendoje, jau kaip europietiškas išradimas.

Šiandien Tower of Hanoi populiarumo geografija apima tiesiogine prasme visą pasaulį. Jį galima rasti vaikų darželiuose, kur mažieji mokosi judindami ryškius plastikinius žiedus, ir universitetų auditorijose, kur informatikos studentai programuoja uždavinio sprendimą kaip rekursinio algoritmo pavyzdį. Paprastas pagaminimas — pakanka kelių medinių lentelių ir diskų rinkinio — ir taisyklių universalumas pavertė šį galvosūkį tikru pasaulio paveldu, atpažįstamu ir vienodai įdomiu bet kurioje kultūroje.

Tower of Hanoi istorija yra turtinga detalėmis, tačiau ne mažiau įdomūs reti epizodai ir siužetai, kurie ją lydėjo ir suteikė ypatingą koloritą.

Įdomūs faktai apie Tower of Hanoi

• Diskų skaičiaus rekordas. Muziejuose ir privačiose kolekcijose galima rasti milžiniškų Tower of Hanoi variantų su trisdešimčia ar net daugiau diskų. Minimalus ėjimų skaičius tokiam uždaviniui viršija milijardą, todėl jį išspręsti rankomis praktiškai neįmanoma. Tokie rinkiniai buvo sukurti ne žaidimui, o kaip įspūdingi eksponatai, pabrėžiantys begalinį šio galvosūkio sudėtingumą ir matematinį gilumą.
• Bokštas populiariojoje kultūroje. Tower of Hanoi ne kartą pasirodė literatūroje, kine ir televizijos serialuose. Amerikiečių rašytojo Eric Frank Russell mokslinės fantastikos apsakyme «Now Inhale» (1959) pagrindinis herojus, laukdamas egzekucijos iš ateivių, pasirenka Tower of Hanoi kaip savo «paskutinį norą». Jis tai daro sąmoningai, žinodamas apie užduoties legendinį nesibaigiamumą. Kad suteiktų įvykiams varžybinį pobūdį, ateiviai paverčia galvosūkį dvikova: du žaidėjai paeiliui daro ėjimus, o nugalėtoju tampa tas, kuris atliks paskutinį. Pasirinkęs bokštą su 64 diskais, herojus faktiškai užsitikrina begalinį atidėjimą. Šiuolaikiniame kine žaidimas taip pat pasirodo. Filme «Beždžionių planetos sukilimas» (2011) Tower of Hanoi naudojamas kaip intelekto testas genetiškai modifikuotoms beždžionėms: viena iš jų sudeda bokštą iš keturių žiedų per dvidešimt ėjimų. Nors tai daugiau nei minimaliai įmanomas ėjimų skaičius (optimaliam sprendimui būtų pakakę penkiolikos perkėlimų), pati scena pabrėžia gyvūnų protinius gebėjimus ir vizualiai parodo uždavinio sudėtingumą. Klasikinis britų serialas «Doctor Who» taip pat atsigręžė į šį galvosūkį. Serijoje «The Celestial Toymaker» (1966) Daktarui buvo pavesta išspręsti Tower of Hanoi su dešimčia diskų. Sąlyga buvo itin griežta: jis turėjo atlikti lygiai 1023 ėjimus — nei daugiau, nei mažiau. Šis skaičius nebuvo pasirinktas atsitiktinai: 1023 yra minimalus įmanomas ėjimų skaičius uždaviniui su dešimčia diskų. Taigi herojui reikėjo nueiti visą kelią be nė vienos klaidos, kas dar kartą pabrėžė Tower of Hanoi reputaciją kaip beveik neįveikiamą išbandymą net genialiam keliautojui laiku.
• Buvimas vaizdo žaidimuose. Įdomu tai, kad Tower of Hanoi tapo savotišku «galvosūkių standartu» ir pateko į vaizdo žaidimų pasaulį. Kanados studija BioWare yra žinoma tuo, kad į daugelį savo projektų įtraukia mini žaidimą, paremtą Tower of Hanoi. Pavyzdžiui, vaidmenų žaidime Jade Empire yra užduotis, kur reikia perkelti žiedus tarp stulpų, o panašių galvosūkių galima rasti garsiose serijose Star Wars: Knights of the Old Republic, Mass Effect ir Dragon Age: Inquisition. Šie epizodai dažnai pateikiami kaip seni mechanizmai ar išbandymai, reikalaujantys iš herojaus sumanumo. Galvosūkis taip pat pasirodo klasikiniuose nuotykių žaidimuose, pavyzdžiui, The Legend of Kyrandia: Hand of Fate, kur vienas iš paslaptingų mechanizmų yra būtent Tower of Hanoi, užmaskuotas kaip magiškas ritualas. Tokie cameo sustiprina Tower of Hanoi įvaizdį kaip universalaus loginės užduoties simbolio.
• Edukacinis aspektas. Be legendų ir pramogų, Tower of Hanoi paliko pėdsaką ir moksle. 2013 m. mokslininkai paskelbė monografiją «The Tower of Hanoi: Myths and Maths» (Hinz ir kt.), kurioje detaliai ištirtos šio galvosūkio ir jo variantų matematinės savybės. Paaiškėjo, kad aplink jį buvo sukurta visa «Tower of Hanoi grafų» teorija, susijusi su Sierpinskio fraktalu ir kitomis matematikos sritimis. Kognityvinėje psichologijoje egzistuoja testas «Tower of Hanoi», kuriuo tikrinamos smegenų vykdomosios funkcijos — gebėjimas planuoti ir laikytis sudėtingų taisyklių. Medicinoje toks testas naudojamas įvertinti pacientų atsigavimo laipsnį po galvos smegenų traumų: gebėjimas išspręsti uždavinį yra kaktinių skilčių veiklos ir naujų neuronų jungčių formavimosi rodiklis. Taip žaidimas, kadaise pardavinėtas kaip pramoginis žaislas, tapo rimtų tyrimų objektu ir net reabilitacijos pagalbininku.

Tower of Hanoi istorija yra ryškus pavyzdys, kaip elegantiška matematinė idėja gali tapti kultūriniu fenomenu. Šis galvosūkis gimė pramogos ir mokslo sankirtoje, apaugo mitais ir simbolika, bet neprarado savo pagrindinio patrauklumo — gryno loginio grožio. Nuo Paryžiaus salonų XIX a. pabaigoje iki šiuolaikinių klasių ir skaitmeninių programėlių Tower of Hanoi išlaiko intelektinės klasikos statusą. Jis verčia susimąstyti apie rekursinio mąstymo galią, moko kantrybės ir tikslaus planavimo. Susipažinę su jo istorija, nejučia pajuntate pagarbą šiam mažam diskų bokštui — begalinės sprendimų paieškos simboliui.

Norite pasijusti kaip žynys, laikantis pasaulio likimą savo rankose, ar tiesiog patikrinti savo loginį mąstymą? Antroje dalyje mes papasakosime, kaip žaisti Tower of Hanoi, išsamiai aptarsime taisykles ir pasidalinsime patarimais, kaip išspręsti šį legendinį galvosūkį. Tegul istorijos supratimas įkvepia jus mokantis žaidimo — jūsų laukia įdomus intelektinis iššūkis.

Galvosūkis išgarsėjo visame pasaulyje ne tik dėl legendos, bet ir dėl savo įtraukiančios mechanikos. Toliau mes išsamiai aprašysime, kaip žaisti Tower of Hanoi, ir atskleisime keletą taktinių gudrybių. Išbandykite savo jėgas sprendžiant šį uždavinį — galbūt pats procesas jus sudomins ne mažiau nei jo sukūrimo istorija.

Tower of Hanoi — loginis stalo galvosūkis vienam žaidėjui (arba varžybiniu būdu dviem, jei sprendžiama pagal greitį). Klasikinis rinkinys susideda iš pagrindo su trimis vertikaliais strypais ir įvairaus skersmens diskų rinkinio (dažniausiai nuo 5 iki 8 šiuolaikinėse versijose). Pradžioje visi diskai yra sudėti ant kairiojo strypo, sudarydami piramidę, kur kiekvienas didesnis diskas yra po mažesniu.

Žaidimo tikslas — perkelti visą piramidę ant kito strypo (dažniausiai nurodoma, kad ant dešiniojo kraštinio) su mažiausiu ėjimų skaičiumi. Partija nėra ribojama laiku: jos trukmė priklauso nuo diskų skaičiaus ir žaidėjo patirties. Pavyzdžiui, užduotis su trimis diskais išsprendžiama per kelias minutes, o aštuonių diskų perkėlimas gali užtrukti iki penkiolikos minučių susitelkusio darbo. Tower of Hanoi lavina loginį mąstymą, dėmesį ir kantrybę, todėl yra vienodai mėgstamas tiek vaikų, tiek suaugusiųjų.

Iš pirmo žvilgsnio Tower of Hanoi atrodo elementari užduotis, tačiau už išorinio paprastumo slypi griežta logika. Perkeldamas piramidę pagal taisykles, žaidėjas praktiškai įsisavina rekursijos principą: didelis tikslas tampa pasiekiamas, jei jį suskaidysime į mažesnių žingsnių seką. Tokia struktūra lavina gebėjimą planuoti veiksmus ir susikoncentruoti, o partijos užbaigimas suteikia ypatingą pasitenkinimą dėl aiškiai sudėlioto sprendimo.

Tower of Hanoi taisyklės: kaip žaisti

Žaidimo tikslas

Žaidėjo užduotis — perkelti visą bokštą — diskų krūvą — nuo pradinio strypo ant kito. Tuo pačiu būtina išlaikyti pradinę tvarką: ant tikslo strypo diskai turi sudaryti taisyklingą piramidę, kur kiekvienas didesnis elementas yra po mažesniu. Kitaip tariant, rezultatas turi visiškai atkartoti pradinę konstrukciją, tik naujoje atramoje.

Įranga

Žaidime naudojamas pagrindas su trimis vertikaliais strypais, kurie sąlyginai žymimi A, B ir C. Be to, reikalingas n diskų rinkinys su skirtingais skersmenimis (n ≥ 3; klasikiniame variante — 8). Visi diskai turi skylutes ir gali laisvai judėti tarp strypų. Partijos pradžioje jie yra sudėti ant strypo A ir sudaro piramidę: didžiausias diskas yra apačioje, o virš jo paeiliui dedami vis mažesni.

Ėjimų taisyklės

• Disko perkėlimas. Kiekvienas ėjimas susideda iš to, kad nuimamas vienas viršutinis diskas nuo pasirinkto strypo ir perkeliamas ant kito. Diskas visada paimamas tik nuo krūvos viršaus, todėl apatiniai elementai lieka nejudantys, kol nebus atlaisvinti. Vienu metu perkelti kelis diskus draudžiama: žaidimas paremtas būtent nuosekliais žingsniais, kai visa konstrukcija palaipsniui surenkama iš naujo.
• Dydžio apribojimas. Ant mažesnio disko negalima dėti didesnio. Ši taisyklė užtikrina piramidės struktūros išsaugojimą: ant kiekvieno strypo diskai turi būti sudėti nuo viršaus žemyn didėjančia tvarka — nuo mažiausių iki didžiausių. Perkeliant diską, jį galima padėti ant tuščio strypo arba ant didesnio skersmens disko, taip palaikant taisyklingą tvarką. Bet koks bandymas pažeisti šią sąlygą daro ėjimą neleistiną.
• Tikslo strypas. Klasikiniame variante tikslas formuluojamas kaip visos piramidės perkėlimas nuo kairiojo strypo A ant dešiniojo strypo C, o vidurinis strypas B naudojamas kaip pagalbinis. Toks sąlyga nustato kryptį ir daro užduotį vienareikšmę. Tačiau bendrai bokštą galima perkelti ant bet kurio iš dviejų laisvų strypų: jei pradžioje nenurodyta, kuris yra tikslinis, rezultatas bus ekvivalentus — svarbu pats faktas, kad piramidė tiksliai atkartota naujoje vietoje.

Žaidimo eiga

Žaidėjas nuosekliai atlieka perkėlimus pagal taisykles. Pirmuoju ėjimu visada nuimamas mažiausias diskas — vienintelis, kuris pradžioje yra laisvas. Jį galima perkelti ant vidurinio arba dešiniojo strypo. Tolimesnė eiga priklauso nuo padaryto pasirinkimo. Žaidimas tęsiasi tol, kol visa piramidė bus sudėta ant tikslo strypo.

Pabaiga

Žaidimas laikomas išspręstu, kai visas bokštas yra perkeltas ant tikslo strypo ir atkartotas pradinėje tvarkoje: apačioje yra didžiausias diskas, o viršuje — mažiausias. Galutinė konstrukcija turi visiškai atitikti pradinę piramidę, tik naujoje vietoje.

Minimalus ėjimų skaičius

Teoriškai įrodyta, kad optimalus ėjimų skaičius Tower of Hanoi su n diskais yra lygus 2^n − 1. Mažoms reikšmėms tai lengva patikrinti: trims diskams — 7 ėjimai, keturiems — 15, penkiems — 31. Pavyzdžiui, aštuoniems diskams reikia 255 ėjimų, o dešimčiai — jau 1023. Bet koks nukrypimas nuo optimalios strategijos padidina ėjimų skaičių, todėl patyrę žaidėjai stengiasi laikytis minimalios trajektorijos.

Taisyklių variacijos

Klasikinė versija numato tris strypus ir laisvą disko perkėlimą ant bet kurio kito. Tačiau egzistuoja pripažinti papildymai ir modifikacijos.

• Su papildomais atramomis. Ketvirto ar penkto strypo pridėjimas veda prie naujų perkėlimo algoritmų paieškos. Žinoma, kad su keturiomis atramomis minimalus ėjimų skaičius yra mažesnis nei su trimis (ši versija žinoma kaip Reve’s Puzzle). Pavyzdžiui, aštuonis diskus galima perkelti per 129 ėjimus vietoje 255. Savavališkam strypų skaičiui universali formulė dar neegzistuoja: kaip orientyras naudojama Frame-Stewart hipotezė, išlikusi neįrodyta daugiau nei septyniasdešimt metų.
• Ciklinis bokštas. Šioje versijoje strypai išdėstyti ratu, o diskai gali būti perkeliami tik viena kryptimi (pavyzdžiui, pagal laikrodžio rodyklę), neperšokant per tarpinę atramą. Taigi nuo strypo A diską galima perkelti tik ant strypo B, nuo B ant C ir t. t. Šis apribojimas gerokai apsunkina strategiją ir padidina ėjimų skaičių, nors rekursinė logika išlieka sprendimo pagrindu.
• Stebuklingas trikampis. Dar viena versija, kur trys strypai išdėstyti trikampio viršūnėse. Galioja tos pačios taisyklės (vienas diskas vienu metu, negalima dėti didesnio ant mažesnio), bet įvedama papildoma sąlyga: mažiausias diskas juda tik pagal laikrodžio rodyklę, o visi kiti — prieš laikrodžio rodyklę. Ši versija iš esmės artima cikliniam bokštui ir susijusi su Grejaus dvejetainio kodo (Frank Gray) naudojimu: diskų perkėlimų seka sutampa su kodais, išdėstytais be nereikalingų žingsnių.

Nepaisant skirtumų variacijose — papildomos atramos, apskritiminis išdėstymas ar judėjimo krypties apribojimai — pagrindinė idėja išlieka ta pati: užduoties struktūra nesikeičia. Tai aiškiai parodo Lukaso sumanymo universalumą: jį galima modifikuoti ir sudėtinginti, bet pradinė logika lieka aiški ir nepakitusi.

Patarimai pradedantiesiems Tower of Hanoi

Išsiaiškinus pagrindines taisykles, natūraliai kyla noras pabandyti išspręsti Tower of Hanoi savarankiškai. Kad pirmieji žingsniai būtų prasmingi, verta remtis patikrintais metodais. Žemiau pateikiami praktiniai patarimai — nuo paprastų taktikų, leidžiančių greitai įvaldyti bazinį metodą, iki sudėtingesnių technikų, padedančių išvengti dažnų klaidų ir lavinti įgūdžius.

Taktiniai metodai

Taktinės priemonės leidžia Tower of Hanoi sprendimą paversti aiškia žingsnių sistema. Net jei užduotis atrodo sudėtinga, teisinga strategija ją paverčia paprastų veiksmų seka. Žemiau aprašyti pagrindiniai metodai, kurie padeda organizuoti žaidimą ir priartėti prie optimalaus ėjimų skaičiaus.

• Algoritmas «atlaisvink didelį diską». Pagrindinis galvosūkio elementas yra didžiausias diskas. Jo neįmanoma perkelti, kol nepašalinti visi kiti viršuje. Todėl sprendimas visada formuojamas dviem etapais: pirmiausia reikia nuimti n − 1 mažesnius diskus ir laikinai perkelti juos ant pagalbinio strypo, tada perkelti didžiausią diską ant tikslo strypo, o po to vėl sudėti ant jo piramidę iš n − 1 disko. Šis metodas yra rekursinio metodo pagrindas: norint perkelti bokštą su n diskais, pirmiausia reikia išspręsti tą pačią užduotį su n − 1 disku. Praktikoje tai reiškia, kad žaidėjo dėmesys kiekviename etape turi būti sutelktas į kelio atlaisvinimą didžiausiam elementui.
• Mažiausio disko vaidmuo. Mažiausias diskas yra judriausias ir iš esmės nustato visos partijos ritmą. Yra strategija, pagal kurią jis juda kas antrą ėjimą, kaitaliojantis su kitais diskais. Jei diskų skaičius nelyginis, pirmasis ėjimas visada yra į tikslo strypą (A → C), jei lyginis — į pagalbinį (A → B). Toliau mažasis diskas juda ratu: nelyginiam n — pagal laikrodžio rodyklę (A → C → B → A ...), lyginiam — prieš laikrodžio rodyklę (A → B → C → A ...). Ši reguliari schema automatizuoja pusę ėjimų ir daro procesą nuspėjamą.
• Vienintelis galimas ėjimas. Po kiekvieno mažojo disko perkėlimo atsiranda tik vienas kitas leidžiamas ėjimas: tarp kitų diskų tuo metu tik vieną galima perkelti nepažeidžiant taisyklių. Tai reiškia, kad strategija sumažinama iki kaitaliojimo: «mažas diskas → vienintelis leidžiamas didelis diskas → mažas → vienintelis didelis...». Šis algoritmas garantuoja užduoties sprendimą mažiausiu ėjimų skaičiumi ir apsaugo nuo klaidų net pradedančiuosius.

Pradedančiųjų klaidos

Nors taisyklės žinomos, pradedantieji dažnai daro tas pačias klaidas. Jos neužkerta kelio užduočiai išspręsti, bet gerokai padidina ėjimų skaičių ir atima sprendimui aiškumą. Susipažinus su dažniausiomis klaidomis, lengviau suprasti, ko reikėtų vengti ir kaip sukurti veiksmingesnę strategiją.

• Atsitiktiniai ėjimai be plano. Dažna klaida — diskų judinimas chaotiškai, be bendros strategijos. Atsitiktiniai perkėlimai gali veikti su 3–4 diskais, bet su 5–6 toks metodas veda prie aklavietės. Protingiau iš karto laikytis algoritmo: atlaisvinti didelį diską, jį perkelti ir atkurti piramidę. Apgalvota strategija užkerta kelią nereikalingiems perkėlimams ir taupo laiką.
• Dydžio taisyklės pažeidimas. Pradedantieji kartais bando uždėti didesnį diską ant mažesnio. Realiame rinkinyje toks ėjimas fiziškai įmanomas, bet jis pažeidžia taisykles ir daro diskų išdėstymą neteisingą. Skaitmeninėse versijose tokie veiksmai paprastai yra blokuojami programos. Visada patikrinkite, kad perkeltas diskas būtų padėtas arba ant tuščio strypo, arba ant didesnio skersmens disko.
• Bandymai visiškai išardyti bokštą. Kartais pradedantieji siekia «iškrauti» visus diskus ant laisvų atramų, manydami, kad po to bus lengviau surinkti piramidę ant tikslo strypo. Žaidimas to neleidžia: vienas iš strypų neišvengiamai lieka užimtas ir blokuoja ėjimus. Efektyvus kelias — etapinis perkėlimas: perkelti dalį diskų ant atsarginio strypo, atlaisvinti ir perkelti pagrindinį (didelį) diską, tada grąžinti nuimtą dalį.
• Skuba ir neatsargumas. Tower of Hanoi yra lėtas žaidimas. Skuboti ėjimai veda prie reikiamų žingsnių praleidimo ir ėjimų skaičiaus padidėjimo. Ypač pradžioje naudinga palaikyti tolygų tempą, stebėti visų trijų strypų būklę ir iš anksto apskaičiuoti kiekvieno ėjimo pasekmes; taip lengviau pasiekti minimalų sprendimą.

Strategijos pažengusiems

Kai baziniai metodai įsisavinti ir klasikinio bokšto sprendimas nebeteikia sunkumų, atsiranda noras išbandyti sudėtingesnius būdus. Pažangios strategijos padeda pamatyti už paprasto žaidimo slypinčią gilią matematinę struktūrą, praplečia rekursijos supratimą ir leidžia dirbti su uždaviniais, kuriuose yra daugiau diskų ar sudėtingesnės versijos. Žemiau pateikiami metodai, kurie lavina strateginį mąstymą ir paverčia žaidimą tikru intelektualiniu iššūkiu.

• Rekursyvus mąstymas. Įvaldžius klasikinį bokštą su 5–6 diskais, pabandykite sąmoningai taikyti rekursinį metodą didesniems n. Suskaidykite užduotį etapais: perkelkite viršutinius k diskus ant pagalbinio strypo, perkelkite (n − k) diską ant tikslo strypo, tada grąžinkite k diskus atgal viršuje. Optimaliame algoritme visada k = n − 1, t. y. pašalinami visi diskai, išskyrus apatinį. Tačiau treniruotės tikslais galima išbandyti ir kitus variantus, net jei jie mažiau efektyvūs. Toks pratimas padeda suprasti, kodėl minimalus ėjimų skaičius yra 2^n − 1, ir pastebėti, kad kiekvienas papildomas diskas padvigubina ėjimų skaičių ir prideda vieną.
• Dvejetainis kodas ir bokštas. Tower of Hanoi ėjimus galima pateikti kaip dvejetainių skaičių seką. Kiekvienas diskas atitinka vieną skaitmenį, o jo padėtis — to skaitmens pasikeitimą. Čia pasireiškia ryšys su Grejaus kodu: pereinant iš vienos būsenos į kitą, pasikeičia tik vienas bitas, kas atitinka vieno disko perkėlimą. Šis pastebėjimas mažai padeda rankiniame žaidime, bet leidžia pamatyti uždavinį kaip nuoseklų visų skaičių nuo 0 iki 2^n − 1 perėjimą dvejetainėje formoje. Iš smalsumo pabandykite įgyvendinti algoritmą programoje: tai sustiprins rekursijos ir strateginio mąstymo supratimą.
• Sprendimas «mintinai». Dar viena naudinga praktika — spręsti Tower of Hanoi be fizinio rinkinio, užrašant ėjimus. Pažymėkite strypus A, B ir C ir užrašykite perkėlimo seką: pavyzdžiui, jei n = 2 — A → B, A → C, B → C; jei n = 3 — A → C, A → B, C → B, A → C, B → A, B → C, A → C. Šiose sekuose aiškiai matoma rekursinė struktūra. Supratus modelį, galima spręsti uždavinį mintyse, o tai puikiai lavina abstraktų mąstymą.
• Papildomi strypai. Jei bazinis variantas nebekelia sunkumų, pabandykite žaisti su keturiomis atramomis. Čia minimali strategija nėra tokia akivaizdi. Keturiems strypams tiksli formulė nežinoma, o kelių algoritmų optimalumas dar neįrodytas. Tačiau žinoma, kad 15 diskų minimaliam sprendimui su keturiais strypais reikia 129 ėjimų — tuo tarpu su trimis jų būtų 32 767. Eksperimentuokite: ant kurių strypų perkelti tarpinės krūvas, kiek diskų panaudoti kiekviename etape. Tai lavina kūrybišką požiūrį ir leidžia giliau suprasti galvosūkio strateginius principus.

Geriausias būdas išmokti spręsti Tower of Hanoi — laikytis aiškios strategijos. Iš pradžių verta įvaldyti bazinį metodą trims strypams, tada palaipsniui didinti diskų skaičių, įvesti laiko apribojimus arba pabandyti sprendimą «mintinai». Šis galvosūkis yra patrauklus tuo, kad visada siūlo naują sudėtingumo lygį ir leidžia toliau tobulėti, nepriklausomai nuo žaidėjo patirties.

Išmokus Tower of Hanoi taisykles ir pagrindines strategijas, galima pereiti prie praktikos. Žaidimas lavina gebėjimą planuoti ir numatyti kelis ėjimus į priekį, ugdo dėmesį ir kantrybę. Nors pirmieji bandymai ne visada bus sėkmingi, nuoseklumas ir susitelkimas garantuoja sėkmę. Tower of Hanoi aiškiai parodo: net ir sudėtingiausi uždaviniai tampa išsprendžiami, jei juos suskaidome į paprastus žingsnius ir atliekame paeiliui.

Daugiau nei prieš 140 metų sukurtas galvosūkis ir šiandien įkvepia. Bandydami surinkti bokštą, tampate dalimi ilgos šio žaidimo mėgėjų tradicijos — nuo moksleivių iki matematikos profesorių. Jo universalumas ir gilumas daro Tower of Hanoi nesenstančia veikla, kuri vienija kartas. Esate pasirengę išbandyti save? Žaiskite Tower of Hanoi internetu jau dabar — nemokamai ir be registracijos!