Kullat e Hanoit

Një zgjidhje e animuar e enigmës Kullat e Hanoi.

Kullat e Hanoit (e quajtur edhe problemi i tempullit të Benares ose Kulla e Brahmës ose Kulla e Lucas dhe nganjëherë e pluralizuar si kulla, ose thjesht enigmë piramidale) është një lojë ose enigmë matematikore e përbërë nga tre shufra, dhe një numër disqesh me diametra të ndryshëm, të cilët mund të rrëshqasin në çdo shufër. Enigma fillon me disqet e vendosura në një shufër sipas madhësisë zvogëluese, më e vogla në krye, duke përafruar kështu një formë konike. Objektivi i enigmës është të lëvizë të gjithë pirgun në shufrën e fundit, duke iu bindur rregullave të mëposhtme:

1. Vetëm një disk mund të zhvendoset në të njëjtën kohë.

   

   Një model i Kullës së Hanoit me 8 disqe.

2. Çdo lëvizje konsiston në marrjen e diskut të sipërm nga një prej pirgjeve dhe vendosjen e tij mbi një pirg tjetër ose në një shufër të zbrazët.
3. Asnjë disk nuk mund të vendoset mbi një disk që është më i vogël se ai.

Me 3 disqe, enigma mund të zgjidhet në 7 lëvizje. Numri minimal i lëvizjeve të nevojshme për të zgjidhur një enigmë të Kullës së Hanoi është 2ⁿ − 1, ku n është numri i disqeve.

Zgjidhje

Puzzle mund të luhet me çdo numër disqesh, megjithëse shumë versione të lodrave kanë rreth 7 deri në 9 prej tyre. Numri minimal i lëvizjeve të nevojshme për të zgjidhur një enigmë të Kullës së Hanoi është 2ⁿ − 1, ku n është numri i disqeve.

Zgjidhje përsëritëse

Një zgjidhje e thjeshtë për enigmën është të alternoni lëvizjet midis pjesës më të vogël dhe asaj jo më të vogël. Kur lëvizni pjesën më të vogël, lëvizeni gjithmonë në pozicionin tjetër në të njëjtin drejtim (në të djathtë nëse numri fillestar i pjesëve është çift, në të majtë nëse numri fillestar i pjesëve është tek). Nëse nuk ka pozicion kullë në drejtimin e zgjedhur, zhvendoseni pjesën në skajin e kundërt, por më pas vazhdoni të lëvizni në drejtimin e duhur. Për shembull, nëse do të fillonit me tre pjesë, do të lëvizni pjesën më të vogël në skajin e kundërt, pastaj do të vazhdoni në drejtimin e majtë pas kësaj. Kur është radha për të lëvizur copën jo më të vogël, ka vetëm një lëvizje të drejtë. Bërja e kësaj do ta kompletojë enigmën në lëvizjet më të vogla.

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

Për një numër çift disqesh:

• bëni lëvizjen e lejuar midis kunjave A dhe B (në secilin drejtim),
• bëni lëvizjen e lejuar  midis kunjave A dhe C (në secilin drejtim),
• bëni lëvizjen e lejuar  midis kunjave B dhe C (në secilin drejtim),
• përsërisni derisa të përfundojë.

Për një numër tek disqe:

• bëni lëvizjen e lejuar midis kunjave A dhe C (në secilin drejtim),
• bëni lëvizjen e lejuar midis kunjave A dhe B (në secilin drejtim),
• bëni lëvizjen e lejuar midis kunjave B dhe C (në secilin drejtim),
• përsërisni derisa të përfundojë.

Në secilin rast, bëhen gjithsej 2ⁿ − 1 lëvizje.

Zgjidhje ekuivalente përsëritëse

Një mënyrë tjetër për të gjeneruar zgjidhje unike optimale përsëritëse:

Numëroni disqet nga 1 deri në n (më i madhi tek më i vogli).

• Nëse n është tek, lëvizja e parë është nga kunja A në kunjin C.

• Nëse n është çift, lëvizja e parë është nga kunja A në kunj B.

Tani, shtoni këto kufizime:

