Wieże Hanoi

Wieże Hanoi to łamigłówka z trzema słupkami i krążkami o różnych średnicach, nałożonymi na pierwszy słupek od największego na dole do najmniejszego na górze. Celem jest przeniesienie całej wieży na ostatni słupek, czyli słupek docelowy. W jednym ruchu przekłada się jeden krążek, zawsze ten z wierzchu, i nigdy nie kładzie się większego krążka na mniejszym. Środkowy słupek pełni rolę słupka pomocniczego.

Na planszy słupki mają litery A, B i C, a ostatni ma podpis „cel”. Krążek 1 jest najmniejszy; numery na krążkach można wyłączyć w opcjach. Pierwsza gra zaczyna się od 4 krążki na słupku A, które da się ułożyć w 15 ruchach, a liczbę krążków wybiera się od 3 do 10.

Krążek przenosi się na trzy sposoby. Stuknięcie lub kliknięcie słupka podnosi jego górny krążek, a stuknięcie innego słupka go tam odkłada. Krążek można też przeciągnąć palcem albo myszą. Z klawiatury, gdy słupek jest zaznaczony klawiszem Tab, cyfra lub litera słupka podnosi i odkłada krążek, Escape oddaje podniesiony krążek, a strzałki przechodzą między słupkami.

Ruch niezgodny z zasadami nie dochodzi do skutku, a gra podaje powód, na przykład „Krążek 2 nie może leżeć na krążku 1”. Plansza lekko się wtedy trzęsie, chyba że w systemie włączono ograniczenie animacji. Trzy liczniki pod planszą pokazują wykonane ruchy, najmniejszą możliwą liczbę ruchów w tej grze oraz czas, który rusza z pierwszym ruchem i staje po ułożeniu wieży.

Po ułożeniu gra podaje czas z dokładnością do dziesiątej części sekundy oraz liczbę podpowiedzi i cofniętych ruchów. Przycisk „Kopiuj wynik” kopiuje linijkę z wynikiem razem z linkiem, a kolejny przycisk dokłada krążek do następnej gry.

Najmniejsza liczba ruchów dla n krążków to 2^n - 1, więc wieża z 5 krążków wymaga co najmniej 31 ruchów, z 6 krążków 63, a z 8 krążków 255. Każdy dodatkowy krążek podwaja tę liczbę i dodaje jeden ruch, bo cała mniejsza wieża musi zejść z największego krążka i potem na niego wrócić. Więcej ruchów wolno wykonać: gra przyjmie każde poprawne ułożenie, a licznik pokaże różnicę względem minimum. Przy jednym ruchu na sekundę sześć krążków zajmuje 1 min 3 s, a dziesięć już 17 min 3 s. Kolumna z ustawieniami podaje, na ile sposobów krążki mogą stać na trzech słupkach zgodnie z zasadami.

Szybkość ręki mierzy rekord Guinnessa. Według Guinness World Records wieżę z 6 krążków najszybciej ułożono w 22,26 s, a rekord należy do Lim Kai Yi od 15 listopada 2024 roku. To co najmniej 63 ruchy, czyli około 2,8 ruchu na sekundę. Tak wyglądał rekord w dniu sprawdzenia tej strony, 23 października 2026 roku.

Te same liczby gra podaje w liczniku minimum, a porównanie ze znanymi odpowiedziami pokazuje cztery wieże z tabeli Lucasa, łamigłówki Dudeneya i zadania maturalnego, każdą z linkiem do gry.

Wystarczy na zmianę wykonywać dwa rodzaje ruchów: najmniejszy krążek przechodzi na kolejny słupek, zawsze w tym samym kierunku, a potem inny krążek wykonuje jedyny dozwolony ruch. Przy pięciu krążkach, jak przy każdej nieparzystej liczbie, najmniejszy krążek idzie najpierw na słupek C i krąży w kolejności A → C → B → A. Przy parzystej liczbie zaczyna od słupka B i krąży w kolejności A → B → C → A.

Między dwoma ruchami najmniejszego krążka zostaje tylko jeden dozwolony ruch, który go nie dotyka: z dwóch pozostałych krążków na wierzchu tylko mniejszy może trafić na większy albo na pusty słupek. Najmniejszy krążek rusza się więc co drugi ruch, w każdym ruchu o numerze nieparzystym. Lucas w trzecim tomie „Récréations mathématiques” przypisuje tę regułę Raoulowi Olive, uczniowi liceum Charlemagne.

Lekcja „Zagadka Wież Hanoi” na Zintegrowanej Platformie Edukacyjnej (ZPE) nazywa ten sposób rozwiązaniem iteracyjnym. Dla trzech krążków to rozwiązanie iteracyjne ma 7 ruchów, zapisanych tu jako numer krążka, słupek startowy i docelowy. Kolejno są to 1: A→C, 2: A→B, 1: C→B, 3: A→C, 1: B→A, 2: B→C, 1: A→C.

Pełne rozwiązanie dla pięciu krążków ma 31 ruchów. Najmniejszy krążek wykonuje w nim 16 z nich, a największy rusza się tylko raz, w ruchu 16, dokładnie w połowie drogi.

W grze ta sama lista ruchów leży pod planszą jako „Rozwiązanie ruch po ruchu” i podświetla następny ruch, dopóki gra idzie zgodnie z nią. Przycisk „Drukuj listę ruchów” drukuje samą listę, bez planszy, dla dowolnej liczby krążków.

Rekurencja sprowadza wieżę z n krążków do dwóch wież z n - 1 krążków i jednego ruchu. Najpierw n - 1 mniejszych krążków trafia na słupek pomocniczy, potem największy krążek przechodzi na słupek docelowy, a na końcu n - 1 krążków wraca na niego ze słupka pomocniczego. Przypadek bazowy to jeden krążek, który przenosi się jednym ruchem.

Lekcja ZPE „Misja matura: Zadanie 1. Wieże Hanoi” podaje pręty jako parametry: x to pręt startowy, y docelowy, a z pomocniczy. Pseudokod procedury hanoi(n, x, y, z) mieści się wtedy w czterech krokach:

1. Jeśli n = 1, przenieś krążek z x na y i zakończ.
2. W przeciwnym razie wykonaj hanoi(n - 1, x, z, y), czyli odłóż mniejszą wieżę na pręt pomocniczy.
3. Przenieś największy krążek z x na y.
4. Wykonaj hanoi(n - 1, z, y, x), czyli nałóż mniejszą wieżę na największy krążek.

Liczbę ruchów opisuje relacja rekurencyjna H(n) = 2H(n - 1) + 1, z H(1) = 1: dwie mniejsze wieże i jeden ruch największego krążka. Tak zapisuje ją Centralna Komisja Egzaminacyjna w zadaniu 9 „Wieże z Hanoi” ze zbioru zadań do egzaminu maturalnego z informatyki na poziomie rozszerzonym. Tabela w tym zadaniu kończy się na H(10) = 1023.

Robert Sedgewick i Kevin Wayne z Uniwersytetu Princeton pokazują ten sam algorytm rekurencyjny w rozdziale o rekurencji swojego kursu programowania. Podstawa programowa dla liceum i technikum z 2018 roku (Dz.U. 2018 poz. 467) wymienia rekurencję w informatyce w zakresie rozszerzonym, choć samej łamigłówki z nazwy nie podaje. Matura z informatyki sprawdza więc samą metodę, a wieże służą za jej przykład w zbiorze zadań CKE i w lekcjach ZPE.

Wzór na wieżę Hanoi wynika z prostej obserwacji: największy krążek musi się ruszyć co najmniej raz, a w chwili tego ruchu wszystkie mniejsze krążki muszą stać razem na trzecim słupku. Mniejsza wieża musi więc przejść dwa razy, a największy krążek raz.

Dowodem jest indukcja matematyczna. Jeden krążek wymaga jednego ruchu, czyli 2^1 - 1. Jeśli n - 1 krążków wymaga 2^(n-1) - 1 ruchów, to n krążków wymaga dwa razy tyle i jeszcze jednego ruchu: 2(2^(n-1) - 1) + 1 = 2^n - 1. Tak wyprowadza wzór magazyn Plus Uniwersytetu Cambridge, a ciąg 1, 3, 7, 15 opisuje hasło A000225 w encyklopedii ciągów OEIS.

W najkrótszym rozwiązaniu krążek o numerze k rusza się 2^(n-k) razy. Przy pięciu krążkach daje to kolejno 16, 8, 4, 2, 1 ruchów, od najmniejszego do największego krążka. Numery krążków w kolejnych ruchach tworzą ciąg 1, 2, 1, 3, 1, 2, 1, 4 i tak dalej. Krążek w ruchu m ma numer o jeden większy od liczby zer na końcu m w zapisie dwójkowym. Ten związek opisuje w encyklopedii OEIS komentarz Andreasa M. Hinza do ciągu A001511.

Liczba ruchów rośnie wykładniczo, bo każdy krążek ją podwaja. To złożoność wykładnicza: 10 krążków to już 1023 ruchy, a wieża z legendy Lucasa, z 64 krążków, wymaga liczby o 20 cyfrach.

Krążki na trzech słupkach mogą stać na 3^n sposobów, bo każdy krążek wybiera jeden z trzech słupków, a kolejność na słupku wyznaczają zasady. Dla pięciu krążków to 243 ustawienia. Graf, w którym każde ustawienie jest punktem, a każdy ruch odcinkiem, z każdym krążkiem coraz bardziej przypomina trójkąt Sierpińskiego; piszą o tym magazyn Plus oraz książka Andreasa M. Hinza, Sandiego Klavžara i Cirila Petra.

