Hanojska kula

Hanojska kula (takođe se naziva Brahma kula ili Lukasova kula, a ponekad i pluralizovano) je matematička igra ili slagalica. Sastoji se od tri šipke i velikog broja diskova različitih veličina koji mogu da klize na bilo koju šipku. Zagonetka počinje uređivanjem diskova u rastućem redosledu na jednoj palici, gde je najmanji na vrhu pa daje izgled konusnog oblika

Model hanojske kule (sa 8 diskova)

Animirano rešenje hanojske kule za T(4,3).

Hanojska kula se iteraktivno prikazuje u Universum muzeju u Meksiku

Cilj ove slagalice je da se sve sa jednog štapa premesti na drugi štap, poštujući sledeća pravila:

1. Samo jedan disk može da se pomera istovremeno.
2. Svaki potez se sastoji od uzimanja gornjeg diska sa jedne gomile i stavljanja tog istog diska na vrh druge gomile, odnosno disk može samo da se pomera ako je na poslednjem mestu na štapu.
3. Nijedan disk ne sme biti smešten na manji disk na štapu.

Sa tri diska ovaj problem može da se reši u sedam koraka. Najmanji broj koraka potrebnih da se reši ovaj problem je 2ⁿ-1, gde je n broj diskova.

Poreklo

Zagonetku je izmislio francuski matematičar Eduar Lukas 1883. Postoji priča o indijskom hramu u Kaši Višvanatu, koji sadrži veliku sobu sa tri poruke koje su istrošene kroz vreme i koje su okružene sa 64 zlatna diska. Sveštenici bramani, radeći u skladu sa starim proročanstvom, pomeraju ove diskove po nepromenljivim pravilima Brahme od tad. Zagonetka je dakle takođe i poznata kao Brahmina kula. Prema legendi, svet će se srušiti kada bude bio završen poslednji potez slagalice. Nije utvrđeno da li je Lukas smislio ovu legendu ili je bio nadahnut njome.

Ako je legenda istinita i ako su sveštenici bili u stanju da pomeraju diskove po stopi u sekundi, koristeći najmanji broj poteza, trebalo bi im oko 2⁶⁴-1 po sekundi ili oko 585 milijardi godina ili 18 446 744 073 709 551 615 okreta da završe ili oko 127 puta trenutne starosti Sunca.

Postoje mnoge varijacije na ovu legendu. Na primer, u nekim kazivanjima hram je manastir, a sveštenici su monasi. Hram ili manastir može se reći da u različitim delovima sveta – uključujući Hanoj u Vijetnamu može biti povezan sa bilo kojom religijom. U nekim verzijama drugi elementi se uvode, kao što je činjenica da je toranj nastao na početku sveta, ili da sveštenici ili monasi čine samo jedan potez dnevno.

Rešenje

Zagonetka se može igrati sa bilo kojim brojem diskova, iako mnoge verzije ove igre koriste od sedam do devet diskova. Minimalan broj poteza potrebnih da se reši ovaj problem je 2ⁿ – 1, gde je n broj diskova.

Iterativno rešenje

Iterativni algoritam rešavanja problema Hanojske kule sa 6 diskova

Jednostavno rešenje za ovakvu slagalicu:

Alternativni pokreti se kreću između najmanjeg dela i ne-najmanjeg dela. Kada pomerate najmanji komad, uvek ga pomerate na sledeću poziciju u istom smeru (sa desne strane ako je početni broj paran ili nalevo ako je polazni broj komada neparan). Ako kula nema položaj u odabranom smeru, pomerite komad na suprotan kraj, ali onda nastavite da pomerate u ispravnom smeru. Na primer, ako ste počeli sa tri komada, trebalo bi da pomerite najmanji komad do suprotnog kraja, a zatim da nastavite u levom pravcu posle toga. Kada je red na pomeranje ne- najmanjeg komada, postoji samo jedan pravilan potez. Uz pomoć ovoga, slagalica će se završiti sa najmanjim brojem poteza.

Jednostavnija izjava iterativnog rešenja

Naizmenično između najmanjeg i narednog najmanjeg, slediti korake za pogodan položaj.

Za paran broj diskova:

• Napravi ispravan potez između rupa A i B
• Napravi ispravan potez između rupa A i C
• Napravi ispravan potez između rupa B i C

Ponavljaj dok ne završiš

Za neparan broj diskova:

• Napravi ispravan potez između rupa A i C
• Napravi ispravan potez između rupa A i B
• Napravi ispravan potez između rupa C i B

Ponavljaj dok ne završiš

U svakom slučaju, ukupno je napravljeno 2ⁿ-1 poteza.

Ekvivalent iterativnog rešenja

Drugi način za generisanje jedinstveno optimalnog iterativnog rešenja:

Broj diskova od 1 do n ( od najmanjeg do najvećeg).

• Ako je n neparan, prvi potez je od A do C
• Ako je n paran, prvi potez je od A do B

Sada dodajte ova ograničenja:

• Nijedan neparan disk ne može ići direktno na drugi neparan disk.
• Nijedan paran disk ne može ići direktno na drugi paran disk
• Nikada ne poništavaj svoj prethodni potez ( to jest ne mrdaj disk nazad ka prethodnoj poziciji).

Imajući u vidu ta ograničenja nakon prvog poteza, postoji samo jedan pravi potez u svakom narednom slučaju.

Redosled ovih jedinstvenih poteza je optimalno rešenje za problem koji je ekvivalentan iterativnom rešenju, gore opisanom.

Rekurzivno rešenje

Interaktivna ilustracija rekurzivnog rešenja Hanojske kule sa 4 diska. Kliknite sivo dugme da otkrijete ili sakrijete fazu.

Ključ za rešavanje ovog problema je da se prizna da se problem može rešiti razbijanjem na manje probleme i dalje razbijanjem tih problema u još sitnije probleme sve dok se ne stigne do rešenja. Na primer:

• Obeležavanjem klinova A, B i C
• Neka je n ukupan broj diskova
• Broj diskova od (najmanji, najviši) do n (najveći, najniži)

Da biste premestili n diskova sa klina A na klin C:

1. Premesti n-1 disk sa A na B. Ovaj potez ostavlja n disk sam na klinu A.
2. Premesti disk n sa A na C
3. Premesti n-1 disk sa B na C, da se on nalazi na disku n

Navedeno je rekurzivni algoritam, da sprovede korake 1 i 3, važi isti algoritam i za n-1. Cela procedura je konačan broj koraka, jer u nekom trenutku će biti potreban algoritam za n= 1. Ovaj korak, pomeranja pojedinačnog diska sa klina A na klin C, je trivijalan. Ovom pristupu može se dodati rigorozan matematički formalizam sa teorijom dinamičko programiranje, programiranja, i često se koristi kao primer rekurzije na časovima programiranja.

Logička analiza rekurzivnog rešenja

Kao i u mnogim matematičkim zagonetkama, pronalaženje rešenja olakšava rešavanje nešto opštijih problema: Kako da pomerimo kulu H (h je visina) diskova izpočetnog klina A (f-form) na klin C (to), B je preostala trećna klina i pod pretpostavkom da f nije isto što i t. Prvo obratite pažnju da je problem simetričan za permutacije imena klinova simetrična grupa S3. Ako je rešenje poznato, pomeranje počinje od klina A do klina C, zatim preimenovanjem kočića, isto rešenje može koristiti za startovanje svakog drugog izbora i destinacije klina. Ako postoji samo jedan disk (ili čak nijedan), problem je trivijalan. Ako je h=1, onda jednostavno premestite disk sa klina A na klin C. Ako je h>1, onda negde u redosledu poteza, najveći disk se mora premestiti sa klina A na neki drugi klin, poželjno na klin C. Jedina situacija koja omogućava ovaj potez je kada svi manji h-1 diskovi su na poziciji B. Dakle, prvo svi n-1 manji diskovi moraju ići sa klina A na klin B. Nakon toga pomerite najveći disk i na kraju pomerite h-1 disk sa klina B u klin C. Prisustvo najvećeg diska ne ometa bilo koji potez od h-1 manjih diskova i trenutno se može ignorisati. Sada se problem svodi na pomeranje h-1 diskova sa jednog klina na drugi, prvo od A do B, i naknadno od B do C, ali isti metod može da koristi oba puta preimenovanjem klinova. Ista strategija može da se koristi da se smanji h-1 disk, do h-2 i h-3 i tako redom sve dok ne ostane samo jedan disk. Ovo se zove rekurzija. Ovaj algoritam se može šematski prikazati na sledeći način. Definišite diskove sa povećanjem veličine, od nula pa naviše, neuključujući h. Tako da diskovi idu od nula pa do h-1.

U nastavku je postupak za kretanje tornja od h diskova, od klina A do klina C, sa B koji je preostala trećina klina:

• PRVI KORAK: Ako je h>1 onda ovu proceduru koristite prvo za pomeranje h-1 manjih diskova sa klina A na klin B.
• DRUGI KORAK: Sada najveći disk, odnosno disk h možete premestiti sa klina A na klin C.
• TREĆI KORAK: Ako je h>1 onda onda opet koristiti ovaj postupak za za pomeranje h-1 manjih diskova sa klina B na klin C.