• Asnjë disk tek nuk mund të vendoset drejtpërdrejt në një disk tek.
• Asnjë disk çift nuk mund të vendoset drejtpërdrejt në një disk çift.
• Ndonjëherë do të ketë dy kunja të mundshme: njëri do të ketë disqe dhe tjetri do të jetë bosh. Vendoseni diskun në kunjin jo të zbrazët.
• Asnjëherë mos lëvizni një disk dy herë radhazi.

Duke marrë parasysh këto kufizime pas lëvizjes së parë, ka vetëm një lëvizje korrekte në çdo hap pasues.

Sekuenca e këtyre lëvizjeve unike është një zgjidhje optimale e problemit ekuivalente me zgjidhjen përsëritëse të përshkruar më sipër.

Zgjidhje rekursive

Ilustrim i një zgjidhjeje rekursive për enigmën Kullat e Hanoi me 4 disqe.

Çelësi për zgjidhjen e një problemi në mënyrë rekursive është të pranosh se ai mund të ndahet në një koleksion nënproblemesh më të vogla, për secilën prej të cilave zbatohet e njëjta procedurë e përgjithshme e zgjidhjes që po kërkojmë, dhe zgjidhja totale gjendet më pas në disa mënyra të thjeshta nga zgjidhjet e atyre nënproblemeve. Secili prej këtyre nënproblemeve të krijuara duke qenë "më i vogël" garanton që rasti(et) bazë do të arrihet përfundimisht. Që andej, për Kullat e Hanoit:

• etiketoni kunjat A, B, C,
• le të jetë n numri i përgjithshëm i disqeve,
• numëroni disqet nga 1 (më i vogli, më i larti) në n (më i madhi, më i ulëti).

Duke supozuar se të gjithë n disqet janë shpërndarë në renditje të vlefshme midis kunjave; duke supozuar se ka m disqe të sipërm në një kunj burimi, dhe të gjithë disqet e mbetur janë më të mëdhenj se m, kështu që ato mund të injorohen në mënyrë të sigurt; për të lëvizur m disqe nga një kunj burimi në një kunj të synuar duke përdorur një kunj rezervë, pa shkelur rregullat:

1. Zhvendosni m - 1 disqe nga burimi në kunj rezervë, me të njëjtën procedurë të përgjithshme të zgjidhjes. Rregullat nuk shkelen, me supozim. Kjo e lë diskun m si një disk të sipërm në kunjin e burimit.
2. Zhvendosni diskun m nga burimi në kunjin e synuar, i cili garantohet të jetë një lëvizje e vlefshme, sipas supozimeve - një hap i thjeshtë.
3. Lëvizni disqet m - 1 që sapo kemi vendosur në rezervë, nga kunja rezervë në kunjin e synuar me të njëjtën procedurë të përgjithshme zgjidhjeje, kështu që ato vendosen në majë të diskut m pa shkelur rregullat.
4. Rasti bazë është të lëvizni 0 disqe (në hapat 1 dhe 3), domethënë, të mos bëni asgjë - gjë që padyshim nuk shkel rregullat.

Zgjidhja e plotë e Kullës së Hanoi-t përbëhet më pas nga lëvizja e n disqeve nga kunja e burimit A në kunjin e synuar C, duke përdorur B si kunj rezervë.

Kësaj qasjeje mund t'i jepet një provë rigoroze matematikore me induksion matematikor dhe shpesh përdoret si shembull i rekursionit gjatë mësimdhënies së programimit.

Zgjidhje jo rekurzive

Lista e lëvizjeve për një kullë që bartet nga një kunj në tjetrin, siç prodhohet nga algoritmi rekurziv, ka shumë rregullsi. Kur numërojmë lëvizjet duke filluar nga 1, rendorja e diskut që do të zhvendoset gjatë lëvizjes m është numri i herëve që m mund të pjesëtohet me 2. Prandaj, çdo lëvizje tek përfshin diskun më të vogël. Mund të vërehet gjithashtu se disku më i vogël përshkon kunjat f, t, r, f, t, r etj për lartësinë teke të kullës dhe përshkon kunjat f, r, t, f, r, t etj. për lartësinë e njëtrajtshme të kullës. Kjo siguron algoritmin e mëposhtëm, i cili është më i lehtë, i realizuar me dorë, sesa algoritmi rekurziv.

