River Crossing Puzzle

Problem: A classic river-crossing logic puzzle (e.g., a farmer must transport a fox, a chicken, and a bag of grain across a river using a boat that only carries the farmer plus one item at a time, without ever leaving the fox alone with the chicken, or the chicken alone with the grain).

Constraints: Boat carries at most 2 entities including the farmer; certain pairs cannot be left unsupervised together.

Approach: Model as a state-search problem where a state is (items on the near bank, items on the far bank, boat position). Perform BFS/DFS over valid state transitions (each move must not leave a forbidden pair unsupervised), searching for a path from the initial state (everything on the near bank) to the goal state (everything on the far bank). The classic solution: take the chicken across first, return alone, take the fox (or grain) across, bring the chicken back, take the remaining item across, return alone, then take the chicken across again.