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

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)

• It can't be NP-complete, since there are only $\theta(m^{10})$ possible inputs, and by Mahaney's theorem you need more than that to make a problem NP-complete (unless P=NP). But if you use a frame, this obstruction vanishes. So it might be NP-complete with a frame. Aug 22 '13 at 17:02
• An intermediate step would be to prove that the problem of deciding if a partially filled 6-tiles jigsaw puzzle (i.e. some of the pieces are already on the board and cannot be moved) can be correctly completed is NP-complete.
– Vor
Aug 23 '13 at 20:36

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.

• I agree that this seems like a reasonable means of solving the problem, but I'm less interested in specifically solving instances of the problem than I am in understanding its complexity. (For instance, if it's in P then there's almost certainly some sort of dynamic-programming approach to it that would handily outdo abstract SAT/linear programming solvers on the problem.) Aug 21 '13 at 19:29
• @StevenStadnicki, OK, fair enough. However, I'm struggling to reconcile ~"I'm interested in understanding its (asymptotic) complexity (e.g., whether it is NP-complete)"~ with ~"I'm interested in the problem for small values of $n$"~.
– D.W.
Aug 21 '13 at 19:30
• Sorry, that may be some confusion in the problem specification; I'm using $n$ to denote (essentially) the number of edge shapes and I'm particularly interested in the case where there's only one edge shape to match (think 'innie' or 'outie'); I'm wondering about the complexity of that problem as a function of $m$, the grid size. Aug 21 '13 at 19:41
• @StevenStadnicki, ahh, my mistake! Sorry, I didn't read carefully enough. That makes sense -- thank you.
– D.W.
Aug 22 '13 at 0:47
• No worries - I should have considered it up front; when I get home I'll try and edit the question to use a more 'traditional' parametrization. Aug 22 '13 at 0:48