In: Computer Science
Design a suitable representation and draw the complete search tree for the following problem: A farmer is on one side of a river, and wishes to cross
the river with a wolf, a chicken and a bag of grain.
He can only take one item at a time in his boat with
him. He can't leave the chicken alone with the grain, or it will eat the grain, and he can't leave the wolf alone with the chicken, or the wolf will eat the chicken. How does he get all three safely across to the
other side?
This is one of the classic problem in artificial intelligence.
Solution.
Given : man, wolf, bag of grain, chicken.
source: one side of the river.
destination : other side of the river.
constraint : man can travel with only one thing at a time, cannot leave bag of grain with chicken, chicken with wolf.
Answer:
Steps:
1. Man will first take chicken along with him to the other side of the river. As wolf cannot eat grain.
2. Man will come back to the side, wolf and and chicken is there.
3. Now man will take wolf along with him to the other side and while returning he will carry chicken along with him to the side where bag of grain is there leaving wolf only on the other side of the river.
4 Now bag of grain and chicken is there with him, so he will take bag of grain to other side and will there as wolf cannot eat grain and will come back alone.
5 Now man will take chicken with him, and all of them will be there at the other side of the river.