Wieże Hanoi

Rozwiązanie łamigłówki dla czterech krążków

Wieże Hanoi – problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach (popularna układanka), przy czym podczas przekładania wolno się posługiwać buforem (reprezentowanym w tym przypadku przez dodatkowy słupek), jednak przy ogólnym założeniu, że nie wolno kłaść krążka o większej średnicy na mniejszy ani przekładać kilku krążków jednocześnie. Jest to przykład zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania parametru wejściowego, tj. liczby elementów wieży.

Pochodzenie

Zagadka wież Hanoi powstała prawdopodobnie w Azji Wschodniej w XIX wieku lub wcześniej. Krążki były ceramiczne, produkowane w Chinach, Japonii i Wietnamie. Gra ta została sprowadzona na Zachód po raz pierwszy przez francuskiego matematyka Édouarda Lucasa w 1883 roku. Do sprzedawanego zestawu dołączona była tybetańska legenda, według której mnisi w świątyni Brahmy rozwiązują tę łamigłówkę dla 64 złotych krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata. Zakładając, że wykonują 1 ruch na sekundę, ułożenie wieży zajmie 2⁶⁴ −1 = 18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, czyli około 584,6 miliardów lat. Dla porównania: od Wielkiego Wybuchu minęło około 14 mld lat.

Algorytm

Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C

Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyjnego lub iteracyjnego.

• Oznaczmy kolejne słupki literami A, B i C.
• Niech $n$ będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C posługując się słupkiem B jako buforem.

Rozwiązanie rekurencyjne

Algorytm rekurencyjny składa się z następujących kroków:

1. przenieś (rekurencyjnie) $n-1$ krążków ze słupka A na słupek B posługując się słupkiem C,
2. przenieś jeden krążek ze słupka A na słupek C,
3. przenieś (rekurencyjnie) $n-1$ krążków ze słupka B na słupek C posługując się słupkiem A

Przykładowe implementacje

• w Pythonie:

def hanoi(n:int, A:list, B:list, C:list):
    """słupki A, B, C są listami"""
    if n > 0:
        hanoi(n-1, A, C, B)
        C.insert(0, A.pop(0))
        hanoi(n-1, B, A, C)

• w Elixirze:

defmodule Hanoi do
  # Jeśli brak krążków -> wszystko ok, nic nie trzeba robić
  def hanoi(0, _, _, _), do: :ok

  # Jeśli jeden krążek -> przełożyć na docelowy słupek
  def hanoi(1, a, _, c) do
    IO.puts "#{a}->#{c}"
  end

  # Więcej niż jeden -> rozwiąż rekurencyjnie
  def hanoi(n, a, b, c) do
    hanoi(n-1, a, c, b)
    hanoi(1, a, b, c)
    hanoi(n-1, b, a, c)
  end
end

• w C++:

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C)
{
  // przekłada n krążków z A korzystając z B na C
  if (n > 0)
  {
    hanoi(n-1, A, C, B);
    cout << A << " -> " << C << endl;
    hanoi(n-1, B, A, C);
  }
}

int main(int argc, char *argv[])
{
  hanoi(3, 'A', 'B', 'C');
  return 0;
}

• w C#:

using System;

namespace Hanoi
{
    public class WiezeHanoi
    {
        // przekłada n krążków z A, korzystając z B, na C
        static void Hanoi(int n, char A, char B, char C)
        {
            if(n > 0)
            {
                Hanoi(n - 1, A, C, B);
                Console.WriteLine("\t{0} -> {1}", A, C);
                Hanoi(n - 1, B, A, C);
            }
        }

        static void Main()
        {
            Console.WriteLine("Wieże Hanoi\n");
            Console.WriteLine("Algorytm przełożenia trzech krążków z wieży A na wieżę C z wykorzystaniem wieży B\n");
            Hanoi(3, 'A', 'B', 'C');
            Console.WriteLine("Naciśnij dowolny klawisz...");
            Console.ReadKey();
        }
    }
}

Algorytm rozwiązywania wież Hanoi jest klasycznym przykładem algorytmu rekurencyjnego używanego w nauczaniu informatyki.

Rozwiązanie iteracyjne

Algorytm iteracyjny składa się z następujących kroków:

1. przenieś najmniejszy krążek na kolejny (*) słupek,
2. wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego,
3. powtarzaj punkty 1 i 2, aż do odpowiedniego ułożenia wszystkich krążków.

