© Yuri Kravchenko, 123RF

Wie bringt ein Fährmann einen Wolf, eine Ziege und einen Kohlkopf mit einem Boot, das jeweils nur eine Fracht trägt, ans andere Ufer eines Flusses, ohne dass der Wolf die Ziege oder die Ziege den Kohlkopf frisst? Mike Schilli programmiert die Lösung in Go.

Ob es Missionare und Kannibalen sind, die einander nicht an den Kragen dürfen, während der Fährmann übersetzt, oder beim klassischen Flussüberquerungsrätsel [1] ein Wolf, eine Ziege und ein Kohlkopf: Die Lösung solcher Denksportaufgaben finden Kopfrechner durch Ausprobieren. Computer hingegen ermitteln sie mittels Bäumen von verketteten Zustandsfolgen und finden den gewünschten Endzustand schließlich irgendwann an einem der Äste [2].

Beim Überqueren des Flusses befinden sich anfänglich Fährmann, Wolf, Ziege und Kohlkopf am Westufer. Der Fährmann kann jeweils einen der drei mit ins Boot nehmen und ans Ostufer übersetzen. Während der Überfahrt muss er sicherstellen, dass er Wolf und Ziege nicht allein am Ufer zurücklässt, weil der Wolf die Ziege fressen würde. Das gleiche gilt für die Ziege und den Kohlkopf, über den sie sich hermachen würde.

Das Rätsel scheint auf den ersten Blick unlösbar. Hat der Fährmann die Ziege übergesetzt und schippert leer zurück, bleibt ihm nur die Wahl zwischen dem Wolf und dem Kohlkopf als nächstem Kandidaten. Von denen verträgt sich aber keiner am anderen Ufer mit der Ziege. Der Trick besteht nun darin, dass der Fährmann auf der Rückfahrt ebenfalls Passagiere befördert und so sicherstellt, dass er niemals eine gefährliche Kombination (Ziege/Kohlkopf beziehungsweise Wolf/Ziege) unbeaufsichtigt zurücklässt.

Fährenalgorithmus

Um die Angelegenheit mit einem Algorithmus zu knacken, muss dieser das Problem als Modell von Zuständen abbilden, die jeweils die Kandidaten entweder dem West- oder dem Ostufer zuweisen. Anfangs sitzen Fährmann, Wolf, Ziege und Kohlkopf alle am Westufer, das Ostufer ist leer. Im zweiten Zustand sitzt die Ziege am Ostufer, und am Westufer sitzen Wolf, Kohlkopf sowie der Fährmann, sobald er von seiner Rückreise angelegt hat.

Jeder Zustand bildet also die beiden Ufer ab, wobei jedes Ufer eine Reihe von Kandidaten beherbergt. Von einem gegebenen Zustand aus kann das System in einen oder mehrere Folgezustände wechseln, von denen manche illegal sind, weil zum Beispiel Wolf und Ziege unbeaufsichtigt am selben Ufer wären, und manche legal.

Ausgehend vom Anfangszustand probiert der Algorithmus der Reihe nach alle möglichen Folgezustände durch. Dabei ermittelt er, ob sie legal sind. Falls ja, sucht er ausgehend davon weitere Folgezustände. So setzt sich der Reigen fort. Findet sich das Programm irgendwann in einem Zustand wieder, bei dem auf einmal alle Kandidaten am Ostufer sitzen, ist das Rätsel gelöst. Das Programm gibt dann dem verblüfften Nutzer den Pfad des mitprotokollierten Suchlaufs als Lösungsschritte aus.

Tiefgang oder oberflächlich

Im Diagramm in Abbildung 1 startet das Programm im Zustand ganz oben, bei dem sich alle Teilnehmer (W = Wolf, G = Goat, C = Cabbage, F = Ferryman) im linken Teil des Rechtecks befinden, also am Westufer. Schreitet der Algorithmus dann nach links unten, findet er einen Zustand, bei dem Kohlkopf und Fährmann am rechten Ufer sitzen. Am linken Ufer befinden sich Wolf und Ziege – aber das ist nach den Regeln illegal, also sortiert der Algorithmus diesen Zustand aus (im Diagramm mit einem roten X) und fährt aus dieser Sackgasse naturgemäß auch keine Folgezustände an.

