It is night and you control a single insect. You know the maze, but you do not know what square the insect will start in. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, the insect is guaranteed to be on the exit square, regardless of initial position. The insect executes the actions mindlessly and does not know whether its moves succeed: if it uses an action which would move it in a blocked direction, it will stay where it is. For example, in the maze below, moving right twice guarantees that the insect will be at the exit regardless of its starting position. Which of the following state representations could be used to solve this problem?
1. A tuple (x, y) representing the position of the insect.
2. A tuple (x, y) representing the position of the insect, plus a list of all squares visited by the insect.
3. An Integer troprosenting how many time steps have passed, plus an integer b representing how many times the insect's motion has been blocked by a wall.
4. A list of boolean variables, one for each position in the maze, indicating whether the insect could be in that position.
5. A list of all positions the insect has been in so far.