Pomoću matematička indukcija, lako je dokazati da navedena procedura zahteva minimalan mogući broj poteza, kao i da je proizvedeno rešenje jedino sa minimalni brojem poteza. Koristeći ponavljanje odnosa tačan broj poteza koje ovo rešenje zahteva može se izračunati na 2^h-1. Ovaj rezultat se dobija uz napomenu da koraci 1 i 3 troše T_h-1 pokreta, a korak 2 troši jedan pokret, dajući T_h=2T_h-1+1.

Ne-rekurzivno rešenje

Lista poteza za kulu sprovodi se od jednog klina na drugi, kao da je proizveden od rekurzivnog algoritma ima mnogo pravilnosti. Kada brojimo poteze počev od 1, redni broj diska koji se pomera tokom poteza m, je broj puta m koji se može podeliti sa 2. Zato svaki neparan potez podrazumeva najmanji disk. Takođe se može primetiti da najmanji disk prolazi kroz klinove f, t, r, f, t, r i slično za neparnu visinu tornja i prolazi kroz klinove f, r, t, f, r, t i slično za parnu visinu tornja. Ovo obezbeđuje sledeći algoritam, koji se lakše obavlja ručno, od rekurzivnog algoritma.

U alternativnim potezima:

• Pomeriti najmanji disk na klin sa kog nije skoro došao
• Pomeriti sledeći disk legalno (neće biti samo jedna mogućnost)

Za prvi potez, najmanji disk ide na klin t ako je h neparno, ili na klin p ako je h parno.

Takođe primetiti da:

• Diskovi čiji redni brojevi imaju parnu jednakost pomeraju se u istom smilsu kao i najmanji disk.
• Diskovi čiji redni brojevi imaju neparnu jednakost pomeraju se u obrnutom smislu.
• Ako je h parno, ostala trećina klina pri uspešnim pomerajima je t, r, f, t, r, f i tako dalje
• Ako je h neparno, ostala trećina klina pri uspešnim pomerajima je t, r, f, t, r, f i tako dalje.

Sa ovim znanjem, set diskova usred optimalnog rešenja, može se obnoviti sa ne više nego položajnih informacija, nego o pojedinačnoj poziciji svakog od njih:

• Pozovi poteze, gore navedene kao diskovi „Prirodni“ potez
• Ispitati najmanji vrhunski disk koji nije disk 0, a obratiti pažnju koji bi njen jedini (legalni) potez mogao da bude (ako ne postoji takav disk onda smo na prvom ili poslednjem koraku)
• Ako je potez diskov „prirodan“ potez onda disk nije pomeran od kad je disk 0 pomeren, i taj potez treba pokrenuti
• Ako taj potez nije diskov „prirodni“ potez onda pomeri disk 0

Binarno rešenje

Pozicije diskova mogu se odrediti više direktno iz binarnih predstavljanja broja pokreta (baze dva), početno stanje sa kao potez #0, sa svim ciframa 0, i finalno stanje #2ⁿ−1 sa svim ciframa 1, koristeći sledeća pravila:

• Postoji jedna binarna cifra (bit) za svaki disk
• Najznačajniji skroz levo bit predstavlja najveći disk. Vrednost 0 ukazuje na to da je najveći disk na početnom klinu, dok 1 ukazuje na to da je na finalnom klinu ( desni klin ako je broj diskova neparan ili pak srednji klin).
• Bitstring se čita sleva nadesno i svaki bit se može koristiti za određivanje lokacije odgovarajućeg diska.
• Bit sa istom vrednošću kao i prethodni znači da se odgovarajući disk slaže na vrh prethodnog diska na istom klinu ( To jest: ravno niz prvi ili nulti znači da su odgovarajući klinovi svi na istom klinu)

Bit sa različitim vrednostima sa prethodnim znači da je odgovarajući disk za jedno mesto ulevo ili udesno od prethodne. Da li je levo ili desno je utvrđeno ovim pravilom:

• Pretpostavimo da je početni klin sa leve strane
• Takođe pretpostavimo „prelom“, tako da pravi klin se računa kao jedan klin „levo“ levog klina, i obrnuto.
• Neka je n broj većih diskova koji se nalaze na istom klinu kao i njihov prvi veći klin, i dodajte jedan ako je najveći disk na levom klinu. Ako je n parno, disk se nalazi jedan klin sa leve strane (u slučaju parnog broja diskova ili pak drugačije).

Na primer : Hanojska kula sa 8 diskova :

• Potez 0 = 00000000
  • Najveći disk je 0 pa je levo (Inicijalni) klin
  • Svi ostali diskovi su 0 takođe, tako da su naslagani na vrh. Stoga svi diskovi su na početnom (inicijalnom) klinu.
• Potez 28-1 = 11111111
  • Najveći klin je jedan, i nalazi se na srednjem ili finalnom klinu.
  • Svi ostali diskovi su jedan, tako da su naslagani na vrhu. Stoga svi diskovi su na konačnom klinu pa je zagonetka završena.