Opcja „Losowa pozycja” rozkłada krążki po słupkach losowo, a każde ułożenie jest równie prawdopodobne. Jedynym wyjątkiem jest największy krążek, który nigdy nie zaczyna na słupku docelowym, więc zawsze musi się ruszyć. Pozycja powstaje dopiero po stuknięciu przycisku „Wylosuj pozycję” i zapisuje się w linku, więc ktoś, kto go otworzy, dostaje ten sam start.

Przycisk „Podpowiedź” pokazuje następny ruch jednej z najkrótszych dróg do celu z bieżącego ustawienia. Podświetla oba słupki i pisze na przykład „Podpowiedź: przenieś krążek 2 z A na C.”. Każda podpowiedź jest liczona, a cofnięcie ruchu jest możliwe bez limitu i trafia do licznika cofniętych ruchów.

Przycisk „Rozwiąż” kończy układanie z bieżącego miejsca w wybranym tempie: od 0,9 s między ruchami przy tempie wolnym do około 0,045 s przy bardzo szybkim. Automatyczne rozwiązywanie można wstrzymać, wykonać nim jeden ruch albo przejąć grę i układać dalej samodzielnie. Gdy gra zaczęta od wieży idzie zgodnie z listą ruchów, automat tę listę kontynuuje.

Gdy wybrane są cztery słupki, gra przyjmuje do 8 krążków, bo podpowiedzi przeszukują wtedy wszystkie 4^n ustawień. Lista ruchów pokazuje rozwiązanie Frame'a i Stewarta, choć istnieją też inne rozwiązania tej samej długości.

Łamigłówkę wydał w 1883 roku francuski matematyk Édouard Lucas jako „la Tour d'Hanoï, véritable casse-tête annamite”, czyli prawdziwą łamigłówkę annamską. Według napisu na pudełku grę przywiózł z Tonkinu „profesor N. Claus (de Siam), mandaryn kolegium Li-Sou-Stian”. Opis z „Journal des Débats” z 27 grudnia 1883 roku cytują R. E. Allardice i A. Y. Fraser.

Obie nazwy to żart. Serwis MacTutor Uniwersytetu St Andrews wyjaśnia, że N. Claus de Siam to anagram „Lucas d'Amiens”, a Li-Sou-Stian to anagram Saint Louis, czyli liceum, w którym Lucas wtedy uczył.

Z grą przyszła legenda. W wielkiej świątyni w Benaresie w Indiach kapłani, bramini, przekładają wieżę z 64 krążków z czystego złota między trzema diamentowymi igłami, po jednym krążku i nigdy większy na mniejszy. Gdy skończą, wieża i bramini runą i nastąpi koniec świata. Lucas opowiada ją w „Récréations mathématiques” z 1893 roku.

Ta legenda to wymysł samego Lucasa. Napisał, że gry nie przywieziono z Tonkinu, „cokolwiek mówi ulotka”, a grę i legendę wymyślono pod numerem 56 przy rue Monge w Paryżu. Nie jest to więc dawna opowieść tybetańska, buddyjska ani wietnamska, a w tekście Lucasa nie ma mnichów ani świątyni w Hanoi. Henri de Parville powtórzył legendę w „La Nature” w 1884 roku, co odnotował W. W. Rouse Ball w „Mathematical Recreations and Essays” z 1914 roku.

Wieża braminów wymaga 18 446 744 073 709 551 615 ruchów, liczby o 20 cyfrach, którą Lucas wypisuje w całości. Ten sam autor opisał też grę na kartce w kratkę, znaną w Polsce jako szewc, czyli kropki i kwadraty.

Psycholodzy używają zadań z wieżami do badania planowania i rozwiązywania problemów, bo w kolejnych ruchach widać, jak ktoś myśli kilka kroków naprzód. Magazyn Plus Uniwersytetu Cambridge ujmuje to tak, że przy takim zadaniu można obserwować, jak ludzie myślą.

Tim Shallice opisał w 1982 roku zadanie do badania zaburzeń planowania. Wieża londyńska to według zespołu z Uniwersytetu Erazma w Rotterdamie (Koppenol-Gonzalez, Bouwmeester i Boonstra, 2010) szeroko stosowane narzędzie do pomiaru umiejętności planowania. Jeremy R. Sullivan, Cynthia A. Riccio i Candace L. Castillo w metaanalizie z 2009 roku oceniali zadania z wieżami jako miary funkcji wykonawczych u dorosłych. Funkcje wykonawcze i planowanie to dwa pojęcia, w których te badania opisują wyniki zadań z wieżami.

Ta gra jest łamigłówką. Liczy ruchy, czas i podpowiedzi, ale jej wynik nie ma znaczenia klinicznego i nie mierzy inteligencji, uwagi ani żadnej innej cechy. Inne znane zadanie z psychologii poznawczej, z kolorami i słowami, można wypróbować w teście Stroopa.