Wieża Hanoi: zasady, rozwiązanie i kod w Pythonie i C++

Wieża Hanoi to łamigłówka z trzema słupkami i stosem krążków, którą da się rozwiązać w 2ⁿ − 1 ruchach i nie szybciej. Przepis na to rozwiązanie mieści się w trzech linijkach kodu. Dla 3 krążków wystarczy 7 ruchów, dla 10 trzeba ich 1023, a każdy kolejny krążek podwaja tę liczbę i dodaje jeden. Dlatego wieża Hanoi jest na lekcjach informatyki klasycznym przykładem rekurencji, czyli funkcji, która rozwiązuje zadanie, wywołując samą siebie dla mniejszego zadania. Kod w Pythonie i C++ z tego tekstu uruchomiliśmy 28 października 2026 roku, a wyniki wklejamy bez poprawek.

Wieża Hanoi: zasady gry

Celem jest przeniesienie wszystkich krążków z jednego słupka na drugi. W jednym ruchu przenosisz tylko jeden krążek i nigdy nie kładziesz większego na mniejszym. Zintegrowana Platforma Edukacyjna (ZPE) w lekcji o zagadce Wież Hanoi wymienia te warunki:

1. Krążki mają różne średnice.
2. Na początku wszystkie krążki leżą na jednym słupku, od największego na dole do najmniejszego na górze.
3. W jednym ruchu przenosisz tylko jeden krążek.
4. Nie wolno położyć większego krążka na mniejszym.
5. Do dyspozycji jest dodatkowy słupek pomocniczy.

W tym tekście słupki nazywamy A (start), B (pomocniczy) i C (cel), a krążki numerujemy od najmniejszego: krążek 1 jest najmniejszy. Zadanie jest rozwiązane, gdy cała wieża stoi na słupku C w tej samej kolejności.

Jak rozwiązać wieżę Hanoi krok po kroku

Wieżę z 3 krążków przenosisz z A na C w 7 ruchach. Najpierw dwa mniejsze krążki trafiają na B, potem największy na C, a na końcu dwa mniejsze przechodzą z B na C. Tak wygląda pełna kolejność ruchów, wygenerowana przez kod z dalszej części tekstu:

Spójrz na ruch 4: największy krążek przechodzi z A na C dokładnie w połowie rozwiązania. Ruchy 1–3 przenoszą wieżę z dwóch krążków z A na B, a ruchy 5–7 przenoszą ją z B na C. Na tym spostrzeżeniu opiera się cały algorytm.

Dla 4 krążków potrzeba 15 ruchów. Najmniejszy krążek rusza wtedy najpierw na B, a nie na C, bo liczba krążków jest parzysta:

Przy układaniu z ręki pomaga jedna obserwacja: co drugi ruch (pierwszy, trzeci, piąty i tak dalej) wykonuje najmniejszy krążek, i zawsze w tym samym kierunku. Opisujemy ją dokładnie w części o rozwiązaniu bez rekurencji.

Frontend Master 2026 · Kodożercy

Pisz kod, nie tylko prompty

Frontend Master 2026 to pakiet sześciu kursów Kodożerców (HTML, CSS, JavaScript, Git) w polskim wideo z 12-miesięcznym dostępem. Fundamenty frontu od pierwszej linijki kodu do deploy.

Wchodzę w to →

Ile ruchów potrzeba: wzór 2ⁿ − 1

Minimalna liczba ruchów dla n krążków wynosi 2ⁿ − 1. ZPE podaje ten sam wzór i przykład: dla trzech krążków 2³ − 1 = 8 − 1 = 7. Wzór wynika z obserwacji z poprzedniej sekcji. Żeby przenieść n krążków, trzeba przenieść n − 1 krążków na słupek pomocniczy, potem największy krążek, a potem znowu n − 1 krążków na niego. Liczba ruchów spełnia więc zależność L(n) = 2 · L(n − 1) + 1, przy L(1) = 1. Po rozwinięciu daje to 2ⁿ − 1.