• Potez 21610 = 11011000
  • Najveći disk je jedan i on je na srednjem (finalnom) klinu
  • Drugi disk je jedan takođe jedan pa je smešten na vrh tog klina, u sredini
  • Treći disk je nula, pa je smešten na drugom klinu. Pošto je n neparno (n=1) to je jedan klin sa leve strane, odnosno levi klin.
  • Četvrti disk je jedan, pa je to drugi klin. Pošto je ne neparno (n=1), to je jedan klin sa leve strane, odnosno desni klin.
  • Peti disk je takođe jedan, i smešten je na vrh desnog klina.
  • Šesti disk je nula pa je smešten na sledeći klin. Pošto je n parno (n=2), disk je jedno mesto nadesno, odnosno na levom klinu.
  • Sedmi i osmi disk su takođe nula, pa su smešteni na vrh, na levom klinu.

Izvorni i odredišni klinovi za mth pokret se mogu elegantno naći iz binarne reprezentacije m-a, koristeći operacije sa bitovima. Da bi koristili sintaksu u C programskom jeziku, pomerite m sa klina (m&m-1)%3 na klin ((m|m-1)+1)%3, gde diskovi počinju od klina 0 i završavaju se klinom 1 ili 2, u zavisnosti da li je broj diskova paran ili neparan. Druga formulacija je sa klina (m-(m&-m))%3 na klin (m+(m&-m))%3.

Osim toga, disk da bi se mogao pomerati određen je sa brojem puta u pokretu sabiranja (m) i može biti podeljen sa dva (odnosno, broj od nula bitova je na desnoj strani). Računajuči prvi potez kao prvi i idetifikovanjem diskova po brojevima 0,1,2 itd prema redosledu povećanja veličine. Ovo omogućava veoma brzo ne rekurzivno računarsko sprovođenje da bi se pronašla pozicija diskova posle m poteza bez pozivanja na bilo koji prethodni potez ili distribuciju diskova.

CTZ operacija, koja prebrojava uzastopne nule na krajevima binarnih brojeva, daje jednostavno rešenje za problem: diskovi su numerisani od nule, a na pokret m, disk broj CTZ(m) se preselio na najmanju moguću udaljenost sa desne strane (kruži oko kako bi se vratio nalevo ako bi bilo potrebno).

Rešenje Grejevog koda

Binarni numerički sistem cifara Grejev kod daje alternativni način rešavanja slagalice. U sivom sistemu brojevi su izraženi binarnim kombinacijama jedinice i nule, ali umesto da bude standardni numerički sistem, Grejev kod radi na pretpostavci da se svaka vrednost razlikuje od svog prethodnika za samo jedan ( i tačno jedan) bit promene. Broj bitova prisutnih u grejovom kodu je važan, a vodeće nule nisu opcija, za razliku od pozicionih sistema. Ako jedno brojanje u sivom kodu bitova po veličini je jednako broju diskova u Hanojskoj kuli, počinje od nule i broji, onda bit menja svaki potez koji odgovara potezu diska gde je najmanji bit u stvari najmanji disk, i najviše značajan bit je najveći.

Brojanje poteza od 1 i identifikovanje diskova brojevima, počevši od 0 sa povećanjem veličine, redni broj diska koji se preselio tokom pokreta m je broj puta m i može se podeliti sa dva.

Ova tehnika identifikuje koji disk da se kreće ali ne i gde da ga pomerite. Za najmanji disk postoje uvek dve mogućnosti. Za ostale diskove postoji uvek samo jedna mogućnost, osim kad se svi diskovi nalaze na istom klinu, ali u tom slučaju bilo da je najmanji disk on mora da se pomeri ili je cilj već postignut. Srećom postoji pravilo koje kaže gde da pomerite najmanji disk. Neka f bude početni klin, t odredište klina i p preostala trećina klina. Ako je broj diskova neparan, najmanji disk kruži duž klinova u smeru f→t→r→f→t→r, itd. Ako je broj diskova paran, ovo mora biti obrnuto f→r→t→f→r→t itd.

Grafička reprezentacija

Igra može biti predstavljena i uz pomoć indirektnog grafikona, čvorovi predstavljaju distribuciju diskova a ivice predstavljaju poteze. Za jedan disk grafik je trougao:

Grafikon za dva diska čine tri trougla respoređena u širem trouglu:

Čvorovi na temenima najspoljnijih trouglova predstavljaju raspodele svih diskova na istom klinu.

Za h+1 diskove, uzmite grafik h diskova, i zamenite svaki mali trougao sa grafikona sa druga dva trougla.

Za tri diskova grafik je:

• Nazovi klinove A, B i C
• Lista pozicije diskova sleva nadesno, po redosledu povećanja veličine.

