Are 'zero-one' jigsaw puzzles NP-complete?

Question

I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed adjacent to each other iff the symbol on one tile's facing edge is $k$ and the symbol on the other tile's facing edge is $\bar{k}$, for some $k\in\{1\ldots n\}$. Then, given a set of $m^2$ tiles, can they be placed into an $m\times m$ square (rotating but not flipping the tiles) with all edges matching correctly? (There's also a variant on this problem in which four $1\times m$ 'framing' edges are provided and the pieces must fit correctly into that frame).

I know this problem is NP-complete for sufficiently large $n$, but the bounds that I've seen on $n$ seem to be fairly large; I'm interested in the problem for small values of $n$ and in particular for $n=1$, the 'zero-one' case (where every edge is labeled either $0$ or $1$ and edges with a $0$ must be matched to edges with a $1$). Here there are (with rotational symmetry) just six tile types (the all-zeroes tile, the all-ones tile, the tile with three zeroes and a one, the tile with three ones and a zero, and two distinct tiles with two zeroes and two ones, '0011' and '0101'), so a problem instance is just a specification of $m$ and a set of five numbers $T_{0000}$, $T_{0001}$, $T_{0011}$, $T_{0101}$, $T_{0111}$ and $T_{1111}$ (representing the count of each type of tile) with $T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$. The problem is obviously in NP (with $m$ given in unary) since a solution can simply be exhibited and then checked in polynomial (in $m$) time, but is it known to be NP-complete, or is there some dynamic programming algorithm that can be applied here? What about the 'framed' case where the problem specification also includes the four edges of the square that are to be matched? (Obviously if the unframed case is NP-complete the framed case almost certainly is as well)

Answer 1

Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP). Either one will be able to encode the constraints, but in a slightly different way:

• For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).

• For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).

I would expect that for small or medium sized $n$, this approach might work efficiently.