Beim Abfahren der Zustände in dieser Baumstruktur bieten sich zwei Verfahren an: Breadth-first (Breite zuerst) und Depth-first (Tiefe zuerst). Breadth-first fährt erst einmal alle direkten Folgezustände eines Zustands an, bevor es tiefer zu deren Nachfolgern vordringt. Depth-first dagegen bohrt so tief, wie es nur geht, und sucht Kinder und Kindeskinder auf, bevor es Brüdern auf gleicher Höhe einen Besuch abstattet.

Abbildung 1: Der Algorithmus wandert vom Ausgangszustand (oben) alle möglichen Folgezustände ab und sortiert illegale Zustände aus.

Im vorliegenden Flussüberquerungsrätsel geht es darum, eine Lösung mit möglichst wenigen Schritten zu ermitteln, also ist Breadth-first der richtige Ansatz, während Depth-first womöglich erst auf eine viel zu umständliche Lösung stoßen würde.

Damit steht das Rüstzeug für den Algorithmus fest, und die Programmierung kann beginnen. Der Übersichtlichkeit halber teilt sich der Code in mehrere Listings auf. Wer gleich losballern möchte, kompiliert und startet den Problemlöser mit der Kommandozeile in Listing 1 ohne jegliche Zusatzmodulemit, also mit reinem Go.

$ go build solver.go passenger.go sort.go \
  sort.go shore.go state.go
$ ./solver

Die Passagiere und den Fährmann modelliert Listing 2 mit von »const« definierten Integerwerten. Die Zuweisung »=iota« instruiert den Compiler, den Konstanten »Goat«, »Wolf« und so weiter die Integerwerte »0, 1, …« zuzuweisen. Damit sich diese nachher zur Unterhaltung des Users wieder in Zeichenketten verwandeln lassen, definiert die Methode »String()« auf den Typ »Passenger« ein Slice mit Strings, in das der Integerwert der Konstante (praktischerweise ab »0« genau wie die Indexnummern im Slice) genau an der richtigen Stelle hineingreift. Generell dient eine »String()«-Methode in Go dazu, selbstdefinierte Typen in Zeichenketten umzuwandeln, sobald diese sich in einem String-Kontext wiederfinden – zum Beispiel, wenn »Printf()« sie mit »”%s”« als Strings ausgeben möchte.

package main
type Passenger int
const (
  Goat Passenger = iota
  Wolf
  Cabbage
  Ferryman
)
func (p Passenger) String() string {
  return []string{"Goat", "Wolf",
    "Cabbage", "Ferryman"}[p]
}

Weiter geht es mit Listing 3, das mit »Shore« eine Datenstruktur für die Darstellung einer Uferseite samt zugehöriger Methoden definiert. Das Array »passengers« speichert die wartenden Passagiere innerhalb der »Shore«-Struktur ab Zeile 8. Alle Elemente sind vom Typ »Passenger«, nehmen also die in Listing 2 definierten Integerwerte an und sind auch in Listing 3 mit den zugehörigen Konstanten (etwa “Wolf”) referenziert, da beide Listings im Package »main« stehen.

package main
import (
  "fmt"
  "sort"
)
type Shore struct {
  passengers []Passenger
}
func (s Shore) String() string {
  sort.Sort(Passengers(s.passengers))
  return fmt.Sprintf("%s", s.passengers)
}
func (s Shore) Copy() Shore {
  c := Shore{}
  c.passengers = make([]Passenger,
    len(s.passengers))
  copy(c.passengers, s.passengers)
  return c
}
func (s *Shore) Add(p Passenger) {
  s.passengers = append(s.passengers, p)
}
func (s *Shore) Remove(p Passenger) {
  result := []Passenger{}
  for _, passenger := range s.passengers {
    if passenger != p {
      result = append(result, passenger)
    }
  }
  s.passengers = result
}
func (s *Shore) Move(p Passenger,
                     t *Shore) {
  s.Remove(p)
  t.Add(p)
}
func (s Shore) Has(p Passenger) bool {
  for _, passenger := range s.passengers {
    if passenger == p {
      return true
    }
  }
  return false
}
func (s Shore) IsValid() bool {
  if s.Has(Ferryman) {
    return true
  }
  if s.Has(Wolf) && s.Has(Goat) {
    return false
  }
  if s.Has(Goat) && s.Has(Cabbage) {
    return false
  }
  return true
}