Bokovi najspoljnijih trouglova predstavljaju najkraće načine kretanja kula sa jednog klina na drugi. Ivica usred strane najvećeg trougla predstavlja kretanje najvećeg diska. Ivica po sredini svake sledeće strane manjeg trougla predstavlja potez svakog narednog manjeg diska. Bokovi najmanjih trouglova predstavljaju poteze najmanjeg diska.

Igra grafika nivoa 7 pokazuje povezanost sa trouglom Sjerpinjskog.

Uopšteno, za slagalice sa n diskova, postoji 3ⁿ čvorova u grafikonu; svaki čvor ima tri ivice do ostalih čvorova, osim tri ugaona čvora, koji imaju dva; uvek je moguće da pomerite najmanji disk na jedan od druga dva klina a moguće je da se kreće jedan disk između ta dva klina osim u situaciji kad su svi diskovi naslagani na jedan klin. Ugaoni čvorovi predstavljaju tri slučaja u kojima su svi diskovi naslagani na jedan klin. Dijagram za n+1 diskova se dobija uzimanjem tri primerka dijagrama n diska- svaki od njih predstavlja položaje i poteze manjih diskova za jednu određenu poziciju novog najvećeg diska – i njihovo spajanje na uglovima sa novim ivicama koje predstavljaju samo tri mogućnosti za kretanje najvećeg diska. Dobijena cifra ima 3ⁿ⁺¹+1 čvorova i idalje ima tri ugla preostala sa samo dve ivice.

Kako se dodaje više diskova, grafik predstavljanja igre će ličiti na fraktal, trougao Sjerpinjskog. Jasno je da velika većina mesta u slagalici nikada neće biti postignuta kada koristite najmanja moguća rešenja. Zaista, da su sveštenici iz legende koristili najduže moguće rešenje (bez ponovnog posećivanja bilo koje pozicije) to bi im potrošilo oko 3⁶⁴ − 1 poteza ili više od 10²³ godina.

Najduži način bez ponavljanja za tri diska može se videti brisanjem neiskorišćenih ivica.

Uzgred, ovakav najduži put bez ponavljanja može se dobiti zabranjujući sve

Hamiltonov ciklus za tri diska izgleda:

Grafikon jasno pokazuje da:

• Iz svake proizvoljne distribucije diskova, tačno je jedan najkraći potez da se pomere svi diskovi na jedan od tri klina
• Između svakog para prozvoljne raspodele diskova postoje jedan ili dva najkraća puta.
• Iz svake proizvoljne distribucije diskova, postoje jedan ili dva duga različita ne-svoja puta za kretanje svih diskova na jedan od tri klina.
• Između svakog para proizvoljne raspodele diskova postoje jedan ili dva različita duga načina prelaska za kretanje tornja h diskova iz jednog klina na drugi. Zatim:
  • N₁ = 2
  • N_h+1 = (N_h)² + (N_h)³.
  • Na primer: N₈ ≈ 1.5456×10⁷⁹⁵

Aplikacije

Hanojska kula se često koristi u psihološkim istraživanjima u rešavanje problema. Takođe postoji varijanta ovog zadatka pod nazivom Kula Londona za neuropsihološku dijagnostiku i lečenje izvršnih funkcija.

Norman i Džang (Kognitivna nauka ) koristi nekoliko izomorfnih (ekvivalentnih) predstava igre za proučavanje uticaja reprezentacije efekata u dizajnu zadatka. Oni su pokazali uticaj na performanse korisnika na način na koji su pravila predstavljena, koristeći varijacije u fizičkom dizajnu komponenti igre. Ovo znanje je uticalo na razvoj okvira za ljudske računarske interakcije.

Hanojska kula se koristi kao rezervna šema rotacije prilikom obavljanja računarskih rezervnih kopija podataka gde je uključeno više traka tj medija.

Kao što je već pomenuto, hanojska kula je popularna za nastavu rekurzivnih algoritama za programiranje na početku studiranja. A piktorijal verzija ove slagalice je programirana u emaks editoru kojoj se pristupa kucanjem M-H hanoj. Tu je uzorak algoritma pisan u prologu. Hanojska kula se koristi kao test za neuropsihijatriske pokušaje da procene deficit frontalnog režnja.

U 2011 godini, istraživači su objavili rezultate eksperimenta koje je utvrdio da je mrav vrsta Linepithema koja je uspešno mogla da reši verziju 3 diska hanojske kule problema kroz nelinearnu dinamiku ili signale fermona.

Opšti najkraći putevi i broj 466/885

