Wieża Hanoi: rozwiązanie, wzór 2^n - 1 i matematyka łamigłówki

Autor: Dawid Siedlarz · · 8 min czytania

Zagraj w Wieża Hanoi za darmo →

W skrócie: wieża Hanoi z n krążkami i trzema słupkami wymaga co najmniej 2n − 1 ruchów: 7 dla 3 krążków, 15 dla 4, 31 dla 5, 127 dla 7. Żeby ją rozwiązać, przenieś górne n − 1 krążków na wolny słupek, największy krążek na słupek docelowy, a potem n − 1 krążków na niego, czyli tę samą łamigłówkę, tylko mniejszą. Szybka reguła: najmniejszy krążek przesuwaj co drugi ruch, zawsze w tym samym kierunku, a pomiędzy wykonuj jedyny inny dozwolony ruch. Łamigłówkę wymyślił Édouard Lucas w 1883 roku.

Wieża Hanoi wygląda jak zabawka: trzy słupki i stos krążków zwężający się ku górze. Trzeba przenieść cały stos na inny słupek, po jednym krążku, nigdy nie kładąc większego na mniejszym. Z 3 krążkami zajmuje to minutę. Z 7 wymaga skupienia. Z 64 trwałoby dłużej, niż będzie świecić Słońce. Za tą prostą łamigłówką kryje się jeden z najczystszych przykładów rekurencji w matematyce, ukryty licznik binarny i fraktal. Najpierw rozwiązanie, potem matematyka.

Zasady

  1. Są trzy słupki. Na początku wszystkie krążki leżą na jednym, największy na dole.
  2. Przenosisz jeden krążek naraz: górny krążek z dowolnego słupka na inny słupek.
  3. Nie wolno położyć krążka na mniejszym.
  4. Łamigłówka jest rozwiązana, gdy cała wieża stoi w tym samym porządku na słupku docelowym.

W naszej grze Wieża Hanoi wieża zaczyna na lewym słupku i ma skończyć na prawym. Poziom łatwy ma 3 krążki, średni 5, a trudny 7. Nie ma limitu czasu, a gra pokazuje obok twojej liczby ruchów najmniejszą możliwą.

Rozwiązanie dla 3 krążków, ruch po ruchu

Nazwijmy słupki A (start, lewy), B (środkowy) i C (cel, prawy), a krążki 1 (mały), 2 (średni) i 3 (duży). Najkrótsze rozwiązanie ma 7 ruchów:

RuchKrążekSkąd → dokądPo ruchu (A | B | C)
11A → C3 2 | – | 1
22A → B3 | 2 | 1
31C → B3 | 2 1 | –
43A → C– | 2 1 | 3
51B → A1 | 2 | 3
62B → C1 | – | 3 2
71A → C– | – | 3 2 1

Spójrz na strukturę. Ruchy 1-3 przenoszą wieżę z dwóch krążków z A na B. Ruch 4 przenosi duży krążek. Ruchy 5-7 przenoszą dwukrążkową wieżę z B na niego. W tym tkwi cały sekret.

Dwa sposoby na dowolną wieżę

1. Metoda rekurencyjna (myśl wieżami)

Żeby przenieść wieżę z n krążków ze słupka startowego na docelowy:

  1. Przenieś górne n − 1 krążków ze startu na wolny słupek (słupek docelowy służy za pomocniczy).
  2. Przenieś największy krążek ze startu na cel.
  3. Przenieś n − 1 krążków z wolnego słupka na cel (start służy za pomocniczy).

Kroki 1 i 3 to ta sama łamigłówka z jednym krążkiem mniej, więc stosujesz do nich te same trzy kroki, i tak dalej, aż zostanie jeden krążek, który po prostu przenosisz. Dlatego wieża Hanoi jest pierwszym przykładem rekurencji na kursach programowania: funkcji, która rozwiązuje problem, wywołując samą siebie dla mniejszej wersji. To też najlepszy sposób, by zrozumieć dowolną pozycję: zapytaj, który największy krążek nie jest jeszcze na miejscu; wszystko nad nim musi trafić na trzeci słupek.

2. Metoda iteracyjna (bez planowania)

  1. W każdym nieparzystym ruchu (1., 3., 5....) przesuń najmniejszy krążek o jeden słupek, zawsze w tym samym kierunku. Przy nieparzystej liczbie krążków kierunek to A → C → B → A (start, cel, środek), przy parzystej A → B → C → A.
  2. W każdym parzystym ruchu wykonaj jedyny dozwolony ruch, który nie dotyczy najmniejszego krążka. Zawsze jest dokładnie jeden.

Trzymając się tych dwóch reguł, skończysz w minimalnej liczbie ruchów bez myślenia naprzód. Tak większość ludzi rozwiązuje 7 krążków. Metoda rekurencyjna uczy, dlaczego to działa.

Dlaczego minimum to 2n − 1

