Tiling problem : tiling square allowing space.

Question

Given we have a 4 by 4 square and we place 2 by 1 tiles until we can not place it anymore without overlapping. For example, if $1$ denotes the tile and $0$ means the empty space, the tiling below is valid.

0110
1111
1111
0110

It is also a valid tiling to fill all space of the square.
Then is there any way to enumerate all possible tiling?

Answer 1

We can describe this problem as a SAT instance: we have a variable for every possible domino position and for each cell of the grid. Then we have the following clauses:

• If a domino position variable is true, then the two corresponding cells are on.

• If two dominoes intersect, they aren't both present.

• For every domino position, the two cells in that position aren't both empty.

• If a cell is on, then at least one of the covering dominoes is.

Feeding these clauses to a SAT solver, we can quickly check with a program that there are exactly $400$ solutions, $106$ if we treat equivalent final shapes as the same, or $19$ if we also treat rotated and reflected solutions as equivalent. (Each link is to a text file with the solutions listed.)