$4.(20$ marks$)$ Consider the following problem:

Once upon a time a farmer went to market and purchased a fox, a goose, and a bag of beans. On

his way home, the farmer came to the bank of a river and hired a boat. But in crossing the river by

boat, the farmer could carry only himself and a single one of his purchases $-$ the fox, the goose, or

the bag of the beans.

If left alone, the fox would eat the goose, and the goose would eat the beans.

The farmer$$s challenge was to carry himself and his purchases to the far bank of the river, leaving

each purchase intact. How could he do it$?$

Use state space search method to solve this problem. Let nodes represent states of the world and use $|$ to

separate the banks. For example, the state where the farmer and the goose are on the starting bank and the fox and beans on the far bank is represented as a state $($F$,$ g $|$ f$,$ b$),$ where F is farmer, g is goose, f is fox, and b is beans. The start state is $($F$,$ f$,$ g$,$ b $|).$