Niech T(n) oznacza najmniejszą liczbę ruchów dla n krążków. Największy krążek musi się ruszyć co najmniej raz. W chwili ruchu musi być sam na swoim słupku, a słupek docelowy musi być pusty, więc pozostałe n − 1 krążków musi leżeć na trzecim słupku: to zajęło co najmniej T(n − 1) ruchów. Potem te krążki muszą jeszcze trafić na niego: znowu co najmniej T(n − 1) ruchów. Zatem

T(n) = 2 × T(n − 1) + 1, przy T(1) = 1.

Daje to 1, 3, 7, 15, 31, 63, 127... i każda liczba jest o jeden mniejsza od potęgi dwójki: T(n) = 2n − 1. Metoda rekurencyjna osiąga dokładnie tę liczbę, więc jest optymalna, a najkrótsze rozwiązanie jest jedyne: istnieje tylko jeden sposób, by zrobić to w 2n − 1 ruchach.

Jak szybko to rośnie

KrążkiNajmniej ruchówPrzy jednym ruchu na sekundę
377 sekund
41515 sekund
531około pół minuty
663około minuty
7127około 2 minut
8255około 4 minut
101023około 17 minut
201 048 575około 12 dni
324 294 967 295około 136 lat
6418 446 744 073 709 551 615około 585 miliardów lat

Każdy dodatkowy krążek podwaja pracę. Tak wygląda wzrost wykładniczy i dlatego łamigłówka służy do jego wyjaśniania.

Ukryte wzory

Który krążek się rusza: licznik binarny

W najkrótszym rozwiązaniu krążek k (licząc od najmniejszego) rusza się dokładnie 2n−k razy. Najmniejszy wykonuje połowę wszystkich ruchów (w zaokrągleniu w górę), największy rusza się raz, dokładnie w połowie: po 3 ruchach przy 3 krążkach, po 15 przy 5, po 63 przy 7.

Jest jeszcze zgrabniejsza reguła. Zapisz numer ruchu w systemie dwójkowym i policz zera na końcu: ruch 1 to 1 (brak zer, krążek 1), ruch 2 to 10 (jedno zero, krążek 2), ruch 3 to 11 (krążek 1), ruch 4 to 100 (dwa zera, krążek 3). Rusza się zawsze krążek o numerze o jeden większym niż liczba końcowych zer. Rozwiązanie to więc dosłownie licznik binarny od 0 do 2n − 1, a z samego numeru ruchu wiadomo, który krążek przesunąć. Ten sam ciąg (1, 2, 1, 3, 1, 2, 1...) to kolejność zmian bitów w kodzie Graya, sposobie liczenia binarnie, w którym w każdym kroku zmienia się tylko jeden bit.

Fraktal: trójkąt Sierpińskiego

Każdy krążek może leżeć na dowolnym z trzech słupków, a kolejność na słupku jest wymuszona (największy na dole), więc dozwolonych pozycji jest dokładnie 3n: 27 dla 3 krążków, 2187 dla 7. Narysuj każdą pozycję jako punkt i połącz dwa punkty, gdy jeden dozwolony ruch prowadzi od jednej pozycji do drugiej. Powstanie trójkąt złożony z trzech mniejszych trójkątów, z których każdy składa się z trzech jeszcze mniejszych: odmiana trójkąta Sierpińskiego, nazwanego od polskiego matematyka Wacława Sierpińskiego. Trzy wierzchołki to pozycje z całą wieżą na jednym słupku, a najkrótsze rozwiązanie biegnie prosto wzdłuż jednego boku.

Nasze trzy poziomy to liczby pierwsze

Liczby postaci 2n − 1 nazywa się liczbami Mersenne'a. Niektóre z nich są pierwsze, i takie są minimalne liczby ruchów na wszystkich naszych poziomach: 7, 31 i 127. Ta ostatnia łączy się z twórcą łamigłówki: w 1876 roku Édouard Lucas udowodnił, że 2127 − 1, liczba 39-cyfrowa, jest pierwsza. Pozostała największą znaną liczbą pierwszą przez 75 lat, do 1951 roku, a test Lucasa-Lehmera, oparty na jego metodzie, do dziś służy do szukania rekordowych liczb pierwszych.

Cztery słupki: znacznie trudniejszy problem

Z czwartym słupkiem wieżę da się przenieść dużo szybciej, bo jest więcej miejsc do odkładania krążków. Wersję z czterema słupkami opublikował Henry Dudeney w The Canterbury Puzzles (1907) jako „The Reve's Puzzle”. W 1941 roku J. S. Frame i B. M. Stewart niezależnie podali metodę: przenieś część górnych krążków na jeden wolny słupek, korzystając z czterech słupków, resztę przenieś trzema pozostałymi, a potem pierwszą grupę z powrotem na wierzch. Najlepszy podział daje takie liczby ruchów:

Krążki3 słupki4 słupki (Frame-Stewart)
375
4159
53113
66317
712725
825533
10102349

Przez ponad 70 lat nikt nie umiał udowodnić, że to najlepsza możliwa metoda dla czterech słupków. Udowodnił to dopiero Thierry Bousch w 2014 roku. Dla pięciu i więcej słupków pytanie wciąż pozostaje otwarte, co jest zdumiewające jak na łamigłówkę sprzedawaną w 1883 roku jako zabawka.

