Der klassische Flussüberquerungs-Rätsel gelöst: Fuchs, Huhn, Getreide

Das „Smart Kit River Crossing Game“ ist eine digitale Version des klassischen Wolf-Ziege-Kohl (oder Fuchs-Huhn-Getreide) Logikrätsels – ein Constraint-Satisfaction-Problem, das mindestens bis ins 9. Jahrhundert Europa zurückreicht. Die Aufgabe: drei Gegenstände mit einem Boot über einen Fluss bringen, das nur ein Item plus Bediener fasst, ohne konfliktäre Paare allein zu lassen.

Die Lösungssequenz

Startzustand: Fuchs, Huhn, Getreide | Boot | (leeres jenseitiges Ufer)

1. Huhn rüberbringen. (Fuchs und Getreide sind sicher zusammen – Fuchs frisst kein Getreide)
2. Allein zurückkehren.
3. Fuchs rüberbringen.
4. Huhn ZURÜCK bringen. (Kritischer Schritt – Fuchs und Huhn dürfen nicht allein bleiben)
5. Getreide rüberbringen. (Fuchs und Getreide sind sicher)
6. Allein zurückkehren.
7. Huhn rüberbringen.

Endzustand: (leeres diesseitiges Ufer) | Boot | Fuchs, Huhn, Getreide

Warum das funktioniert: Constraint-Analyse

Verbotene Paare (unbeaufsichtigt): Fuchs+Huhn (Prädation), Huhn+Getreide (Verzehr).
Sichere Paare: Fuchs+Getreide (keine Interaktion).
Schlüsselerkenntnis: Das Huhn kollidiert mit BEIDEN anderen – es ist der „zentrale Knoten“ im Konfliktgraph. Daher muss das Huhn das Shuttle-Item sein: zuerst bewegt, zurückgebracht, zuletzt bewegt. Fuchs und Getreide interagieren nie direkt.

Verallgemeinerbarer Problemlösungsansatz

1. Constraints explizit modellieren – alle verbotenen Zustände listen.
2. Das am stärksten constrainte Element identifizieren – hier das Huhn.
3. Vom Ziel rückwärts arbeiten – letzter Zug muss das letzte Item bringen.
4. Zustandsraum-Suche nutzen – BFS/DFS findet optimale Lösung (Minimum 7 Züge).
5. Verifizieren, dass keine verbotenen Zustände auftreten – auch während Bootstransit.

Varianten und Erweiterungen

Missionare und Kannibalen (je 3, Boot fasst 2). Eifersüchtige Ehemänner (3 Paare, Boot fasst 2, keine Frau mit anderem Mann außer ihrem eigenen). Moderne Versionen fügen Zeitlimits, mehrere Boote, dynamische Constraints hinzu. Die Kernlogik bleibt: Constraint Satisfaction durch Zustandsraum-Suche.