You have a $9 \times 9$ grid of squares, each of which can be colored red or blue. The grid is initially colored all blue, but you can change the color of any square any number of times. Imagining the grid divided into nine $3 \times 3$ subsquares, you want each subsquare to be all one color but neighboring subsquares to be different colors.

Formulate this problem in the straightforward way. Compute the size of the state space.

You need color a square only once. Reformulate, and compute the size of the state space. Would breadthfirst graph search perform faster on this problem than on the one in (a)? How about iterative deepening tree search?

Given the goal, we need consider only colorings where each subsquare is uniformly colored. Reformulate the problem and compute the size of the state space.

How many solutions does this problem have?

Parts (b) and (c) successively abstracted the original problem (a). Can you give a translation from solutions in problem (c) into solutions in problem (b), and from solutions in problem (b) into solutions for problem (a)?