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 264 −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 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) 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) krążków ze słupka B na słupek C posługując się słupkiem A

Przykładowe implementacje

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
#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;
}
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 krążków:

Dowód

Łatwo pokazać, że

  • w pierwszym kroku przekładamy 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 ruchów
  • przekładamy -ty krążek na drugi słupek – wymaga to jednego ruchu
  • przekładamy pozostałe krążki ze słupka 3. na -ty krążek leżący na 2. słupku – wymaga to co najmniej ruchów

a więc

Aby wykazać, że można przeprowadzić poniższe rozumowanie.

Aby móc ruszyć -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ć -ty krążek). A więc ze słupka 1 przekładamy krążki na słupek 3. Ponieważ aż do momentu gdy na drążku 1 pozostanie tylko -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 krążków (którego minimalna liczba ruchów wynosi ). Na przełożenie krążka -tego potrzeba co najmniej jeden ruch. Po jego przełożeniu znów potrzeba przełożyć krążki – jest to oczywiście znów sytuacja krążków (wymagająca co najmniej ruchów).

A więc

co w połączeniu z górnym ograniczeniem na daje równość

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:

Niech

Wtedy

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

Po powrocie do otrzymujemy

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ł.[1]

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

Zobacz też

Przypisy

  1. Wieże Hanoi (pol. • ang. • niem.). 1999-08-21. [dostęp 2020-01-08].

Linki zewnętrzne

Media użyte na tej stronie

Tower of Hanoi 4.gif
Autor:

André Karwath aka Aka

, Licencja: CC BY-SA 2.5
This animation shows the solution of the game "Tower of Hanoi" with four discs. There is also a version with three discs.
Trudne zadanie Hanoi.jpg
Autor: Zylla, Licencja: CC BY-SA 4.0
Sytuacja gdy zastajemy układ w trakcie układania na zadany stos i chcemy kontynuować układanie.
Tower of Hanoi.jpeg
Autor: unknown, Licencja: CC-BY-SA-3.0