Missionare und Kannibalen

Aufgabe
3 Missionare und 3 Kannibalen müssen einen Fluss überqueren. Das Boot kann maximal zwei Personen tragen und kann nicht ohne Bootsführer fahren. Dabei kann jeder Missionar und jeder Kannibale Bootsführer sein. Um sicher zu stellen, das niemand aufgefressen wird, sollten nie mehr Kannibalen als Missionare auf einer Seite stehen, wenn mindestens ein Missionar auf der Seite ist. Wie schafft man es mit den wenigsten Überfahrten alle 6 Personen über den Fluss zu bekommen?

Aufgabe

3 Missionare und 3 Kannibalen müssen einen Fluss überqueren.
Das Boot kann maximal zwei Personen tragen und kann nicht ohne Bootsführer fahren.
Dabei kann jeder Missionar und jeder Kannibale Bootsführer sein.
Um sicher zu stellen, das niemand aufgefressen wird, sollten nie mehr Kannibalen als Missionare auf einer Seite stehen, wenn mindestens ein Missionar auf der Seite ist.
Wie schafft man es mit den wenigsten Überfahrten alle 6 Personen über den Fluss zu bekommen?

Tipp 1
Eine Skizze hilft. Wie starte ich? Was ist der "Zustand" nach der ersten Überfahrt?

Tipp 2
Hier lohnt es sich, ein Netzwerk an Möglichkeiten zu entwickeln, und jeweils alle Möglichkeiten zu explorieren.

Lösung
Die kürzeste Lösung benötigt 11 Schritte. K stehe für Kanibal, M für Missionar und B für Boot. Anfangszustand: 3K 3M B \|\| 0K 0M 1: -> 1K 1M 2: <- 1M Alternativ: 1: -> 2K 2: <- 1K Situation: 2K 2M B \|\| 1K 1M 3: -> 2K 4: <- 1K 5: -> 2M 6: <- 1K 1M 7: -> 2M 8: <- 1K 9: -> 2K Situation: 1K 0M \|\| 2K 3M B 10: <- 1K 11: -> 2K Alternativ: 10: <- 1M 11: -> 1K 1M

Aufgabe

Tipp 1

Tipp 2

Lösung