2. Problem Formulation (20 points) Consider the Cats and Mice problem: Three cats and three mice wish to cross from the left side to the right side of the river using a single boat. The boat can only hold two animals and can be rowed by any animal in the group. The goal is to find a sequence of moves that transfers all six animals to the right hand side of the river. At no time can the cats outnumber the mice on either side of the river. Your task is to formulate this as a search problem. (a) (6 pts) Define a state representation. (When deciding what variables to include in your represen- tation, you should assume that an action is defined by the number of cats and the number of mice to be moved to the other side of the river.) (b) (8 pts) Show the complete search space for this problem. Clearly indicate the initial state and the goal state. Assume that the boat is initially at the left bank of the river. 2. Problem Formulation (20 points) Consider the Cats and Mice problem: Three cats and three mice wish to cross from the left side to the right side of the river using a single boat. The boat can only hold two animals and can be rowed by any animal in the group. The goal is to find a sequence of moves that transfers all six animals to the right hand side of the river. At no time can the cats outnumber the mice on either side of the river. Your task is to formulate this as a search problem. (a) (6 pts) Define a state representation. (When deciding what variables to include in your represen- tation, you should assume that an action is defined by the number of cats and the number of mice to be moved to the other side of the river.) (b) (8 pts) Show the complete search space for this problem. Clearly indicate the initial state and the goal state. Assume that the boat is initially at the left bank of the river