Part 2: Drawing State Space Diagrams (30 points) 1. Consider the following problem: You are given a 3x3 grid of squares, and each square can either be filled with an "X", an "0", or be empty. Pressing a square will toggle the states of the square and also its left, right, above, and below it. 0 X 0 For example, if we press the upper-left square in the grid above, the resulting grid will be: 0 x X NORQUEST COLLEGE X The goal of the game is to fill out the grid only with x or o. 2. Draw the state space diagram for the problem using a graph or a tree structure up to 3 levels. Label each node with the state of the problem at that point in the search process. Your start node is: 3. Analyze the state space diagram and the structure of the problem. How many nodes are in the state space? How many possible solutions are there? What is the optimal solution, and how many steps does it require? 4. Which search algorithms you think would be the best to fine a path from start node to the goal node?