Szybciej się nie da, a dowód jest krótki. Największy krążek można ruszyć tylko wtedy, gdy wszystkie mniejsze leżą na jednym słupku, a drugi słupek jest wolny. To wymaga przeniesienia n − 1 krążków, czyli co najmniej L(n − 1) ruchów. Potem trzeba je przenieść jeszcze raz, na największy krążek, czyli znowu co najmniej L(n − 1) ruchów. Takie rozumowanie przedstawia polska Wikipedia w haśle o wieżach Hanoi.

Według legendy dołączonej do zestawu sprzedawanego w XIX wieku mnisi w świątyni Brahmy przekładają 64 złote krążki, a gdy skończą, nastąpi koniec świata. Policzyliśmy to w Pythonie: 2⁶⁴ − 1 = 18 446 744 073 709 551 615 ruchów. Przy jednym ruchu na sekundę i roku liczącym 365,25 dnia (31 557 600 sekund) daje to około 584,5 mld lat. Wikipedia podaje około 584,6 mld lat. Niewielka różnica wynika z przyjętej długości roku albo z zaokrąglenia.

Algorytm rekurencyjny: pseudokod i kod w Pythonie

Algorytm rekurencyjny przenosi n − 1 krążków na słupek pomocniczy, potem największy krążek na cel, a potem n − 1 krążków ze słupka pomocniczego na cel. Pseudokod w lekcji ZPE wygląda tak:

funkcja wiezaHanoi(n, A, B, C)
    jeżeli n > 0 wykonaj:
        wiezaHanoi(n - 1, A, C, B)
        wypisz: "Przeniesienie z " A " do " C
        wiezaHanoi(n - 1, B, A, C)

Warunek n > 0 odcina przypadek bazowy: dla zera krążków funkcja nic nie robi i od razu wraca. Bez niego funkcja wywoływałaby samą siebie bez końca. Szerzej o tym, jak działa rekurencja i kiedy się ją stosuje, piszemy w tekście o algorytmach rekurencyjnych.

Kod w Pythonie

Ten sam algorytm w Pythonie. Funkcja dodatkowo zlicza ruchy, żeby wynik dało się porównać ze wzorem:

def hanoi(n, skad, pomocniczy, dokad):
    """Przenosi n krążków ze słupka skad na słupek dokad."""
    if n == 0:
        return 0
    ruchy = hanoi(n - 1, skad, dokad, pomocniczy)
    print(f"Krążek {n}: {skad} -> {dokad}")
    ruchy += 1
    ruchy += hanoi(n - 1, pomocniczy, skad, dokad)
    return ruchy


liczba = hanoi(3, "A", "B", "C")
print("Liczba ruchów:", liczba)

Wynik w konsoli (Python 3.14.3):

Krążek 1: A -> C
Krążek 2: A -> B
Krążek 1: C -> B
Krążek 3: A -> C
Krążek 1: B -> A
Krążek 2: B -> C
Krążek 1: A -> C
Liczba ruchów: 7

Drzewo wywołań i złożoność

Kolejność jest identyczna jak w tabeli na początku tekstu. Na drzewie wywołań widać, skąd się bierze: każde wywołanie dla n krążków rozdziela się na dwa wywołania dla n − 1 i jeden ruch pośrodku.

Wersja rekurencyjna ma złożoność czasową O(2ⁿ), bo wykonuje 2ⁿ − 1 ruchów. ZPE nazywa to złożonością wykładniczą, czyli taką, która rośnie bardzo szybko razem z liczbą krążków. Pamięci potrzeba niewiele: w danej chwili na stosie wywołań leży najwyżej n + 1 wywołań, od hanoi(n) do hanoi(0). Domyślny limit głębokości rekurencji w Pythonie (sys.getrecursionlimit()) wynosi 1000. Wieża z kilkudziesięciu krążków go nie wyczerpie. Wcześniej skończy się cierpliwość, bo już 30 krążków to ponad miliard ruchów. Porównanie złożoności różnych algorytmów znajdziesz w tekście o sortowaniu, wyszukiwaniu i złożoności.

Wieża Hanoi w C++

W C++ algorytm wygląda tak samo, zmienia się tylko składnia. Typ long long w liczniku ruchów wystarcza do wież z 63 krążkami. Napisy w konsoli zostawiamy bez polskich znaków, bo ich wyświetlanie zależy od ustawień konsoli w systemie.

#include <iostream>

