Kulla e Hanoit

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko
Një model i Kullës së Hanoit (me 8 disqe)
Zgjidhje e animuar e Kullës së 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:

  1. Vetëm një disk mund të lëvizet në një kohë.
  2. 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..
  3. 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ë 2n - 1, ku n është numri i disqeve.

Origjina[redakto | redakto tekstin burimor]

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 264−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[redakto | redakto tekstin burimor]

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ë 2n - 1, ku n është numri i disqeve.[1]

Zgjidhja përsëritëse[redakto | redakto tekstin burimor]

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[redakto | redakto tekstin burimor]

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 2n-1 lëvizje.

Paraqitja grafike[redakto | redakto tekstin burimor]

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:

Tower of Hanoi 1-disk graph.svg

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

Tower of Hanoi 2-disk graph.svg

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:

Tower of Hanoi-3.svg
  • 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:

Tower of Hanoi 3-disk graph - longest path.svg

Qarku Hamiltonian  për tri disqe është:

Tower of Hanoi-4 Longest Cycle.svg

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ë Nh 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ë:
    • N1 = 2
    • Nh+1 = (Nh)2 + (Nh)3.
    • Për shembull: N8 ≈ 1.5456×10795

Aplikimi[redakto | redakto tekstin burimor]

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[redakto | redakto tekstin burimor]

  1. ^ a b c d e f Douglas R. Hofstadter: Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books 1985, ISBN 0-465-04540-5

Lidhje të jashtme[redakto | redakto tekstin burimor]