Consider the problem of tiling a surface $($completely and exactly covering it$)$ with n

dominoes $(2$ x $1$ rectangles$).$ The surface is an arbitrary edge$-$connected $($i$.$e$.,$ adjacent

along an edge, not just a corner$)$ collection of $2$n $1$x$1$ squares $($e$.$g$.,$ a checkerboard, a

checkerboard with some squares missing, a $10$ x $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. $($Hint: does it matter which particular domino goes

on a given pair of squares?$)$

c$.$ Construct a surface consisting of $6$ squares such that your CSP formulation from part

$($b$)$ has a tree$-$structured constraint graph.

d$.$ Describe exactly the set of solvable instances that have a tree$-$structured constraint

graph.