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

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

Formulate this problem precisely as a CSP where the squares are the variables, keeping the state space as small as possible. (Hint: does it matter which particular domino goes on a given pair of squares?)

Construct a surface consisting of 6 squares such that your CSP formulation from part (b) has a treestructured constraint graph.

Describe exactly the set of solvable instances that have a treestructured constraint graph.