River Crossing Puzzle

Problem A classic river-crossing logic puzzle: a farmer must transport a fox, a chicken, and a bag of grain across a river using a boat that carries only the farmer plus one item at a time. The fox must never be left alone with the chicken, and the chicken must never be left alone with the grain.

Input / Output

• Input: the set of items, and the pairs that may not be left together unsupervised.
• Output: a valid sequence of crossings that moves everything to the far bank — and in the generalised version, the shortest such sequence.

Constraints

• The boat carries at most two entities including the farmer, and the farmer must be aboard for every crossing.
• A forbidden pair may not be left unsupervised on either bank.
• Items may be ferried back, so the reachable states form a graph rather than a straight line.

Example

• The classic seven-move solution: take the chicken across, return alone, take the fox across, bring the chicken back, take the grain across, return alone, take the chicken across again.