Tiefe Kopien

Generell bietet Go keine Möglichkeit, eine verschachtelte Struktur vollständig zu kopieren. Um eine Deep Copy anzulegen, muss der Programmierer selbst Hand anlegen und zum Beispiel in einer Struktur liegende Arrays explizit kopieren. Die Methode »Copy()« ab Zeile 17 in Listing 3 wirkt auf einem vorgegebenen »Shore«-Objekt und initialisiert ein neues, noch leeres. Danach alloziert sie mit »make« ein »passenger«-Array gleicher Länge, kopiert dann mit der in Go eingebauten »copy()«-Funktion die Elemente des Originals in die Kopie und gibt Letztere an den Aufrufer zurück. So kann dieser einfach Spielzustände duplizieren und nächste Schritte durch graduelle Veränderungen einleiten.

Um einer Uferseite neue Passagiere zuzuordnen, sie wieder abzuziehen, einer neuen Uferseite zuzuweisen oder abzufragen, ob ein Passagier am vorliegenden Ufer stationiert ist, bedient man sich der Methoden »Add()«, »Remove()«, »Move()« und »Has()« in den Zeilen 25 bis 52 von Listing 3. So kann zum Beispiel ein Zustandsobjekt später eine seiner Uferseiten auswählen und mit »west.Has(Wolf)« eine Boolesche Antwort (»true«/»false«) auf die Frage erhalten, ob der Wolf anwesend ist.

Hier zeigt sich ein Nachteil der als Array gewählten Datenstruktur zum Speichern der Passagiere: Um zu sehen, ob ein bestimmter Passagier anwesend ist, muss eine For-Schleife alle Elemente abfahren, bis sie ihn findet, oder bei einer erfolglosen Suche am Ende »false« zurückgeben. Das Entfernen eines Passagiers reißt gar ein Loch in das Array, das eine For-Schleife dann umständlich wieder zusammenflicken muss, indem sie es ab Zeile 31 kurzerhand ohne den entfernten Passagier wieder aufbaut. Eine Map böte zügigere Zugriffe, hat aber den Nachteil, dass die in ihr gelagerten Daten unsortiert vorliegen und zu Anzeigezwecken sortiert werden müssten.

Ob die auf einer Uferseite anwesenden Passagiere den Regeln des Spiels widersprechen, prüft die Methode »IsValid()« ab Zeile 54. Sie implementiert quasi die Business-Logik des Verfahrens. Bei Anwesenheit des Fährmanns ist der Zustand auf jeden Fall erlaubt, denn Wolf und Ziege kommen gut miteinander aus, solange ein Aufpasser da ist. Fehlt er jedoch, gibt »IsValid()« in Zeile 59 »false« zurück, denn der Wolf würde kurzerhand die Ziege verschlingen. Dasselbe gilt für Ziege und Kohlkopf, und die Methode gibt auch in diesem Fall »false« für illegale Zustände auf der Uferseite zurück. Ist dagegen alles in Ordnung, liefert sie »true«.

Sortieren mit Go

Damit der Algorithmus später einfach feststellen kann, ob zwei Uferobjekte identische Passagiere aufweisen, vergleicht er deren mit »String()« ab Zeile 12 erzeugte Darstellung Zeichen für Zeichen. Da diese Arrays beim Umbauen zwischen Spielzuständen ihre ursprüngliche Ordnung verlieren, sortiert Zeile 13 sie nach den Passagiernummern. Diese sind zwar vom Typ her reinrassige Ganzzahlen, doch weigert sich der Go-Compiler, sie mit der Standardfunktion zur Integersortierung, »sort.Ints()«, zu sortieren. Deswegen greift Listing 4 ihm unter die Arme und bringt ihm bei, wie man ein Array von »Passenger«-Werten sortiert. Es definiert den Typ »Passengers« (Plural) sowie drei Methoden, mit deren Hilfe Go beliebige Datentypen sortiert.