Në lëvizje alternative:

• Zhvendosni diskun më të vogël në kunj nga i cili nuk ka ardhur së fundmi.
• Lëvizni një disk tjetër (do të ketë vetëm një mundësi).

Për lëvizjen e parë, disku më i vogël shkon në kunj t nëse h është tek dhe në kunj r nëse h është çift.

Gjithashtu vini re se:

• Disqet ordinalet e të cilëve kanë barazi të barabartë lëvizin në të njëjtin kuptim si disku më i vogël.
• Disqet ordinalet e të cilëve kanë barazi tek lëvizin në kuptim të kundërt.
• Nëse h është çift, kunja e tretë e mbetur gjatë lëvizjeve të njëpasnjëshme është t, r, f, t, r, f, etj.
• Nëse h është tek, kunja e tretë e mbetur gjatë lëvizjeve të njëpasnjëshme është r, t, f, r, t, f, etj.

Me këtë njohuri, një grup disqesh në mes të një zgjidhjeje optimale mund të rikuperohen pa më shumë informacion mbi gjendjen sesa pozicionet e secilit disk:

• Thirrni lëvizjet e detajuara mbi lëvizjen "natyrore" të diskut.
• Ekzaminoni diskun më të vogël të sipërm që nuk është disku 0 dhe vini re se cila do të ishte lëvizja e vetme (të lejuar) e tij: nëse nuk ka një disk të tillë, atëherë ne jemi ose në lëvizjen e parë ose të fundit.
• Nëse kjo lëvizje është lëvizja "natyrale" e diskut, atëherë disku nuk është zhvendosur që nga lëvizja e fundit e diskut 0, dhe kjo lëvizje duhet bërë.
• Nëse kjo lëvizje nuk është lëvizja "natyrale" e diskut, atëherë zhvendoseni diskun 0.

Aplikimet

Imazhi topografik 3D AFM i nanofletës së paladiumit me shumë shtresa në vaferë silikoni, me strukturë të ngjashme me kullat e Hanoit.

Kulla e Hanoit përdoret shpesh në kërkimet psikologjike për zgjidhjen e problemeve. Ekziston edhe një variant i kësaj detyre të quajtur Kulla e Londrës për diagnostikimin neuropsikologjik dhe trajtimin e funksioneve ekzekutive.

Zhang dhe Norman përdorën disa paraqitje izomorfike (ekuivalente) të lojës për të studiuar ndikimin e efektit përfaqësues në hartimin e detyrës. Ata demonstruan një ndikim në performancën e përdoruesit duke ndryshuar mënyrën se si janë përfaqësuar rregullat e lojës, duke përdorur variacione në dizajnin fizik të komponentëve të lojës. Kjo njohuri ka ndikuar në zhvillimin e kornizës TURF për përfaqësimin e ndërveprimit njeri-kompjuter.

Kullat e Hanoi përdoret gjithashtu si një skemë e rrotullimit rezervë kur kryeni kopje rezervë të të dhënave kompjuterike ku përfshihen kaseta/media të shumta.

Siç u përmend më lart, Kullat e Hanoi janë të njohura për mësimin e algoritmeve rekursive për studentët fillestarë të programimit. Një version piktural i kësaj enigme është programuar në redaktorin emacs, i aksesuar duke shtypur M-x hanoi. Ekziston gjithashtu një algoritëm mostër i shkruar në Prolog.

Kulla e Hanoi përdoret gjithashtu si një test nga neuropsikologët që përpiqen të vlerësojnë deficitet e lobit frontal.

Në vitin 2010, studiuesit publikuan rezultatet e një eksperimenti që zbuloi se një specie e milingonave ishte në gjendje të zgjidhte me sukses versionin me 3 disqe të problemit të Kullës së Hanoi përmes dinamikës jolineare dhe pheromone signals.

Në vitin 2014, shkencëtarët sintetizuan nanofletë paladium me shumë shtresa me një strukturë të ngjashme me Kullat e Hanoit.