Searching Problem in AI

Q. A farmer has a wolf, a goat and a cabbage on the west side of a river. He wants to get all of his animals and cabbage across the river onto the east side. The farmer has a row boat but he only has enough room for himself and one other thing. The wolf will eat the goat if they are left together alone. The goat will eat the cabbage if they are left together alone. How can the farmer get everything on the east side? Draw the search tree and show the final solution.

Solution:

Farmer, Wolf, Goat, Cabbage = (f,w,g,c)

West side, East side = (W,E)

Initially, all are on the West side.

                                         (W, W, W, W)

Then,

Farmer + Goat (W -> E)  (E, W, E, W)

Farmer alone (E -> W)    (W, W, E, W)

Farmer + Wolf (W -> E)  (E, E, E, W)

Farmer + Goat (E -> W)  (W, E, W, W)

Farmer + Cabbage (W -> E) (E, E, W, E)

Farmer alone (E -> W)    (W, E, W, E)

Farmer + Goat (W -> E)  (E, E, E, E)

Finally, all arrived on the East side.