package main
type Passengers []Passenger
func (p Passengers) Len() int {
  return len(p)
}
func (p Passengers) Swap(i, j int) {
  p[i], p[j] = p[j], p[i]
}
func (p Passengers) Less(i, j int) bool {
  return p[i] < p[j]
}

Die erste heißt »Len()« und gibt die Länge des Arrays an, die es einfach über die eingebaute Funktion »len()« ermittelt. Die zweite ist »Swap()« und zeigt dem Compiler, wie er während der Sortierung zwei Elemente an den Indexpositionen »i« und »j« miteinander vertauscht. Das gelingt in Go sehr einfach, weil es die Syntax »a,b = b,a« versteht. Drittens braucht die Sortierfunktion eine Methode »Less()«, die immer dann einen wahren Wert zurückgibt, falls der erste hereingereichte Wert kleiner ausfällt als der zweite. Beim vorliegenden Array von Integern führt der numerische Vergleich der beiden Elemente mit »p[i] < p[j]« zum Ziel.

Mit diesem Rüstzeug in Listing 4 kann nun Listing 3 »sort.Sort(Passengers(…))« auf das Array mit »Passenger«-Typen aufrufen, das die Funktion dann In-Place [3] sortiert.

Von Zustand zu Zustand

Die Zustände des Spiels, also die Situation an beiden Ufern, definiert Listing 5 mit dem Datentyp »State«. Go kennt ja keine Klassen, bietet aber Objektorientierung mit Structs und Methoden, die auf dem im Struct definierten Datentyp herumorgeln.

Dabei ist es wichtig, den Unterschied zwischen schreibenden und lesenden Methoden zu beachten. Ein normaler “Receiver”, das dem Funktionsnamen vorangestellte Objekt, wie zum Beispiel in der Funktion »IsValid()« in Zeile 13, erlaubt der Funktion nur lesenden Zugriff. Schreiben darf sie wohl, allerdings nur auf einer Kopie des Objekts, die nach Ablauf der Funktion auf Nimmerwiedersehen verschwindet.

package main
import (
  "fmt"
)
type State struct {
  west Shore
  east Shore
  prev *State
}
func (s State) IsValid() bool {
  return s.west.IsValid() &&
    s.east.IsValid()
}
func (s State) String() string {
  return fmt.Sprintf("%s | %s",
    s.west.String(),
    s.east.String(),
  )
}
func (s *State) Move(p Passenger) {
  from := &s.west
  to := &s.east
  if to.Has(Ferryman) {
    from, to = to, from
  }
  from.Move(p, to)
}
func (s State) IsFinished() bool {
  return len(s.west.passengers) == 0
}
func (s State) Copy() State {
  d := State{}
  d.west = s.west.Copy()
  d.east = s.east.Copy()
  return d
}
func (s State) Successors() []State {
  startShore := s.east
  if s.west.Has(Ferryman) {
      startShore = s.west
  }
  results := []State{}
  for _, passenger :=
         range startShore.passengers {
    candidate := s.Copy()
    candidate.Move(passenger)
    if passenger != Ferryman {
      candidate.Move(Ferryman)
    }
    if candidate.IsValid() {
      results = append(results, candidate)
    }
  }
  return results
}

Für persistente schreibende Zugriffe muss ein sogenannter Pointer Receiver her, wie ihn zum Beispiel »Move()« ab Zeile 25 zeigt. Egal, ob es sich bei »Move()« um einen normalen Receiver oder einen Pointer handelt, sieht der Aufruf von »state.Move()« völlig identisch aus. Deshalb muss der Programmierer aufpassen wie ein Haftelmacher: Fehlt der Pointer aus Versehen, treten keine Fehler auf – nur wird nichts richtig geschrieben, was (wissenschaftlich belegt) zu Tischhämmern und Haareraufen führt.

Das State-Objekt führt die zwei Ufer-Objekte »west« und »east« mit sich sowie einen Pointer »prev« auf den Zustand, aus dem es ursprünglich hervorging. Findet der Algorithmus später eine Lösung, lässt sich über diese Pointer-Kette rückwärts der Weg zum Ziel nachvollziehen. Von welchem Ufer aus sich Fährmann und Passagiere in Bewegung setzen, um in einem Folgezustand zu landen, hängt davon ab, wo der Fährmann sich gerade befindet. So legt Zeile 26 die Richtung West-Ost fest, vertauscht aber »from« und »to« in Zeile 29, falls es den Fährmann auf der Ostseite findet.

