Kulla e Hanoit

Pamje interaktive e Kullës së Hanoit në Universitetin muze të Meksikës

Kulla e Hanoit (e quajtur edhe si Kulla e Brahmas ose Kulla e Lucas',^[1] dhe nganjëherë e përdorur në shumës) është një lojë matematikore ose një engimë. Ajo përbëhet nga tri shufra, dhe një numër disqesh të madhësive të ndryshme të cilat mund të zhvendosen nga një shufër në tjetrën. Fillimisht ato janë të vendosura në shtyllën e parë, të renditura nga më e madhja deri te më e vogla në krye, duke marrë një formë konike.

Objektivi i lojës është të lëvizet i tërë pirgu në një shtyllë tjetër, duke përcjell disa rregulla të thjeshta:

Vetëm një disk mund të lëvizet në një kohë.
Secila lëvizje duhet të marrë një disk që ndodhet në maje dhe ta vendos mbi një pirg tjetër p.sh. një disk mund të lëvizet nëse është më i larti disk në pirg..
Asnjë disk nuk mund të vendoset mbi një disk më të vogël.

Me tri disqe, engima mund të zgjidhet në shtatë lëvizje. Numri minimal i lëvizjeve që duhen për të zgjidhur një Kullë të Hanoit është 2ⁿ - 1, ku n është numri i disqeve.

Origjina

Kjo lojë u zbulua nga matematikani francez Édouard Lucas në vitin 1883. Ekziston një rrëfim mbi një tempull indian në Kashi Vishwanath i cili përmban një dhomë të madhe me tri mesazhe të fshehura kohore në të, të rrethuara nga 64 disqe të arta. Priftërinjtë e Brahminit, duke vepruar sipas urdhërave të profecisë antike, i kanë lëvizur këto disqe, në koordinim me rregullat e pandryshueshme të Brahmas, që nga ajo kohë. Engima është e njohur edhe me emrin Kulla e Brahmas. Sipas legjendë, kur të kryhet lëvizja e fundit, bota do të marrë fund.^[1] Nuk është e qartë nëse Lucasi e shpiku këtë legjendë apo u inspirua nga ajo.

Nëse legjenda do të ishte e vërtetë, dhe nëse priftërinjtë janë të gjendje të lëvizin disqet në shkallë prej 1 për sekond, duke përdorur numrin më të vogël të lëvizjeve, do të duheshin 2⁶⁴−1 sekonda ose 585 miliardë vite^[1] ose 18,446,744,073,709,551,615 lëvizje për tu përfunduar, që janë rreth 27 herë mosha aktuale e diellit.

Ekzistojnë disa variante të kësaj legjende. Për shembull, në disa tregime, tempulli është një manastir dhe lëvizet nga murgjit. Tempulli ose manastiri mund të jetë në vende të ndryshme të botës - duke përfshirë Hanoin, Vietnamin, dhe mund të lidhet me cilindo religjion. Në disa versione, përfshihen elemente të tjera, si fakti se kulla është krijuar në fillim të botës, ose se priftërinjtë ose murgjit mund të bëjnë vetëm një lëvizje në ditë.

Zgjidhja

Engima mund të luhet me çfarëdo numri të disqeve, megjithëse shumica e versioneve janë me shtatë ose nëntë. Numri minimal i lëvizjeve për zgjidhjen e engimës është 2ⁿ - 1, ku n është numri i disqeve.^[1]

Zgjidhja përsëritëse

Një zgjidhje e thjeshtë për engimën në version të thjeshtë: bëj lëvizje në mes të diskut më të vogël dhe atij jo më të vogël. Kur lëvizet disku më i vogël, zhvendose në pozicionin e ardhshëm në drejtim të njëjtë (djathtas nëse numri fillestar i disqeve është tek, majtas nëse është çift). Nëse nuk ka pozicion kulle në drejtimin e zgjedhur, lëvize diskun në fundin e kundërt, por pastaj vazhdo të lëvizësh në drejtimin korrekt. Për shembull, ju keni filluar me tri disqe, ju keni lëvizur diskun më të vogël në fund, dhe pastaj keni vazhduar në drejtimin majtas. Kur vie radha për lëvizje të diskut jo më të vogël, ekziston vetëm një lëvizje e lejuar. Kjo do të përfundojë lojën në numër të vogël lëvizjesh.^[1]

Paraqitje më e thjeshtë e zgjidhjes përsëritëse

Përcjell hapat në raste të caktuar, për lëvizja në mes të diskut më të vogël dhe atij njëherë më të madh se ai, si më poshtë:

Për numër tek të disqeve:

bëje lëvizjen e lejuar në mes të kujave A dhe B
bëje lëvizjen e lejuar në mes të kujave A dhe C
bëje lëvizjen e lejuar në mes të kunjave B dhe C
përsëriti hapat e parë derisa të përfundohet

Për numër çift të disqeve:

bëje lëvizjen e lejuar në mes të kujave A dhe C
bëje lëvizjen e lejuar në mes të kujave A dhe B
bëje lëvizjen e lejuar në mes të kujave C dhe D
përsëriti hapat e parë derisa të përfundohet

Në secilin rast janë kryer 2ⁿ-1 lëvizje.

Paraqitja grafike

Loja mund të paraqitet nga një graf i padrejtuar, ku nyjat paraqesin grupimet e disqeve dhe brinjët paraqesin lëvizjet. Për një disk, grafiku është trekëndësh:

Grafiku për dy disqe përbëhet nga tre trekëndësha të vendosur në një trekëndësh më të madh:

Nyjet në kulmet më të skajshme të trekëndëshit paraqesin grupimet e të gjithë disqeve në të njëjtën kunj.

Për h+1 disqe, merret grafiku i h disqeve dhe zëvendësohet secili trekëndësh i vogël me graf për dy disqe.

Për tri disqe grafiku është ky:

quajmë kunjat a, b dhe c
renditim pozitat e disqeve nga majtas djathtas në renditje ashtu që madhësia e tyre rritet

Faqet e trekëndëshit më të skajshëm paraqesin rrugët më të shkurtra të lëvizjes së një kulle nga një kunj në tjetrën. Brinja në mes të fuqes së trekëndëshit më të madh paraqet një lëvizje të diskut më të madh. Brinja në mes të faqeve të secilit trekëndësh të ardhshëm paraqet një lëvizje të secilit disk më të vogël. Faqet e trekëndështave të vegjël paraqesin lëvizjet e disqeve më të vogla.

Grafiku i lojës në nivel të shtatë tregon lidhshmërinë me trekëndëshin Sierpiński.

Rruga më e gjatë jo-përsëritëse për tri disqe mund të vizualizohet duke larguar brinjët e papërdorura:

Qarku Hamiltonian për tri disqe është:

Grafiku qartazi tregon se:

Për secilin grupim arbitrar të disqeve, ekziston saktësisht një rrugë e shkurtër për të lëvizur gjithë disqet në njërën nga tri shtyllat.
Në mes të secilës palë të grupimeve arbitrare të disqeve ekzistojnë një ose dy rrugë të shkurtra.
Nga secili grupim arbitrar i disqeve, ekzisojnë një ose dy rrugë të ndryshme të gjata që nuk kalojnë nëpër vetvete për të lëvizur të gjitha disqet në tri kunja.
Në mes të secilës palë të grupimeve arbitrare të disqeve ekzistojnë një ose dy rrugë të ndryshme të gjata që nuk kalojnë nëpër vetvete.
Le të jetë N_h numr i rrugëve që nuk kalojnë nëpër vetveve për lëvizjen e kullës prej h-disqesh nga një kunj në tjetrën. Atëherë:
- N₁ = 2
- N_h+1 = (N_h)² + (N_h)³.
- Për shembull: N₈ ≈ 1.5456×10⁷⁹⁵

Aplikimi

Kulla e Hanoit përdoret shpesh në kërkime psikologjike në zgjidhjen e problemeve. Ekziston një variant i kësaj detyre e quajtur Kulla e Londrës për diagnoza neuropsikologjike dhe tretmane të funksioneve ekzekutive.

Kulla e Hanoit është e famshme për mësimin e algoritmave rekursive për studentët që fillojnë të mësojnë programimin.

Kulla e Hanoit u përdor po ashtu si test nga neuropsikologët në përpjekje për të vlerësuar deficitet e një pjeseje të trurit.

Në vitin 2010, hulumtuesit publikuan rezultatet e një eksperimenti ku gjetën se specia e milingonave Linepithema humile mund ta zgjidhte në mënyrë të suksesshme versionin 3-disqsh të Kullës së Hanoit.^[1]

Shënime

^ ^a ^b ^c ^d ^e ^f Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 0-465-04540-5. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

Lidhje të jashtme

Weisstein, Eric W., "Tower of Hanoi", MathWorld.
Tower of Hanoi at DMOZ
Tower of Hanoi: Code in Lisp
Tower of Hanoi Variant Game: Pyramid Mover
Tower of Hanoi: online game Arkivuar 3 shtator 2022 tek Wayback Machine

[Hofstadter_1985-1] ^ ^a ^b ^c ^d ^e ^f Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 0-465-04540-5. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]