Four people need to cross a bridge at night which only supports two people at the same time. Person A needs 1 minute to cross the bridge, B needs 2 minutes, C needs 5 minutes and D needs 10 minutes. When two people cross the bridge they move at the slowest person’s pace. They have a torch which has battery left for only 17 minutes. They can’t cross the bridge without light. How can they manage to cross the bridge?

One might guess that an obvious solution would be to let the fastest person (A) shuttle each other person over the bridge and return alone with the torch. This would give the following schedule:

A, B | -> | 2 |

A | <- | 1 |

A,C | -> | 5 |

A | <- | 1 |

A,D | -> | 10 |

The total duration of this schedule would be 19 minutes, so the torch would run out of battery while person A and D are still on the bridge.

The optimal solution consists of letting the two slowest people (C and D) cross the bridge together, giving the following schedule:

A, B | -> | 2 |

B | <- | 2 |

C,D | -> | 10 |

A | <- | 1 |

A,B | -> | 2 |

Which gives a total crossing time of exactly 17 minutes.

Writing a prolog program to solve this kind of river crossing problems is a walk in the park. Check it out if you want to know an alternative solution.