Chefsache und Knechtarbeit

Ein Zustand gilt als legal, falls, wie »IsValid()« ab Zeile 13 in Listing 5 prüft, seine beiden Ufer-Objekte »west« und »east« mit ihren »IsValid()«-Methoden grünes Licht geben. Die String-Darstellung des »State«-Objekts errechnet dessen »String()«-Methode ab Zeile 18. Sie delegiert ihrerseits die Darstellung nur an die beiden Ufer-Objekte und fügt als Chefsache beide Teilergebnisse mit einem trennenden Mittelstrich zu einem String zusammen. Eine Kopie eines Zustands legt »Copy()« ab Zeile 38 an, indem es Kopien der beiden Ufer anfertigt, wobei es ebenfalls die harte Arbeit an die Ufer-Objekte delegiert.

Der Endzustand des Spiels wird erreicht, wenn »IsFinished()« ab Zeile 34 einen wahren Wert zurückgibt. Dazu prüft die Methode nur, ob auf der Westseite niemand mehr weilt. Falls nicht geschummelt wurde, sind dann Fährmann und alle Passagiere auf der Ostseite.

Die wichtigste Aufgabe eines State-Objekts besteht darin, Folgezustände zu finden, damit der Solver später den Suchbaum aufbauen kann. Die Methode »Successors()« ab Zeile 45 versucht hierzu, den Fährmann entweder allein oder mit einem am selben Ufer wartenden Passagier ans andere Ufer zu schicken. Sie probiert blind einfach alle Möglichkeiten durch und prüft jeweils in Zeile 60 mit »IsValid()«, ob damit ein gültiger Zustand entstanden ist. Falls ja, hängt es ihn an die Ergebnisliste an, die die Methode an den aufrufenden Solver zurückreicht.

Des Rätsels Lösung

Dem Solver in Listing 6 bleibt nun nur noch, in »main()« den Startzustand anzulegen, dessen Westufer den Fährmann sowie alle Passagiere zuzuweisen und »solve()« ab Zeile 8 aufzurufen. Dort bestimmt eine Todo-Liste in Form eines Arrays von State-Objekten noch zu untersuchende Zustände. Stellt sich einer davon als Zielzustand heraus, gibt »IsFinished()« in Zeile 25 einen wahren Wert zurück. Die For-Schleife ab Zeile 27 stellt dann den Pfad dorthin zusammen, indem sie die »prev«-Pointer der Zustände verfolgt. Diese führen sie bis zum Startzustand, der einen uninitialisierten »prev«-Pointer aufweist, also gemäß dem Go-Standard den Wert »nil« hält. Aus dieser verkehrten Folge baut Zeile 32 rückwärts ein Array auf, indem es neue Elemente mit »append()« immer am Anfang des bestehenden Arrays einfügt und aus dem Ergebnis ein neues Array macht.

package main
import (
  "errors"
  "fmt"
)
func solve(state State) ([]State, error) {
  seen := make(map[string]bool)
  todo := []State{state}
  for len(todo) > 0 {
    // pop off last element
    lastidx := len(todo) - 1
    s := todo[lastidx]
    todo = todo[:lastidx]
    // prevent cycles
    if _, ok := seen[s.String()]; ok {
      continue
    }
    seen[s.String()] = true
    if s.IsFinished() {
      path := []State{}
      for cs := &s; cs.prev != nil;
                    cs = cs.prev {
        c := cs.Copy()
        path = append([]State{c}, path...)
      }
      path = append([]State{state}, path...)
      return path, nil
    }
    for _, succ := range s.Successors() {
      // insert new element at end
      succ.prev = &s
      todo = append([]State{succ}, todo...)
    }
  }
  return []State{},
    errors.New("Can't solve")
}
func main() {
  var state State
  state.west.Add(Wolf)
  state.west.Add(Cabbage)
  state.west.Add(Ferryman)
  state.west.Add(Goat)
  solution, err := solve(state)
  if err != nil {
    panic(err)
  }
  fmt.Printf("Solution:\n")
  for _, step := range solution {
    fmt.Printf("[%s]\n", step)
  }
}