Zanimljiva generalizacija originalnog cilja slagalice je da se počne sa datom konfiguracijom diskova, gde svi diskovi nisu nužno na istom U principu to može biti prilično teško da izračunate najkraći niz poteza da biste rešili ovaj problem. Rešenje je predložio Andreas Hinz, a zasniva se na posmatranju da u najkraćem redosledu poteza, najveći disk koji treba da se pomera ( očigledno može ignorisati sve od najvećih diskova koji će se prostirati na istom klinu u obe početne i finalne konfiguracije ) će se pomeriti ili tačno jednom ili dva puta tačno.

Matematičke veze sa ovim problemom uopšteno postaju još zanimljivije kada se uzme u obzir prosečan broj kretanja u najkraćem redosledu poteza između dve početne i krajnje konfiguracije diska koje su izabrane nasumično. Hinz i Džan Hat Tung nezavisno su otkrili (vidite takođe, Chapter 1. str. 14) da je prosečan broj diskova u H kuli, daje sledećim tačnim formulama:

${\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{29}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{29}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.$

Imajte na umu da za veliko dovoljno n, samo prvi i drugi uslovi ne konvergiraju na nulu, tako da smo dobili asimptotski izraz : $466/885\cdot 2^{n}-1/3+o(1)$, as $n\to \infty$. Tako intuitivno, možemo inetpretirati frakciju $466/885\approx 52.6\%$ kao predstavu odnosa snage jedan mora da izvrši kada se ide iz nasumično izabrane konfiguracije na drugu nasumično izabranu konfiguraciju, u odnosu na teškoće moraju da pređu " najteži " put dužine 2n - 1 koji podrazumeva kretanje svih diskova sa jednog klina na drugi. Alternativno objašnjenje za pojavu stalnog 466/885, kao i novog i donekle pravilnog algoritma za izračunavanje najkraće putanje, dao je Romik .

Varijacije

Ciklični hanoj

U cikličnom Hanoju, imamo tri štipaljke ( A, B, C), koji su raspoređene kao krug sa smerom kazaljke na satu i suprotno od smera koji se definiše kao - B - C - A i A - C - B - respektivno. Pravac kretanja diska mora biti kao kazaljke na satu. Dovoljno je da predstavite niz diskova koji se pomeraju. Rešenje možete naći korišćenjem dva međusobno rekurzivna postupka:

Da biste premestili n diskove u smeru kazaljke na satu u susednu ciljani klin :

1. Pomerite n-1 diskove u smeru kazaljke na satu na ciljani klin
2. Pomerite #n disk jedan korak u smeru kazaljke na satu
3. Pomerite n-1 diskove u smeru kazaljke na satu na početni klin
4. Pomerite #n disk jedan korak u smeru kazaljke na satu
5. Pomerite n-1 diskove u smeru kazaljke na satu na ciljani klin

Da biste premestili n diskove u smeru kazaljke na satu u susedni ciljani klin :

1. Pomerite n-1 diskove u smeru kazaljke na satu na rezervni klin
2. Pomerite #n disk jedan korak u smeru kazaljke na satu
3. Pomerite n-1 diskove u smeru kazaljke na satu na ciljani klin

Neka C ( n) i A (n ) predstavljaju kretanje n diskova u smeru kazaljke na satu i suprotno, onda možemo zapisati obe formule :

         C(н) = A(н-1) н A(н-1)    и      A(н) = A(н-1) н C(н-1) n A(н-1).

          Tako  C(1) = 1                  и      A(1) = 1 1,
                C(2) = 1 1 2 1 1          и      A(2) = 1 1 2 1 2 1 1.

Rešenje za cikličan Hanoi ima neke zanimljive osobine :

1. Potez prenosa toranja diskova sa klin na drugi klin su simetrični u odnosu na centar.
2. Najmanji disk je prvi i poslednji za pomeranje.
3. Grupe najmanjih diskova potezima se smenjuju sa pojedinačnim potezima drugih diskova
4. Broj diskova poteza koje je navedeno pod C(n) i A(n) je najmanji.

Sa četiri klina i više

Iako verzija tri klina ima jednostavno rekurzivno rešenje kao što je gore navedeno, optimalno rešenje za Hanojsku kulu problema sa četiri klina ( tzv Reova puzla), a kamoli više klinova, još uvek je otvoren problem. Ovo je dobar primer kako jednostavan, rešiv problem može dramatično biti teži otpuštanjem jednog od problema ograničenja.

Činjenica da je problem sa četiri ili više klinovi otvoren problem ne znači da ne postoji algoritam za pronalaženje ( svih ) optimalnih rešenja. Jednostavno predstavljaju igru od strane grafikona, čvorovi čine distribuciju diskova a ivice čine poteze i koristeći pretragu u širinu prvo traže da nađu jedno (ili sve ) najkraćim putem (a ) prelazkom na toranj od jednog klina na drugu. Međutim, čak i pametno sprovođenje na najbrži računar je sada dostupno, ovaj algoritam ne daje nikakav način efikasnog računarskog rešenja za veliki broj diskova; Program će zahtevati više vremena i memorije nego što je na raspolaganju. Dakle, čak i da poznajemo algoritam, ostaje nepoznato koliko poteza optimalno rešenje zahteva i koliko postoji optimalnih rešenja za 1000 diskova i 10 klinovima.

Iako se ne zna tačno koliko potezi se mora napraviti, postoje asimptotski rezultati. Tu je i " pretpostavka - optimalnog rešenja" kojoj daje okvir Frejm Stevartov algoritam, otkriven je nezavisno od Frejma i Stjuarta 1941. godine. Odnošenje na Frejm – Stevartovo nagađanje tvrdi da Rama - Stjuart algoritam uvek daje optimalno rešenje. Optimalnosti okvira - Stevartovog algoritma je računski utvrdio za 4 klina sa do 30 diskova.

Za ostale varijante Hanojske kule sa problemom sa četiri kule, pogledajte papir Paul Stockmeierove ankete.

Frejm-Stevartov algoritam

Frame - Stjuart algoritam, dajući optimalno rešenje za četiri ( ili čak i više ) klinova, opisan je u nastavku:

• Neka je n broj diskova
• Neka je r broj klinova
• Definišemo T(n, r) da je minimalni broj poteza potrebnih za prenos n diskova koji koriste r klinovi

Algoritam može biti opisan rekurzivno :

1. a neko k, 1<=k<n, za prenos top k diskova na jedan klin osim početnih ili klinova destinacije, uzimajući T(k, r) poteza
2. Bez narušavanja klin koji sada sadrži top k diskove, prenosi preostale n-k diskove do odredišta klina, koristeći samo preostale r-1 klinove, uzimajući T(n-k, r-1) poteze.

Čitav proces traje 2T(k, r)+T(n-k, r-1) poteza. Dakle, k treba birati tako da je ova količina minimum. ( U četiri klinskom scenariju, idealno k je jednako koren iz 2n+1 zaobljeno minus 1. )

Hanojska kula sa više gomila

Patent broj 7.566.057 izdaje Viktor Mascolo otkriva zagonetku Hanojske kule sa dve ili više gomile i duplo više klinova kao gomila. Nakon početka na određenom klinu, svaki gomila se pomera i biva raseljena od strane gomile druge boje na drugom klinu kada se rešava slagalice. Diskovi jedne boje i još jedan klin koji isključuje sve ostale boje, tako da postoje tri štipaljke na raspolaganju za svaki disk boje, dva se dele sa drugim bojama, i onaj koji se ne deli. Na zajedničkim klinovima, disk ne može biti postavljen na drugi disk druge boje iste veličine, mogućnost da se ne pojavljuje u standardnoj slagalice.

Najjednostavnija igra sa više gomila ( 2 × 4 ), ima dve gomile i četiri klinovi, i zahteva 3[T(n)] poteza da reše gde je T(n) broj poteza potreban da reši pojedinačan klin sa n diskova. Igra se nastavlja sa sve dužim i dužim nizom poteza koji variraju između boja. U njemu se zaključuje u obrnutom načinu sa sve kraćim i kraćim takvim serijama poteza. Počevši od druge serije od tri poteza, alternativni niz poteza se udvostručuje po dužini za prvu polovinu utakmice, a dužine su prepolovljene kako se igra zaključuje. Rešenje uključuje algoritam pogodan za Hanosjku kulu u algoritmu koji ukazuje na prebacivanje između boja. Kada postoje k gomile n diskova po komadu u igri, i k>2, to zahteva K[T(n)]+T(n-1)+1 poteza da ih premesti.

Dodavanje u centralni deo univerzalnog klina otvorenog za diskove sa svih klinova pretvara ovu zagonetke Hanojske kule sa više gomila u Reovu zagonetku sa više gomila kao što je opisano u prethodnom odeljku. U ovim igrama svaka gomila može da se kreće između četiri klina, ista kombinacija za tri u igri 2 × 4 plus centralni univerzalni klin. Najjednostavniji igra ove vrste ( 2 × 5 ) ima dve gomile i pet klinove. Rešenje je pretpostavljeno da bude optimalno rešenje 2 × 4 slagalice sa pretpostavljenim optimalnim rešenjem za Reovu zagonetku. Potrebno je R(n)+2R(n-1)+2 poteza, gde je R(n) broj poteza u pretpostavljenom optimalnom rešenju Reove zagonetke za gomilu n diskova.

Magnetni Hanoj

U magnetnoj hanojskoj kuli, svaki disk ima dve odvojene strane Severnu i Južnu ( obično u boji "crveno" i " plavo" ). Diskovi ne moraju biti postavljene sa sličnim polovima zajedno - magneti za svaki disk sprečavaju ovaj nelegalni potez. I svaki disk se mora okrenuti, kao što se pomera.

Početna konfiguracija Hanojske kule sa dve boje (n=4)

Kula sa dve boje

Ova varijacija čuvene slagalice Hanojske kule je ponuđena učenicima razreda 3-6 na 2ème Championnat de France des Jeux Mathématiques et Logiques održane u julu 1988. godine.

Krajnja konfiguracija Hanojske kule sa dve boje (n=4)

Pravila slagalice su u suštini ista : diskovi se prenose između klinova jedan po jedan. Ni u jednom trenutku ne može veći disk biti postavljen na vrh jednog manjeg. Razlika je u tome što sada za svaku veličinu postoje dva diska : jedan crni i jedan beli. Takođe, sada postoje dve kule diskova naizmeničnih boja. Cilj slagalice je da se stvore jednobojni tornjevi ( iste boje). Za najveće diskove na dnu kule se pretpostavlja da menjaju pozicije.

Detaljno rekurzivno rešenje ovakve kule se raspravlja ovde : http://rmm.ludus-opuscula.org/PDF_Files/Chaugule_BicolorHanoi_37_48(4_2015)_low.pdf

Hanojska kula u popularnoj kulturi

U priči naučne fantastike "Sada Udahnite ", Erik Frank Russell, čovek je zarobljenik na planeti gde je lokalni običaj da zatvorenik igra igru sve dok ne pobedi ili izgubi pre njegovog pogubljenja. Glavni junak zna da spasilački brod može potrajati godinu ili više da stigne, pa on bira da igra Hanojsku kulu sa 64 diskova. (Ova priča pominje legende o budističkim monasima koji igraju utakmicu do kraja sveta.)1966 godine priča doktora Hua, Nebeski Toimaker, eponimski zlikovac primorava doktora da igraju deseto komadni 1.023 - poteze igre Hanojske kule poznate pod nazivom Trilodžik igra sa komadima koji formiraju oblik piramide kada se slažu.

U 2007. godini, koncept problema Hanojske kule je korišćen kod profesora Laiton i Diaboličkoj kutiji iz zagonetke 6, 83, i 84, ali su diskovi bili zamenjeni sa palačinkama. Zagonetka je zasnovana na dilemi gde je kuvar restorana morao hrpu palačinki sa jedne ploče premesti na drugu sa osnovnim principima originalne puzle ( tj tri ploče na kojima bi se palačinke mogle pomeriti, nisu bili u stanju da stave veću palačinku na manju, itd )

U filmu Planeta majmuna: Početak (2011), ove kule, nazivane u filmu "Lukasova kula", se koriste kao test za proučavanje inteligencije majmuna.

Zagonetka se redovno pojavljuje u avanturama i slagalicama. Budući da je lako sprovesti i lako prepoznati, pošto je dobro prilagođena za korišćenje kao slagalice u većim grafičkim igrama ratovi zvezda i Mass Effect ). Neke implementacije koriste prave diskove, ali druge prikrivaju slagalicu u nekoj drugoj formi. Postoji verzija arkada za Sega / Andamiro.

