State Representation in the Farmer Problem

The farmer puzzle is a classic problem involving a farmer who needs to transport a wolf, a goat, and a cabbage across a river. The farmer will use a boat and can only take one of the wolf, goat and cabbage at a time with him or go by himself. The wolf and goat cannot be left alone together (the wolf will eat the goat). The goat and cabbage cannot be left alone together (the goat will eat the cabbage).

Consider this as a toy search problem. Initially, the farmer, the wolf, the goat and the cabbage are all on the left bank of the river. The goal is to figure out a way for the farmer to successfully transport all three items safely across the river. The farmer can see both side of the river at all time.

If you’re a farmer needing to transport a wolf, goat, and cabbage across a river, how would you best represent the state of everyone’s position?