1. Three missionaries and three savages came to the river to cross it. There was a boat on the bank, which could carry no more than two people at a time. The question is how should the missionaries row the ferry, for the sake of safety, so that the number of savages on both sides of the river and on the boat at any one time should not exceed the number of the missionaries (otherwise it is not safe and the missionaries may be eaten by savages).

(a) Define the states and actions. (b) List all the possible states. (c) Analyze and determine the minimum number of states.

(d) Define the heuristic function applicable to the problem.