Search code examples
calgorithmriver-crossing-puzzle

Cannibals and Missionaries with Strength

i need some help with a math task our professor gave us. Any suggestions would help. The problem is:

There are N cannibals and M missinaries. All missionaries have a strenght attribute, which can be 1 or any positive whole number. Strenght indicates how many cannibals he can fight off.

Basically: there are two sides of the river, there is a 2-slot boat, and you have to transfer all the guys to the other side, without letting the cannibals eat the missionaries.

How would you write a program for this? What would be the transferring-grouping algorythm?

Thanks in anticipation,

Mark.

Solution

  • 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'