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)