Model your problem as a states graph.
In here, a state is ({L,R}n,{L,R}m,{L,R}) Where:
- First
n
entries: one for each missionary - where he is: left/right bank of the river - next,
m
entries: one for each canibal- where he is: left/right bank of the river - Last entry is for the boat
These are your vertices - you should also trim the invalid states - where strength of missionaries is not enough in one (or more) side. It is easy to calculate it for each state.
Your edges are:
E = { (S1,S2) | Can move in one boat ride from S1 to S2 }
All is left to do - use some shortest path algorithm to find the shortest path from: (L,L,....,L)
to (R,R,...,R)
.
You can use BFS for this task, or even bi-directional search - or an informed algorithm (with admissible heuristic) such as A* Algorithm.
PS. The 'graph' is just conceptual, in practice you will have a function next:S->2^S
, that given a state - returns all valid successors of this state (states that you can get to them using one edge on the graph from S
). This will allow you to "generate the graph" on the fly.
Your next(S)
function should be something like (high level pseudo code, without optimizations):
next(S):
let x be the bank where the boat is, and y the other bank
for each person p1 on bank x:
S' = S where boat and p1 moved from x to y
if S' is valid according to strength limitations, yield S'
for each p2 != p1 on bank x:
S' = S where boat and p1 and p2 moved from x to y
if S' is valid according to strength limitations, yield S'