Anfangs steht in der Todo-Liste nur der Startzustand mit allen Teilnehmern am Westufer. Die »for«-Schleife ab Zeile 13 entfernt in Zeile 17 mit Slice-Arithmetik immer das letzte Element. Am Ende der Schleife sucht dann »Successors()« mögliche Nachfolger des aktuellen Zustands und fügt sie am Anfang des »todo«-Array-Slices ein. Dadurch entsteht eine Warteschlange, bei der neue Elemente von links eingeschoben und von rechts abgeholt werden (“First in, last out”).

Dieses Verfahren führt zu einer Breitensuche [4] (Breadth-first, Abbildung 2) im Suchbaum. Sie klappert die Knoten schichtweise ab, bis sie den Zielzustand findet. Käme statt einer Warteschlange ein Stack zum Einsatz (“First in, first out”), etwa indem neue Zustände rechts an das Array angehängt und von dort auch wieder abgeholt würden, hätte dies ein Depth-first-Verhalten im Baum zur Folge. Der Algorithmus würde nicht schichtweise vorgehen, sondern immer sofort bis zum äußersten Astende vorstoßen. Dabei fände er möglicherweise schneller eine Lösung – aber nicht unbedingt die kürzeste, sondern vielleicht eine sehr umständliche.

Abbildung 2: Die Breitensuche (Breadth-first) erforscht den Baum schichtweise und findet den kürzesten Lösungspfad. Quelle: MRE, CC BY-SA 3.0

Damit der Solver sich nicht festfährt und den Fährmann zum Beispiel immer leer hin- und herfahren lässt, was eine unendliche Reihe von Folgezuständen generiert, prüft Zeile 20, ob ein vorgeschlagener Folgezustand schon einmal bearbeitet wurde. Dazu schlägt sie in der Map »seen« (einer Hash-Tabelle) nach, ob die String-Darstellung des Zustands dort als Schlüssel steht. Falls ja, ignoriert die »continue«-Anweisung in Zeile 21 diesen Eintrag und läutet die nächste Runde in der »for«-Schleife ein.

Abbildung 3 zeigt die Ausgabe des Solvers, der in insgesamt sieben Zügen eine Lösung gefunden hat. Zuerst bringt der Fährmann die Ziege ans Ostufer, fährt leer zurück, schippert den Wolf ans Ostufer, nimmt aber die Ziege wieder mit. Am Westufer angelangt, schnappt er sich den Kohl und lässt die Ziege da. Er bringt das Grünzeug ans Ostufer, an dem der Wolf wartet, aber den Kohl in Ruhe lässt. Nun muss der Fährmann nur noch leer zurückfahren und die Ziege ans Ostufer bringen. Damit ist die ganze Mannschaft ohne bedrohliche Zwischenfälle heil angekommen.

Abbildung 3: Der Algorithmus löst das Rätsel in sieben Zügen.

Noch mehr

Einmal programmiert, lässt sich der Solver bei Bedarf auch erweitern. Wie wäre es mit einem zusätzlichen Passagier, der sich mit allen anderen gut verträgt, zum Beispiel einem Lachs? Flugs in Listing 2 im »const«-Konstrukt mit »Salmon« eingebaut und in der »main()«-Funktion in Listing 6 mit »state.west.Add(Salmon)« verdrahtet, findet der Solver auch dafür eine Lösung, allerdings etwas umständlicher: Abbildung 4 zeigt die neun Schritte zum Ziel.

Abbildung 4: Mit einem Lachs als zusätzlichem Passagier findet sich ebenfalls eine Lösung, wenngleich eine umständlichere.

Dabei setzt der Fährmann zuerst die Ziege über, dann den Lachs, und dann den Kohlkopf. Nun kann er allerdings nicht leer zum am Westufer verbleibenden Wolf zurückfahren, denn die Ziege würde den Kohlkopf verspeisen. Stattdessen bringt er die Ziege wieder zurück, setzt den Wolf über, um dann leer zurück zur Ziege am Westufer zu fahren und sie als letzte überzusetzen. Daran hätte ein menschlicher Rätselfreund sicher eine Weile herumgetüftelt, aber für den Algorithmus bedeutet das nur Routine. (uba)