Flussüberquerung

„River Crossing“ ist eine Reihe klassischer Logikrätsel, bei denen der Spieler eine Gruppe von Figuren oder Gegenständen mit einem Boot begrenzter Kapazität unter Einhaltung bestimmter Einschränkungen über einen Fluss befördern muss. Bestimmte Kombinationen von Passagieren dürfen an keinem der beiden Ufer allein gelassen werden – beispielsweise würde ein Wolf eine Ziege fressen oder eine Ziege den Kohl. Der Spieler muss eine Abfolge von Bootsfahrten finden, mit der alle sicher auf die andere Seite gebracht werden können, ohne dass dabei gegen eine der Einschränkungen verstoßen wird.

Regeln (Klassische Aufgabe mit Wolf, Ziege und Kohlkopf)

1. Ein Bauer muss einen Wolf, eine Ziege und einen Kohlkopf über einen Fluss transportieren.
2. Das Boot kann jeweils nur den Bauern und einen weiteren Gegenstand aufnehmen.
3. Der Bauer muss bei jeder Überfahrt im Boot sitzen (das Boot kann nicht von selbst über den Fluss fahren).
4. Der Wolf und die Ziege dürfen nicht allein zusammen gelassen werden (der Wolf würde die Ziege fressen).
5. Die Ziege und der Kohlkopf dürfen nicht allein zusammen gelassen werden (die Ziege würde den Kohlkopf fressen).
6. Der Wolf und der Kohlkopf können gefahrlos allein gelassen werden.
7. Das Ziel ist es, alle vier (Bauer, Wolf, Ziege, Kohlkopf) auf die andere Seite zu bringen.

Lösung (Klassisches Rätsel)

1. Der Bauer bringt die Ziege über den Fluss.
2. Der Bauer kehrt allein zurück.
3. Der Bauer bringt den Wolf hinüber.
4. Der Bauer bringt die Ziege zurück.
5. Der Bauer bringt den Kohlkopf hinüber.
6. Der Bauer kehrt allein zurück.
7. Der Bauer bringt die Ziege hinüber.

Insgesamt: 7 Überfahrten.

Gängige Varianten

• Missionare und Kannibalen: 3 Missionare und 3 Kannibalen müssen übergesetzt werden; an keinem Ufer dürfen die Kannibalen die Missionare zahlenmäßig übertreffen.
• Eifersüchtige Ehemänner: 3 Paare müssen übergesetzt werden; keine Frau darf sich mit einem anderen Mann am selben Ufer aufhalten, es sei denn, ihr Ehemann ist ebenfalls anwesend.
• Brücke und Taschenlampe: 4 Personen überqueren nachts mit einer Taschenlampe eine Brücke; es können immer nur zwei gleichzeitig überqueren; jede Person läuft mit einer anderen Geschwindigkeit; das Paar bewegt sich im Tempo der langsameren Person.
• Größere Gruppen: Erweiterte Versionen mit mehr Figuren und komplexeren Einschränkungsgraphen.

Strategien

• Die entscheidende Einschränkung identifizieren: Finde heraus, welche Figur oder welcher Gegenstand die meisten Konflikte verursacht. Im klassischen Rätsel steht die Ziege sowohl im Konflikt mit dem Wolf als auch mit dem Kohlkopf, was sie zum Schlüsselelement macht, das es zu bewältigen gilt.
• Die Shuttle-Technik: Manchmal muss man einen Gegenstand zur Startseite zurückbringen, um einen Konflikt zu lösen. Dieser kontraintuitive „Rückwärtsschritt“ ist oft der entscheidende Ansatz.
• In Zuständen denken: Stelle jede mögliche Konfiguration der Gegenstände auf beiden Ufern als „Zustand“ dar. Das Rätsel besteht nun darin, einen Weg durch gültige Zustände vom Start zum Ziel zu finden.
• Kreuzungen minimieren: Die optimale Lösung erfordert so wenige Kreuzungen wie möglich. Beim klassischen Rätsel sind 7 Kreuzungen optimal.
• Konfliktgraph: Zeichne einen Graphen, der zeigt, welche Gegenstände miteinander in Konflikt stehen. Der Gegenstand mit den meisten Konflikten erfordert in der Regel die größte Sorgfalt – oft muss er als Erster transportiert werden und muss möglicherweise zurückgebracht werden.
• Rückwärts vorgehen: Manchmal hilft es, sich vorzustellen, wie die letzten paar Überquerungen aussehen müssen, und rückwärts zu arbeiten, um frühere Züge zu bestimmen.

Rätsel zum Überqueren eines Flusses gehören zu den ältesten bekannten Logikrätseln; die früheste überlieferte Version findet sich in der mittelalterlichen Handschrift „Propositiones ad Acuendos Juvenes“ (Aufgaben zur Schärfung des Verstandes der Jugend), die Alkuin von York um 800 n. Chr. zugeschrieben wird. Alcuin war ein englischer Gelehrter und Berater von Kaiser Karl dem Großen, und seine Sammlung umfasste neben dem Wolf-Ziege-Kohl-Problem auch mehrere andere mathematische Rätsel. Damit sind Flussüberquerungsrätsel über 1.200 Jahre alt.

Die Variante „Missionare und Kannibalen“ entstand im 19. Jahrhundert und wurde im 20. Jahrhundert zu einem Standardproblem in der Forschung zur Künstlichen Intelligenz. Es war eines der ersten Probleme, das zur Veranschaulichung von Algorithmen zur Zustandsraum-Suche herangezogen wurde. Im Jahr 1968 nutzte Amarel es als Fallstudie für die Problemdarstellung in der KI und zeigte, wie die Wahl der Darstellung den Schwierigkeitsgrad bei der Lösungsfindung dramatisch beeinflusst. Seitdem taucht das Problem in unzähligen KI-Lehrbüchern auf.

Das „Brücke-und-Fackel“-Problem erlangte große Bekanntheit, als es Ende der 1990er- und in den 2000er-Jahren zu einer beliebten Interviewfrage bei Technologieunternehmen wurde, insbesondere bei Microsoft. Es fordert Bewerber heraus, die Gesamtüberquerungszeit zu optimieren, wenn die Personen unterschiedliche Geschwindigkeiten haben – eine grundlegend andere Herausforderung als die klassische Flussüberquerung, bei der es um die Erfüllung von Nebenbedingungen geht.

Rätsel zum Thema „Flussüberquerung“ haben sich seit über einem Jahrtausend gehalten, weil sie grundlegende Fähigkeiten zur Problemlösung vermitteln: das Aufteilen einer komplexen Situation in einzelne Zustände, das Erkennen von Einschränkungen, das In-Betracht-Ziehen kontraintuitiver Schritte (etwas zurückbringen) und das systematische Ausloten von Möglichkeiten. Sie tauchen weltweit in Büchern zur Freizeitmathematik, in Informatik-Lehrplänen und in Rätselsammlungen auf. Ihr erzählerischer Rahmen – ein Bauer, ein Fluss, hungrige Tiere – macht abstrakte Logik greifbar und einprägsam.