Consider the problem of tiling a surface (completely and exactly covering it) with $n$ dominoes ($2\times 1$ rectangles). The surface is an arbitrary edge-connected (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 tree-structured constraint graph.
-
Describe exactly the set of solvable instances that have a tree-structured constraint graph.