(*) Kolejny słupek wyznaczamy w zależności od liczby krążków. Jeśli liczba krążków jest parzysta, kolejnym słupkiem jest ten po prawej stronie (gdy dojdziemy do słupka C w następnym ruchu używamy słupka A). Natomiast jeśli liczba krążków jest nieparzysta, kolejnym słupkiem jest ten po lewej stronie (gdy dojdziemy do słupka A w następnym ruchu używamy słupka C).

Najmniejsza liczba wymaganych ruchów

Równanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla $n$ krążków:

$L(n)=L(n-1)+1+L(n-1).$

Dowód

Łatwo pokazać, że $L(n)\leqslant L(n-1)+1+L(n-1){:}$

• w pierwszym kroku przekładamy $n-1$ krążków na jeden słupek (bez straty ogólności załóżmy, że jest to krążek nr 3) – wymaga to co najmniej $L(n-1)$ ruchów
• przekładamy $n$-ty krążek na drugi słupek – wymaga to jednego ruchu
• przekładamy pozostałe krążki ze słupka 3. na $n$-ty krążek leżący na 2. słupku – wymaga to co najmniej $L(n-1)$ ruchów

a więc $L(n)\leqslant L(n-1)+1+L(n-1).$

Aby wykazać, że $L(n)\geqslant L(n-1)+1+L(n-1),$ można przeprowadzić poniższe rozumowanie.

Aby móc ruszyć $n$-ty krążek, trzeba najpierw zdjąć wszystkie leżące na nim krążki, tak by po ich zdjęciu jeden ze słupków pozostał wolny (aby na jego „dno” mógł trafić $n$-ty krążek). A więc ze słupka 1 przekładamy krążki $1,2,\dots n-1$ na słupek 3. Ponieważ aż do momentu gdy na drążku 1 pozostanie tylko $n$-ty krążek nie ma znaczenia czy rzeczywiście się on tam znajduje, a więc do tego momentu sytuacja upraszcza się do rozwiązania problemu wież Hanoi dla $n-1$ krążków (którego minimalna liczba ruchów wynosi $L(n-1)$). Na przełożenie krążka $n$-tego potrzeba co najmniej jeden ruch. Po jego przełożeniu znów potrzeba przełożyć krążki $1,2,\dots n-1$ – jest to oczywiście znów sytuacja $n-1$ krążków (wymagająca co najmniej $L(n-1)$ ruchów).

A więc $L(n)\geqslant L(n-1)+1+L(n-1),$

co w połączeniu z górnym ograniczeniem na $L(n)$ daje równość

$L(n)=L(n-1)+1+L(n-1)=2\cdot L(n-1)+1.$

Postać jawna wzoru na liczbę ruchów

Powyższe równanie rekurencyjne można w łatwy sposób przekształcić do postaci jawnej, tj. nie korzystającej z rekursji:

$L(n)=2\cdot L(n-1)+1,$

$L(n)+1=2\cdot L(n-1)+1+1=2\cdot (L(n-1)+1).$

Niech $L'(n)=L(n)+1.$

Wtedy

$L'(n)=2\cdot L'(n-1)$

jest to równanie określające ciąg geometryczny o ilorazie równym 2 takie, że

${\begin{matrix}L(1)=1L'(1)=2L'(2)=4\\\vdots \\L'(n)=2^{n}\end{matrix}}$

Po powrocie do $L(n)$ otrzymujemy

$L(n)=2^{n}-1.$

Zastosowanie

Mimo swojego wieku łamigłówka jest stale tematem prac matematyków i znane są jej bardziej rozbudowane wersje np. z więcej niż trzema słupkami.

Hanoi przy dowolnym układzie krążków. Jaki jest pierwszy ruch?

Bardziej wymagająca myślenia wersja polega na znalezieniu najkrótszej drogi do ułożenia przypadkowo ułożonych krążków na wyznaczony stos. Takie zadanie przypomina sytuację mnicha, który kontynuuje układanie stosu w miejscu, w którym jego poprzednik przerwał.

W psychologii łamigłówka ta jest jednym z testów na kojarzenie.

Zobacz też

• kod Graya
• rekurencja
• stos

Linki zewnętrzne

• Gra Wieże Hanoi – online w trzech językach
• Eric W.E.W. Weisstein Eric W.E.W., Tower of Hanoi, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Grant Sanderson, Binary, Hanoi and Sierpinski, kanał 3blue1brown na YouTube, 25 listopada 2016 [dostęp 2021-03-15].