Missionaries and cannibals

(27th-April-2020)

• Three missionaries and three cannibals are on the left bank of a river.

• There is one canoe which can hold one or two people.

• Find a way to get everyone to the right bank, without ever leaving a group of missionaries in one place outnumbered by cannibals in that place.

Represent the state as (m, c, b)

In the initial state (3, 3, 1)

Target state (0, 0, 0)

(3,3,1) → CC → (3,1,0) → C → (3,2,1) → CC → (3,0,0)

→ C → (3,1,1) → MM → (1,1,0) → MC → (2,2,1) → MM → (0,2,0) → C

→ (0,3,1) → CC → (0,1,0) → C → (0,2,1) → CC → (0,0,0)