Historia: Lucas, pseudonim i legenda

Łamigłówka ukazała się w Paryżu w 1883 roku jako dzieło „profesora N. Clausa de Siam” z „kolegium Li-Sou-Stian”. Oba to anagramy: N. Claus de Siam to Lucas d'Amiens, a Li-Sou-Stian to Saint Louis, czyli Liceum Saint-Louis, w którym Édouard Lucas uczył matematyki. Lucas (1842-1891) jest znany także z liczb Lucasa, kuzynek ciągu Fibonacciego, i z czterotomowego zbioru matematycznych rozrywek.

Do łamigłówki dołączona była legenda: w wielkiej świątyni kapłani przenoszą wieżę z 64 złotych krążków między trzema diamentowymi iglicami według tych samych dwóch zasad, a gdy skończą, nastąpi koniec świata. Jak pokazuje tabela wyżej, nawet przy jednym ruchu na sekundę i bez błędów potrzebowaliby około 585 miliardów lat, ponad 40 razy więcej niż wiek Wszechświata. Legenda, podobnie jak nazwa Hanoi, była częścią egzotycznego opakowania Lucasa, a nie starożytną tradycją.

Gdzie dziś używa się wieży Hanoi

  • Nauka programowania. To klasyczne ćwiczenie z rekurencji; opisana wyżej metoda w trzech krokach to funkcja na kilka linijek.
  • Nauka matematyki. Równania rekurencyjne, indukcja matematyczna, wzrost wykładniczy i system dwójkowy w jednej łamigłówce.
  • Psychologia. Zadania z wieżami służą do badania planowania i rozwiązywania problemów: na ile ruchów naprzód ktoś myśli. Odmiana zwana wieżą Londynu, zaproponowana przez Tima Shallice'a w 1982 roku, jest używana w badaniach neuropsychologicznych.
  • Kopie zapasowe. Schemat rotacji taśm „wieża Hanoi” korzysta z tego samego wzoru 1, 2, 1, 3, 1, 2, 1, żeby zdecydować, którą taśmę nadpisać, dzięki czemu kopie gęsto pokrywają ostatnie dni i coraz rzadziej starsze okresy.

Wskazówki do naszej gry

  • Zacznij od poziomu łatwego i rozwiązuj 3 krążki metodą iteracyjną, aż wejdzie w nawyk, potem przejdź na metodę rekurencyjną przy 5 krążkach.
  • Przy nieparzystej liczbie krążków (wszystkie nasze poziomy: 3, 5, 7) pierwszy ruch to najmniejszy krążek na prawy słupek.
  • Sprawdź półmetek: gdy rusza się największy krążek, wszystkie pozostałe muszą leżeć na środkowym słupku.
  • Nigdy nie przesuwaj najmniejszego krążka dwa razy z rzędu; to zawsze zmarnowany ruch.
  • Wynik to 1000 × najmniejsza liczba ruchów ÷ twoja liczba ruchów, razy 1, 2 albo 4 zależnie od poziomu, więc idealne 7 krążków daje 4000 punktów. Cofnięcie ruchu liczy się jako ruch.

Jeśli lubisz łamigłówki, w których opłaca się planować kilka ruchów naprzód, spróbuj też Przesuwania skrzyń (odmiana Sokobana) i Przesuwanki.

Najczęściej zadawane pytania

Ile ruchów potrzeba do rozwiązania wieży Hanoi?

Przy n krążkach i trzech słupkach minimum to 2 do potęgi n minus 1: 7 ruchów dla 3 krążków, 15 dla 4, 31 dla 5, 63 dla 6 i 127 dla 7. Każdy kolejny krążek podwaja liczbę ruchów i dodaje jeden.

Jak rozwiązać wieżę Hanoi z 3 krążkami?

Ze słupkami A (start), B (środek) i C (cel): mały krążek z A na C, średni z A na B, mały z C na B, duży z A na C, mały z B na A, średni z B na C i mały z A na C. To 7 ruchów, czyli minimum.

Jaki jest trik na wieżę Hanoi?

W każdym nieparzystym ruchu przesuń najmniejszy krążek o jeden słupek, zawsze w tym samym kierunku (najpierw w stronę słupka docelowego przy nieparzystej liczbie krążków, w stronę środkowego przy parzystej). W każdym parzystym ruchu wykonaj jedyny dozwolony ruch, który nie dotyczy najmniejszego krążka.

Ile trwałoby przeniesienie 64 krążków?

2 do potęgi 64 minus 1, czyli 18 446 744 073 709 551 615 ruchów. Przy jednym ruchu na sekundę i bez żadnego błędu to około 585 miliardów lat, mniej więcej 40 razy więcej niż obecny wiek Wszechświata.

Kto wymyślił wieżę Hanoi?

Francuski matematyk Édouard Lucas, który w 1883 roku wydał ją pod pseudonimem N. Claus de Siam, będącym anagramem Lucas d'Amiens. Dołączył do niej legendę o kapłanach przenoszących 64 złote krążki, po czym miał nastąpić koniec świata.