Consider the problem of tiling a surface (completely and exactly covering it) with n dominoes (2 × 1 rectangles). The surface is an arbitrary edge-connected (i.e., adjacent along an edge, not just a corner) collection of 2n 1×1 squares (e.g., a checkerboard, a checkerboard with some squares missing, a 10 × 1 row of squares, etc.). 

a. Formulate this problem precisely as a CSP where the dominoes are the variables. 

b. Formulate this problem precisely as a CSP where the squares are the variables, keeping the state space as small as possible. 

c. Construct a surface consisting of 6 squares such that your CSP formulation from part (b) has a tree-structured constraint graph. Describe exactly the set of solvable instances that have a tree-structured constraint graph.