// Przenosi n krążków ze słupka skad na słupek dokad, zwraca liczbę ruchów
long long hanoi(int n, char skad, char pomocniczy, char dokad) {
    if (n == 0) {
        return 0;
    }
    long long ruchy = hanoi(n - 1, skad, dokad, pomocniczy);
    std::cout << "Krazek " << n << ": " << skad << " -> " << dokad << '\n';
    ruchy += 1;
    ruchy += hanoi(n - 1, pomocniczy, skad, dokad);
    return ruchy;
}

int main() {
    long long liczba = hanoi(3, 'A', 'B', 'C');
    std::cout << "Liczba ruchow: " << liczba << '\n';
    return 0;
}

Wynik po kompilacji (Microsoft C/C++ 19.29, cl /EHsc /W4 /std:c++17 hanoi.cpp, bez ostrzeżeń):

Krazek 1: A -> C
Krazek 2: A -> B
Krazek 1: C -> B
Krazek 3: A -> C
Krazek 1: B -> A
Krazek 2: B -> C
Krazek 1: A -> C
Liczba ruchow: 7

Kod nie używa niczego spoza standardowej biblioteki, więc skompiluje się też w g++ albo clang (g++ -std=c++17 hanoi.cpp). Tego nie sprawdzaliśmy, bo na komputerze testowym był tylko kompilator Microsoftu. Ten sam układ funkcji pokazujemy w C++ przy algorytmie Euklidesa, jeśli chcesz porównać dwie rekurencje obok siebie.

Rozwiązanie iteracyjne bez rekurencji

Wieżę Hanoi da się rozwiązać zwykłą pętlą, bez rekurencji, jeśli zapamiętasz jedną regułę o najmniejszym krążku. Według ZPE wygląda ona tak.

Reguła najmniejszego krążka

1. Przenieś najmniejszy krążek na kolejny słupek. Przy parzystej liczbie krążków kolejny jest słupek po prawej (z A na B, z C na A). Przy nieparzystej liczbie krążków kolejny jest słupek po lewej (z A na C).
2. Innym krążkiem wykonaj jedyny dostępny ruch, czyli taki, w którym nie kładziesz większego krążka na mniejszy.
3. Powtarzaj oba kroki, aż wszystkie krążki znajdą się na słupku C.

Dla 3 krążków (liczba nieparzysta) najmniejszy krążek wędruje więc w kółko A → C → B → A. Dla 4 krążków krąży w drugą stronę: A → B → C → A.

Kod iteracyjny w Pythonie

W kodzie trzymamy słupki jako listy, a wierzch słupka to ostatni element listy:

def hanoi_iteracyjnie(n):
    slupki = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    # parzyste n: najmniejszy krążek krąży A -> B -> C, nieparzyste: A -> C -> B
    cykl = ["A", "B", "C"] if n % 2 == 0 else ["A", "C", "B"]
    gdzie = 0  # indeks słupka z najmniejszym krążkiem w cyklu
    for numer in range(1, 2 ** n):
        if numer % 2 == 1:
            skad = cykl[gdzie]
            gdzie = (gdzie + 1) % 3
            dokad = cykl[gdzie]
        else:
            x, y = [s for s in "ABC" if s != cykl[gdzie]]
            # jedyny dozwolony ruch: mniejszy wierzchni krążek na drugi słupek
            if not slupki[y] or (slupki[x] and slupki[x][-1] < slupki[y][-1]):
                skad, dokad = x, y
            else:
                skad, dokad = y, x
        slupki[dokad].append(slupki[skad].pop())
        print(f"{numer}. {skad} -> {dokad}")
    return slupki


print(hanoi_iteracyjnie(3))

Wynik w konsoli (Python 3.14.3):

1. A -> C
2. A -> B
3. C -> B
4. A -> C
5. B -> A
6. B -> C
7. A -> C
{'A': [], 'B': [], 'C': [3, 2, 1]}

Sprawdziliśmy też, że dla każdej liczby krążków od 1 do 12 wersja iteracyjna daje dokładnie tę samą sekwencję ruchów co rekurencyjna. Iteracja nie przyspiesza rozwiązania, bo ruchów i tak jest 2ⁿ − 1. Program trzyma za to stan w trzech listach zamiast na stosie wywołań funkcji. Każda lista działa jak stos: dokładasz i zdejmujesz tylko z wierzchu. ZPE zwraca uwagę, że właśnie dlatego wieże Hanoi przypominają stos, czyli strukturę danych, z której korzystają procesory.

