Farmer, hex, fox and grain problem. Creating an admissible heuristic via Graph Search? I'm having troubles trying to think of an admissible heuristic for this problem. Currently I've represented this problem as follows. My graph for this is as follows. Graph 0 means left side of the river 1 means right side of the river The problem: A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right side of the river using a raft. The farmer can take one item at a time (hen, fox, or bushel of grain) using the raft. The hen cannot be left alone with the grain, or it will eat the grain. The fox cannot be left alone with the hex, or it will eat the hen. Right now i'm attempting to think of a way to create an admissible heuristic through euclidean distance.

Since the farmer can move only one object at a time, and has to move him or herself back and forth, it should be easy to see that with $n$ objects left on the left side of the river, and with the farmer on the right, it takes at least $2n$ moves to complete. If the farmer is on the left, it will take at least $2n-1$ moves

So, in terms of your defined variables, we have as a lower bound for the cost:

$$h(n)=2(1-FX)+2(1-HN)+2(1-GR)+FM-1$$