Modelová sada věží Hanoje (s 8 disky)
Animované řešení Hanojské věže puzzle pro T(4,3).
Hanojská věž nebo Hanojské věže je matematická hra nebo puzzle. Skládá se ze tří kolíků a množství disků různých velikostí, které mohou klouzat na jakýkoliv kolík. Puzzle začíná tím, že disky jsou úhledně naskládány v pořadí podle velikosti na jednom kolíku, ten nejmenší nahoře, čímž vzniká kuželovitý tvar.
Skládanku vynalezl francouzský matematik Édouard Lucas v roce 1883. Existuje legenda o indickém chrámu, který obsahuje velkou místnost se třemi časem opotřebovanými sloupky obklopenou 64 zlatými disky. Brahmovi kněží, kteří vykonali příkaz starověkého proroctví, hýbali s těmito disky v souladu s pravidly skládačky. Podle legendy, když je dokončen poslední tah skládačky, nastane konec světa. Skládanka je proto známá také jako Brahmova věž. Není jasné, zda Lucas tuto legendu vynalezl nebo se jí inspiroval. Hanojská věž je problém často používaný k výuce začínajícího programování, zejména jako příklad jednoduchého rekurzivního algoritmu.
Pokud by legenda byla pravdivá a pokud by kněží byli schopni pohybovat disky rychlostí jednoho za sekundu při použití nejmenšího počtu pohybů, trvalo by jim to 264−1 sekundy nebo zhruba 600 miliard let (probíhající operace je ) . (V kontextu, vesmír je v současné době asi 13,7 miliard let starý.)
Existuje mnoho variant této legendy. Například v některých sděleních je chrám klášterem a kněží jsou mniši. Lze říci, že chrám nebo klášter se nachází v různých částech světa – včetně Hanoje, Vietnamu, a může být spojen s jakýmkoli náboženstvím. V některých verzích jsou zavedeny další prvky, jako například skutečnost, že věž byla vytvořena na počátku světa, nebo že kněží nebo mniši mohou udělat pouze jeden pohyb denně.
Vlajková věž v Hanoji mohla sloužit jako inspirace pro název.
Většina hračkářských verzí puzzle má 8 disků. Hra se mnoha nováčkům zdá nemožná, přesto je řešitelná jednoduchým algoritmem:
Následující řešení je jednoduchým řešením pro hračku puzzle.
Střídavě se pohybuje mezi nejmenším kusem a nejmenším kusem. Při pohybu nejmenšího kusu se pohybuje vždy stejným směrem (buď doleva nebo doprava, ale buďte důslední). Pokud ve zvoleném směru není žádná věž, posuňte ji na opačný konec. Když se otáčí, aby se pohnul nejmenším kusem, je jen jeden legální pohyb.
Jako v mnoha matematických hádankách, hledání řešení je usnadněno vyřešením o něco obecnějšího problému: jak přesunout věž h (h=výška) disků z počátečního kolíku f (f=z) na cílový kolík t (t=do), r je zbývající třetí kolík a za předpokladu t ≠ f. Nejprve si všimněte, že problém je symetrický pro permutace názvů kolíků (symetrická skupina S3). Pokud je známo řešení pohybující se z kolíku f na kolík t, pak přejmenováním kolíků může být stejné řešení použito pro každou další volbu počátečního a cílového kolíku. Pokud existuje pouze jeden disk (nebo dokonce žádný), problém je triviální. Pokud h=1, pak jednoduše přesuneme disk z kolíku f na kolík t. Pokud h>1, pak někde v pořadí přesunů musí být největší disk přesunut z kolíku f na jiný kolík, nejlépe na kolík t. Jediná situace, která tento přesun umožňuje, je, když jsou všechny menší disky h-1 na kolíku r. Proto nejprve musí všechny menší disky h-1 přejít z f na r. Následně přesuneme největší disk a nakonec přesuneme menší disky h-1 z peg r do peg t. Přítomnost největšího disku nebrání jakémukoli přesunu menších disků h-1 a může být dočasně ignorována. Nyní je problém redukován na přesun disků h-1 z jednoho peg do druhého, nejprve z f do r a následně z r do t, ale stejnou metodu lze použít v obou případech přejmenováním kolíků. Stejnou strategii lze použít pro redukci problému h-1 na h-2, h-3 a tak dále, dokud nezůstane jen jeden disk. Tomu se říká rekurze. Tento algoritmus lze schematizovat následovně. Identifikujte disky v pořadí podle zvětšení přirozenými čísly od 0 do, ale nezahrnující h. Proto disk 0 je nejmenší a disk h-1 největší.
Následující postup je postup pro přesun věže h disků z kolíku f na kolík t, přičemž r je zbývající třetí kolík:
Pomocí matematické indukce je snadno prokázáno, že výše uvedený postup vyžaduje minimální možný počet pohybů a že vyrobené řešení je jediné s tímto minimálním počtem pohybů.
Pomocí relací opakování lze vypočítat přesný počet tahů, které toto řešení vyžaduje: . Tohoto výsledku se dosáhne tak, že se poznamená, že kroky 1 a 3 se pohybují, a krok 2 se pohybuje jedním tahem, přičemž .
Řešení z libovolné počáteční konfigurace
Pro nalezení optimálního řešení z libovolné počáteční konfigurace lze algoritmus zobecnit následovně:
trbDiscs je lišta pro výběr množství disků
Seznam pohybů pro věž, které se přenášejí z jednoho kolíku na druhý, jak je vyprodukován rekurzivním algoritmem, má mnoho zákonitostí. Při počítání pohybů začínajících od 1 je řadová číslice disku, který se má během pohybu m přesunout, počtem, kolikrát může být m děleno 2. Proto každý lichý pohyb zahrnuje nejmenší disk. Lze také pozorovat, že nejmenší disk prochází kolíky f, t, r, f, t, r, atd. pro lichou výšku věže a prochází kolíky f, r, t, f, r, t, atd. pro sudou výšku věže. To poskytuje následující algoritmus, který je jednodušší, prováděný ručně, než rekurzivní algoritmus.
Pro úplně první tah, nejmenší disk jde do peg t, pokud h je lichý a do peg r, pokud h je sudý.
Pokud je tedy počet disků vyrovnaný, řešení začne:
Například v 8-disk Hanoi:
Výše uvedený algoritmus lze ve Schématu kódovat následovně:
Binární číselná soustava šedých kódů poskytuje alternativní způsob řešení hádanky. V šedém systému jsou čísla vyjádřena v binární kombinaci nul a jedniček, ale spíše než jako standardní poziční číselná soustava pracuje šedý kód s předpokladem, že každá hodnota se liší od svého předchůdce pouze o jeden (a přesně jeden) změněný bit. Počet bitů přítomných v šedém kódu je důležitý a úvodní nuly nejsou volitelné, na rozdíl od pozičních systémů.
Pokud počítáme v Grayově kódu velikost bitu rovnající se počtu disků v konkrétní Hanojské věži, začíná na nule a počítá se, pak změněný bit každým pohybem odpovídá disku k přesunu, kde nejmenší-významný-bit je nejmenší disk a nejvýznamnější-bit je největší.
Tato technika určuje, který disk má být přesunut, ale ne kam. U nejmenšího disku jsou vždy dvě možnosti. U ostatních disků je vždy jedna možnost, kromě případů, kdy jsou všechny disky na stejném kolíku, ale v takovém případě je to buď nejmenší disk, který musí být přesunut, nebo již bylo cíle dosaženo. Naštěstí existuje pravidlo, které říká, kam má být nejmenší disk přesunut. Nechť f je počáteční kolík, t cílový kolík a r zbývající třetí kolík. Pokud je počet disků lichý, nejmenší disk cykluje podél kolíků v pořadí f->t->r->f->t->r, atd. Pokud je počet disků sudý, musí být obrácený: f->r->t->f->r->t atd.
Úpravou hry může být přesun věže z jednoho kolíku na druhý pomocí co největšího počtu pohybů, aniž by došlo ke stejnému rozdělení disků více než jednou. Jednoduchý algoritmus (napsaný v Scheme) je:
Kde procedura (move-disk d f t r) přesune disk d z peg f na peg t, ignoruje peg r. Počet tahů tohoto jedinečně definovaného řešení je 3height-1 a všechna 3height různá rozdělení disků jsou procházena (při zahrnutí počáteční a konečné distribuce). Tomu se říká Hamiltonova cesta. Pro toto řešení lze disk, který má být přesunut, nalézt s trojkovým šedým kódem podobným způsobem, jak je vysvětleno pro nejkratší řešení. Ve skutečnosti existuje trojkovitý šedý kód začínající všemi číslicemi 0 a končící všemi číslicemi rovnými 2, který uvádí postupná rozdělení disků Hamiltonovy cesty z peg 0 na peg 2 pro věž h disků, přičemž každý kód ukazuje pozice disků v sestupném pořadí podle velikosti při čtení zleva doprava. Tento šedý kód je jedinečně definován uložením dodatečné podmínky, že každá číslice je přepínána častěji než každá významnější číslice vlevo. Toto je kód potřebný pro věž v Hanoji.
Disk, který má být přesunut, je určen tím, kolikrát může být počítadlo tahu děleno 3. Místo, kam má být disk přesunut, může být také snadno určeno. Za každou trojici tahů dvakrát za sebou ve stejném směru přesuňte nejmenší disk, následovaný tahem jednoho z větších disků (pouze jeden směr je možný) Mezi každou trojicí tahů obraťte směr nejmenšího disku. Úplně první tah nejmenšího disku má být proveden z počátečního kolíku na zbývající třetí kolík. Všimněte si také, že nepoužitý kolík každého tahu se střídá mezi počátečním a cílovým kolíkem. Tato tvrzení lze snadno prokázat matematickou indukcí.
Další úpravou je přemístění věže z kolíku zpět na stejný kolík při procházení všech distribucí disků. (kruhová Hamiltonova cesta) Existují přesně dvě řešení, ale zrcadlí se navzájem v tom smyslu, že ve skutečnosti existuje jedna cesta, kterou lze procházet v obou směrech. Je zřejmé, že délka cesty je 3height. Jednoduchý algoritmus pro kruhovou Hamiltonovu cestu je:
Hra může být reprezentována neřízeným grafem, uzly reprezentující rozdělení disků a větve reprezentující tahy. Pro jeden disk je graf trojúhelník:
Pro h+1 disky, vezměte graf h disků a nahraďte každý malý trojúhelník:
Výše uvedený graf je pro 2 disky. Úhlové body krajního trojúhelníku představují rozdělení se všemi disky na jednom kolíku. Pro 3 disky je graf:
Každá strana krajního trojúhelníku představuje nejkratší způsoby přesunu věže z jednoho kolíku na druhý. Větev uprostřed stran největšího trojúhelníku představuje přesun největšího disku. Větev uprostřed stran každého dalšího menšího trojúhelníku představuje přesun každého dalšího menšího disku. Strany nejmenších trojúhelníků představují přesuny nejmenšího disku.
Kruhová hamiltonová cesta pro tři disky je:
Grafy jasně ukazují, že:
Hanojská věž je často využívána v psychologickém výzkumu řešení problémů. Existuje také varianta tohoto úkolu zvaná londýnská věž pro neuropsychologickou diagnostiku a léčbu výkonných funkcí.
Hanojská věž se také používá jako rotační schéma zálohování při provádění počítačových dat Zálohy, kde se jedná o více pásek/médií.
Jak bylo uvedeno výše, Hanojská věž je populární pro výuku rekurzivních algoritmů začínajícím studentům programování. Obrazová verze této skládačky je naprogramována do editoru emacs, ke kterému se přistupuje zadáním M-x hanoi. V Prologu je také napsán ukázkový algoritmus.
Hanojská věž je také používána jako paměťový test neuropsychology, kteří se snaží vyhodnotit amnézii.
Ačkoli má tříkolková verze jednoduché rekurzivní řešení, jak je uvedeno výše, optimální řešení pro problém Hanojské věže se čtyřmi nebo více kolíky je stále otevřeným problémem. To je dobrý příklad toho, jak lze jednoduchý, řešitelný problém dramaticky ztížit mírným uvolněním jednoho z omezení problému.
Skutečnost, že problém se čtyřmi nebo více kolíky je otevřený problém, neznamená, že neexistuje žádný algoritmus pro nalezení (všech) optimálních řešení. Jednoduše reprezentujte hru pomocí neřízeného grafu, uzly jsou distribuce disků a hrany jsou pohyby (o délce 1) a použijte Dijkstrův algoritmus pro nalezení jedné (nebo všech) nejkratší cesty pohybující se věží z jednoho kolíku na druhý. Nicméně, i když je tento algoritmus šikovně implementován na nejrychlejším počítači, který je nyní k dispozici, neposkytuje žádný způsob efektivního výpočtu řešení pro velké množství disků; program by vyžadoval více času a paměti, než je k dispozici. Tudíž, i když máme algoritmus, zůstává neznámé, kolik pohybů optimální řešení vyžaduje a kolik optimálních řešení existuje pro 1000 disků a 10 kolíků.
Ačkoli není přesně známo, kolik tahů musí být provedeno, existují určité asymptotické výsledky. Existuje také „předpokládané-optimální řešení“, které lze rekurzivně aplikovat při hledání řešení – viz průzkum Paula Stockmeyera pro vysvětlení a některé varianty problému se čtyřmi kolíky.
Ačkoli souhlasí s počítačovými experimenty pro malé počty disků, neexistuje dosud obecný důkaz, že toto předpokládané optimální řešení je ve skutečnosti optimální. Výsledky z roku 2004 však ukázaly, že předpokládané optimální řešení musí být stejného řádu jako optimální řešení.
Popis předpokládaného optimálního řešení
Problém pro čtyři kolíky se někdy nazývá „Reveho puzzle“. Řešení pro čtyři (nebo více) kolíků, které nebylo prokázáno jako optimální, je popsáno níže:
Algoritmus lze popsat rekurzivně:
Celý proces se pohybuje. Proto by měl být vybrán počet, pro který je toto množství minimální.
Předpokládá se, že tento algoritmus (s výše uvedenou volbou pro ) je optimální a nejsou známy žádné protipříklady.
Dva stohy a více stohů
Nedávná patentová přihláška USA odhaluje multistack Tower of Hanoi puzzle [1.února 2007, sériové č.11/701,454] se dvěma nebo více zásobníky a dvakrát více kolíky než zásobníky. Po začátku na konkrétní kolík, každý zásobník přemístí a je přemístěn různobarevný zásobník na jiný kolík, když je puzzle vyřešeno. Disky jedné barvy mají také další kolík, který vylučuje všechny ostatní barvy, takže existují tři kolíky k dispozici pro každý barevný disk, dva, které jsou sdíleny s jinými barvami a jeden, který není sdílen. Na sdílené kolíky, disk nesmí být umístěn na různobarevný disk stejné velikosti, možnost, která nevzniká ve standardní puzzle.
Nejjednodušší hra s více zásobníky (2 x 4) má dva zásobníky a čtyři kolíky a vyžaduje 3[T(n)] tahy, aby vyřešila, kde T(n) je počet tahů potřebných k vyřešení jednoho zásobníku klasických n disků. Hra postupuje jako na houpačce s delšími a delšími sériemi tahů, které se střídají mezi barvami. Končí obráceným způsobem na houpačce s kratšími a kratšími takovými sériemi tahů. Počínaje druhou sérií tří tahů se tyto alternativní série tahů zdvojnásobí v délce pro první polovinu hry a délky se zmenší na polovinu, jak hra končí. Řešení zahrnuje vnoření algoritmu vhodného pro Tower of Hanoi do algoritmu, který určuje, kdy přepínat mezi barvami. Když je ve hře k zásobníků n disků za kus a k > 2, vyžaduje k[T(n)] + T(n-1) tahy k jejich přemístění.
Přidáním centrálně umístěného univerzálního kolíku otevřeného pro disky ze všech zásobníků se tyto multistackové hlavolamy Tower of Hanoi převedou do multistackových hlavolamů Reveho, jak je popsáno v předchozí části. V těchto hrách se každý zásobník může pohybovat mezi čtyřmi kolíky, stejnou kombinací tří ve hře 2 x 4 plus centrálním univerzálním kolíkem. Nejjednodušší hra tohoto druhu (2 x 5) má dva zásobníky a pět kolíků. Řešení odhadované jako optimální prolíná optimální řešení 2 x 4 hlavolamu s předpokládaným optimálním řešením Reveho hlavolamu. Trvá R(n) + 2R(n-1) + 2 tahy, kde R(n) je počet tahů v předpokládaném optimálním řešení Reveho pro zásobník n disků.
V klasickém sci-fi příběhu Now Inhale od Erica Franka Russella (Astounding Science Fiction April 1959 a v různých antologiích) je lidský hrdina vězněm na planetě, kde je místním zvykem nutit vězně hrát hru, dokud není vyhrána nebo prohrána, a pak je okamžitá poprava. Hrdinovi je řečeno, že hra může být jedním z jeho vlastního druhu, pokud ji lze hrát v jeho cele s jednoduchým vybavením přísně podle pravidel, která jsou napsána dříve a nemohou se změnit po začátku hry, a má konečný koncový bod. Hra a poprava jsou vysílány po celé planetě a sledovat zoufalého vězně, jak se snaží hru roztočit co nejdéle, je velmi populární zábava; rekord je šestnáct dní. Hrdina ví, že záchrané lodi může trvat rok i déle, než dorazí, a tak se rozhodne hrát Towers of Hanoi se 64 disky, dokud nedorazí záchrana. Když si místní uvědomí, že byli podvedeni, jsou naštvaní, ale podle jejich vlastních pravidel s tím nemohou nic dělat. Změní pravidla, která budou platit pro všechny budoucí vězně. Tento příběh odkazuje na legendu o buddhistických mniších, kteří hráli hru až do konce světa, a odkazuje na hru jako arkymalarky. (slangový výraz „malarky“, což znamená nesmysl, datuje tento příběh nejméně o 30 let. )
Ve filmu Cizinec než fikce je na přeplněném stole profesora Julese Hilberta k vidění miniaturní puzzle Towers of Hanoi.
V seriálu Doctor Who „Nebeský hračkář“ vyzve hračkář Doktora, aby dokončil „Trilogickou hru“ (deset disků Hanoj) přesně za 1 023 (210 − 1) tahů.
Existuje kapela s názvem Towers of Hanoi.
Puzzle se pravidelně objevuje v adventurách a puzzle hrách. Vzhledem k tomu, že je snadno implementovatelné a snadno rozpoznatelné, dobře se hodí pro použití jako puzzle ve větší grafické hře. Některé implementace používají rovné disky, ale jiné zamaskují puzzle v nějaké jiné formě. Následuje částečný seznam her, které puzzle používají: