Jak grać w Wieże Hanoi

Wieże Hanoi to jedna z najstarszych i najbardziej eleganckich łamigłówek w matematyce. Zaczynasz z trzema słupkami i schludnym stosem krążków na skrajnie lewym słupku — każdy krążek mniejszy od tego pod nim, tworząc zgrabną piramidę. Wyzwanie wygląda na trywialne, a okazuje się prawdziwym sprawdzianem planowania.

Cel

Przenieś cały stos z lewego słupka na prawy, odbudowany w tej samej kolejności, z najmniejszym na górze. Środkowy słupek jest do twojej dyspozycji jako tymczasowe miejsce odkładania po drodze.

Zasady

• Przenoś tylko jeden krążek naraz — zawsze górny krążek słupka.
• Większy krążek nigdy nie może spoczywać na mniejszym. Ta jedna zasada czyni łamigłówkę interesującą.

Sterowanie

Dotknij lub kliknij słupek, aby podnieść jego górny krążek; krążek unosi się i czeka. Dotknij drugiego słupka, aby go tam położyć, albo dotknij tego samego słupka ponownie, aby anulować i odłożyć go z powrotem. Na klawiaturze naciśnij 1, 2 lub 3 dla lewego, środkowego i prawego słupka. Możesz wybrać, iloma krążkami grać, od szybkich 3 aż po wymagające 8 — użyj przycisku liczby krążków, aby zmienić poziom trudności.

Strategia

Za doskonałym rozwiązaniem kryje się piękna rekurencyjna sztuczka. Aby przenieść stos N krążków na słupek docelowy, najpierw przenieś górne N−1 krążków na słupek zapasowy, potem przesuń największy krążek na słupek docelowy, a następnie przenieś ten stos N−1 na jego wierzch. Działa też prostszy rytm: zawsze przenoś najmniejszy krążek co drugą turę, cyklicznie w jednym stałym kierunku, a w turach pomiędzy wykonuj jedyny inny dostępny legalny ruch.

Matematyka

Najmniejsza liczba ruchów potrzebnych dla N krążków to dokładnie 2ᴺ − 1. Tak więc 3 krążki rozwiązuje się w 7 ruchach, 5 krążków w 31, 7 w 127, a pełny stos 8 zajmuje 255 doskonałych ruchów. Spróbuj dorównać optymalnej liczbie, gdy już opanujesz wzór.