Türme von Hanoi

Visualisierung

Was sind die Türme von Hanoi?

Die Türme von Hanoi sind ein klassisches mathematisches Rätsel und ein Paradebeispiel für rekursive Algorithmen in der Informatik. Das Puzzle wurde 1883 vom französischen Mathematiker Édouard Lucas erfunden.

Das Spiel besteht aus:

• 3 Stäben (Start, Hilfs- und Zielstab)
• n Scheiben unterschiedlicher Größe, die auf dem Startstab gestapelt sind (größte unten, kleinste oben) Ziel: Alle Scheiben vom Startstab auf den Zielstab versetzen – unter folgenden Regeln:

1. Pro Zug darf nur eine Scheibe bewegt werden.
2. Eine größere Scheibe darf niemals auf einer kleineren liegen.
3. Alle drei Stäbe dürfen als Zwischenlager genutzt werden.

Warum ist Hanoi wichtig für die Informatik?

Das Hanoi-Problem ist kein bloßes Spielzeug. Es veranschaulicht zentrale Konzepte:

Der Algorithmus

Grundidee

Um n Scheiben von Stab A nach Stab C zu bewegen (mit B als Hilfsstab):

1. Bewege die oberen n-1 Scheiben von A nach B (mit C als Hilfe).
2. Bewege die größte Scheibe von A nach C.
3. Bewege die n-1 Scheiben von B nach C (mit A als Hilfe).

Pseudocode

hanoi(n, start, ziel, hilf):
    wenn n == 1:
        bewege Scheibe 1 von start nach ziel
    sonst:
        hanoi(n-1, start, hilf, ziel)
        bewege Scheibe n von start nach ziel
        hanoi(n-1, hilf, ziel, start)

Haskell-Notation (funktional)

hanoi n start ziel hilf =
    if (n == 1)
        then move n start ziel
        else hanoi (n-1) start hilf ziel
             ++ move n start ziel
             ++ hanoi (n-1) hilf ziel start

Java-Implementierung

Minimale Version

public class Hanoi {
    public static void hanoi(int n, char start, char ziel, char hilf) {
        if (n == 1) {
            System.out.println("Scheibe 1: " + start + " → " + ziel);
            return;
        }
        hanoi(n - 1, start, hilf, ziel);
        System.out.println("Scheibe " + n + ": " + start + " → " + ziel);
        hanoi(n - 1, hilf, ziel, start);
    }
 
    public static void main(String[] args) {
        int n = 3;
        System.out.println("Türme von Hanoi mit " + n + " Scheiben:");
        hanoi(n, 'A', 'C', 'B');
    }
}

Ausgabe für n = 3:

Türme von Hanoi mit 3 Scheiben:
Scheibe 1: A → C
Scheibe 2: A → B
Scheibe 1: C → B
Scheibe 3: A → C
Scheibe 1: B → A
Scheibe 2: B → C
Scheibe 1: A → C

Erweiterung: Züge als Liste zurückgeben

import java.util.ArrayList;
import java.util.List;
 
public class HanoiListe {
 
    public record Zug(int scheibe, char von, char nach) {
        @Override
        public String toString() {
            return "Scheibe " + scheibe + ": " + von + " → " + nach;
        }
    }
 
    public static List<Zug> hanoi(int n, char start, char ziel, char hilf) {
        List<Zug> züge = new ArrayList<>();
        if (n == 1) {
            züge.add(new Zug(1, start, ziel));
            return züge;
        }
        züge.addAll(hanoi(n - 1, start, hilf, ziel));
        züge.add(new Zug(n, start, ziel));
        züge.addAll(hanoi(n - 1, hilf, ziel, start));
        return züge;
    }
 
    public static void main(String[] args) {
        int n = 4;
        List<Zug> züge = hanoi(n, 'A', 'C', 'B');
        System.out.println("Anzahl Züge: " + züge.size()); // 15
        züge.forEach(System.out::println);
    }
}

Rekursionsbaum

Für n = 3 entsteht folgender Rekursionsbaum (Aufrufe):

hanoi(3, A, C, B)
├── hanoi(2, A, B, C)
│   ├── hanoi(1, A, C, B)  →  Scheibe 1: A → C
│   ├── Scheibe 2: A → B
│   └── hanoi(1, C, B, A)  →  Scheibe 1: C → B
├── Scheibe 3: A → C
└── hanoi(2, B, C, A)
    ├── hanoi(1, B, A, C)  →  Scheibe 1: B → A
    ├── Scheibe 2: B → C
    └── hanoi(1, A, C, B)  →  Scheibe 1: A → C

Knoten im Baum: 2ⁿ⁺¹ − 1 = 7 Knoten (für n=3)
Anzahl Züge: 2ⁿ − 1 = 7 Züge (für n=3)

Komplexitätsanalyse

Zeitkomplexität

Für n Scheiben gilt die Rekurrenzrelation:

T(1) = 1
T(n) = 2 · T(n-1) + 1

Lösung: T(n) = 2ⁿ − 1

Legende: Das Hanoi-Problem mit 64 Scheiben würde – bei einem Zug pro Sekunde – über 580 Milliarden Jahre dauern.

Speicherkomplexität

Die Rekursionstiefe beträgt n, daher ist der Call-Stack-Verbrauch O(n).

Iterative Lösung

Das Hanoi-Problem lässt sich auch ohne Rekursion lösen – mit einer bitweisen Strategie:

public class HanoiIterativ {
    public static void hanoi(int n) {
        long züge = (1L << n) - 1; // 2^n - 1
        char[] stäbe = (n % 2 == 0)
            ? new char[]{'A', 'B', 'C'}
            : new char[]{'A', 'C', 'B'};
 
        for (long i = 1; i <= züge; i++) {
            int scheibe = Long.numberOfTrailingZeros(i) + 1;
            char von = stäbe[(int)((i / scheibe) % 3)];
            // Vereinfachte Darstellung – vollständige Implementierung
            // erfordert Zustandsverfolgung der Stäbe
            System.out.println("Zug " + i + ": Scheibe " + scheibe);
        }
    }
}

Hinweis: Die iterative Variante ist technisch korrekt, aber schwerer zu verstehen. Für Lernzwecke ist die rekursive Version vorzuziehen.

Versionen & Abhängigkeiten

Java

• Java Version: 21 (LTS)
• Empfehlung: Java 21 oder höher verwenden, um Records und moderne Sprachfeatures zu nutzen.

Keine externen Abhängigkeiten

Dieses Projekt benötigt keine Bibliotheken – nur Standard-Java. Ideal zum Einstieg in Rekursion und Algorithmen.

<properties>
    <maven.compiler.source>21</maven.compiler.source>
    <maven.compiler.target>21</maven.compiler.target>
</properties>

GitHub-Repository

Den vollständigen Code – inklusive interaktiver Simulation, Rekursionsbaum-Visualisierung und Schritt-für-Schritt-Player – findest Du auf GitHub:

GitHub-Repository

Fazit

Die Türme von Hanoi sind ein zeitloser Klassiker, der auf elegante Weise zeigt, wie Rekursion komplexe Probleme auf einfache Teilprobleme reduziert. Mit nur wenigen Zeilen Java-Code lässt sich ein Algorithmus implementieren, der mathematisch beweisbar optimal ist.

Wer Rekursion wirklich verstehen will, sollte Hanoi nicht überspringen – es ist das “Hello World” der algorithmischen Denkweise.