Jeśli wolisz rozpisać tę regułę jako diagram przed pisaniem kodu, zasady rysowania pętli i warunków opisujemy w tekście o schematach blokowych.

Skąd się wzięła wieża Hanoi: Lucas, 1883 i legenda

Łamigłówkę opisał w 1883 roku francuski matematyk Édouard Lucas. ZPE przypomina, że Lucas zajmował się też ciągiem Fibonacciego i sprawdzaniem, czy liczba jest pierwsza. Według polskiej Wikipedii sama zagadka powstała prawdopodobnie wcześniej w Azji Wschodniej, a Lucas sprowadził ją na Zachód. Do zestawu, który sprzedawał, dołączona była legenda o 64 złotych krążkach, opisana wyżej przy wzorze.

Łamigłówka nadal zajmuje matematyków. Wikipedia wspomina na przykład wersje z więcej niż trzema słupkami, dla których liczenie najkrótszego rozwiązania jest dużo trudniejsze.

FAQ

Ile ruchów potrzeba dla 4, 5 i 8 krążków?

Dla 4 krążków potrzeba 15 ruchów, dla 5 krążków 31 ruchów, a dla 8 krążków 255 ruchów. Każdy wynik to 2ⁿ − 1: 2⁴ − 1 = 15, 2⁵ − 1 = 31, 2⁸ − 1 = 255. Pełną tabelę do 64 krążków znajdziesz w sekcji o wzorze.

Czy da się rozwiązać wieżę Hanoi w mniej niż 2ⁿ − 1 ruchach?

Nie, przy trzech słupkach i standardowych zasadach 2ⁿ − 1 to minimum. Największego krążka nie ruszysz, dopóki pozostałe n − 1 krążków nie będzie stało razem na jednym słupku, a potem musisz je przenieść jeszcze raz. To daje co najmniej 2 · L(n − 1) + 1 ruchów.

Dlaczego przy parzystej liczbie krążków pierwszy ruch idzie na słupek B?

Dlatego, że przy parzystej liczbie krążków najmniejszy krążek krąży w kierunku A → B → C, a przy nieparzystej A → C → B. Jeśli przy 4 krążkach zaczniesz od A → C, zagadkę nadal da się rozwiązać, ale nie w 15 ruchach.

Jak zrobić wieżę Hanoi w Scratchu?

W Scratchu każdy słupek możesz zapisać jako osobną listę. Ruch to wtedy usunięcie ostatniego elementu jednej listy i dodanie go do drugiej, tak jak w kodzie iteracyjnym wyżej. Regułę najmniejszego krążka łatwiej tam zaprogramować niż rekurencję. Od czego zacząć pierwszą grę w Scratchu, pokazujemy w poradniku o grze w labirynt.

Podsumowanie

Wieża Hanoi to łamigłówka z trzema słupkami, w której przenosisz cały stos krążków z jednego słupka na drugi. Ruszasz jeden krążek naraz i nigdy nie kładziesz większego na mniejszym. Najkrótsze rozwiązanie ma 2ⁿ − 1 ruchów: 7 dla trzech krążków, 15 dla czterech, a dla 64 krążków ponad 18 trylionów, czyli około 584,5 mld lat przy ruchu na sekundę. Algorytm rekurencyjny przenosi n − 1 krążków na słupek pomocniczy, potem największy krążek, a potem znowu n − 1 krążków. W Pythonie i C++ mieści się w kilku linijkach. Wersja bez rekurencji opiera się na regule najmniejszego krążka, który co drugi ruch idzie na kolejny słupek w kierunku zależnym od parzystości n. Obie wersje dają tę samą sekwencję ruchów i ten sam czas działania O(2ⁿ).

Mateusz Wojdalski

Specjalista SEO i content marketingu w Devstock. Zajmuję się strategią treści, automatyzacją procesów marketingowych i wdrożeniami AI w codziennej pracy. Badam nowe narzędzia, adaptuję je do realnych zadań i piszę o tym, co faktycznie działa.