a.

$$ (M_L,C_L,B,M_R,C_R) $$

$$ (3,3,L,0,0) $$

State Space Diagram and Size

The state space consists of all possible valid states where:

• The number of missionaries and cannibals on each side is between 0 and 3.

• The boat is either on the left (L) or right (R).

• The missionaries must never be outnumbered by cannibals on either side.

Total Possible States

Each person can be on either side, and the boat can also be on either side. Without considering validity constraints, the total number of possible states is:

$$ (4 \times 4) \times 2 = 32 $$

(because M_L, C_L each range from 0 to 3, and B has 2 values).

• State Space Size: The number of valid states in the state space is 20 (excluding invalid states where missionaries are outnumbered).

b.

Solving the Missionaries and Cannibals Problem using Graph-Search Algorithm

We will implement Graph-Search with Breadth-First Search (BFS).

Graph-Search Pseudocode (BFS)