3 Missionaries and 3 cannibals - crossing the river

3 missionaries (or sheep or carrots) and 3 cannibals (or wolves or rabbits) stand on a riverbank. On
the same riverbank a boat, that can maximally take 2 persons (minimally 1), lies. The 6 people are
facing a problem: how to optimally transport (minimal number of moves) ourselves from
the current riverbank (the left one) to the opposite bank of the river (the right one) in a way
that guarantees that at any time the number of cannibals never outnumber the number of
missionaries (they will then be eaten)?

The missionaries and cannibal problem is a popular problem used in Artificial intelligence to understand and experiment with search methods. Here is a list of the possible optimal solutions for the various cases

1 cannibal and 1 missionary

Step1:(left 1 1 0 0)
Step2:(right 0 0 1 1)

2 cannibals and 2 missionaries

Solution1:
((left 2 2 0 0) (right 2 0 0 2) (left 2 1 0 1) (right 0 1 2 1) (left 1 1 1 1) (right 0 0 2 2))

Solution2:
((left 2 2 0 0) (right 1 1 1 1) (left 2 1 0 1) (right 0 1 2 1) (left 0 2 2 0) (right 0 0 2 2))

3 cannibals and 3 missionaries

Solution1:
((left 3 3 0 0)
(right 3 1 0 2)
(left 3 2 0 1)
(right 3 0 0 3)
(left 3 1 0 2)
(right 1 1 2 2)
(left 2 2 1 1)
(right 0 2 3 1)
(left 0 3 3 0)
(right 0 1 3 2)
(left 1 1 2 2)
(right 0 0 3 3))

Solution2:

((left 3 3 0 0)
(right 2 2 1 1)
(left 3 2 0 1)
(right 3 0 0 3)
(left 3 1 0 2)
(right 1 1 2 2)
(left 2 2 1 1)
(right 0 2 3 1)
(left 0 3 3 0)
(right 0 1 3 2)
(left 0 2 3 1)
(right 0 0 3 3))

2 cannibals and 3 missionaries

Solution1:

((left 3 2 0 0)
(right 2 1 1 1)
(left 2 2 1 0)
(right 1 1 2 1)
(left 2 1 1 1)
(right 1 0 2 2)
(left 1 1 2 1)
(right 0 0 3 2))

Solution2:

((left 3 2 0 0)
(right 3 0 0 2)
(left 3 1 0 1)
(right 1 1 2 1)
(left 2 1 1 1)
(right 0 1 3 1)
(left 1 1 2 1)
(right 0 0 3 2))

1 cannibal and 2 missionaries

Solution1:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 0 0 2 1))

Solution2:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 1 0 1 1) (left 2 0 0 1) (right 0 0 2 1))

0 cannibal and 1 missionaries

((left 1 0 0 0) (right 0 0 1 0))

Solutions are not possible for numbers greater than 3 or cases in which cannibals outnumber missionaries.