Problem je predstavljen kao deo nagrada izazov u 2011. u epizodi američke verzije Survivor TV serija. Oba igrača ( Ozzi Lusth i Benjamin " Trener " Vade) borila su se da shvate kako da reše zagonetku i uz pomoć svojih kolega članova plemena.

U nauci i materijalima

3D AFM Topografska slika višeslojnog paladijuma, sa strukturom Hanojske kule.

U 2014, naučnici sintetiše višeslojna paladijum nanosheet sa strukturom poput Hanojske kule. Ovo je prvi put da se slična struktura posmatra u prirodi.

Vidi još

• Šema rotacije, TOH aplikacija
• Baguenaudier
• Rekurzija (nauka o računarima)

Literatura

• Warren, Henry S. (2003). „Section 5-4: Counting Trailing 0's.”. Hacker's delight (1st izd.). Boston MA: Addison-Wesley. ISBN 978-0-201-91465-8. 
• Sniedovich, Moshe (2010). Dynamic Programming: Foundations and Principles. Taylor & Francis. ISBN 978-0-8247-4099-3. Arhivirano iz originala 24. 09. 2015. g. Pristupljeno 29. 10. 2015. 
• Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. str. 197. ISBN 978-0-8218-4814-2. 
• Moscovich, Ivan (2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN 978-0-7611-1826-8. 
• Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. str. 137. ISBN 978-0-03-084693-9. 
• Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 978-0-465-04540-2. 

Spoljašnje veze

• Weisstein, Eric W. „Tower of Hanoi”. MathWorld. 
• Tower of Hanoi animation