Czy układanki „zero-jedynkowe” są kompletne NP?

Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka to ˉ k , dla niektórych k ∈ { 1 … n } . Następnie, biorąc pod uwagę zestaw m 2 płytek, można je umieścić w m × $\{1\ldots n, \bar{1}\ldots\bar{n}\}$$k$$\bar{k}$$k\in\{1\ldots n\}$$m^2$$m\times m$kwadratowy (obracający się, ale nie odwracający płytki) z dopasowaniem wszystkich krawędzi? (Istnieje również wariant tego problemu, w którym cztery $1\times m$ krawędzie kadrowania o a elementy muszą dobrze pasować do tej ramy).

Wiem, że ten problem jest NP-zupełny dla wystarczająco dużego , ale granice, które widziałem na n, wydają się być dość duże; Interesuje mnie problem małych wartości n, a zwłaszcza n = 1 , przypadek „zero-jeden” (gdzie każda krawędź jest oznaczona jako 0 lub 1, a krawędzie z 0 muszą być dopasowane do krawędzi z $n$$n$$n$$n=1$$0$$1$$0$$1$$m$$T_{0000}$$T_{0001}$$T_{0011}$$T_{0101}$$T_{0111}$$T_{1111}$$T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$$m$$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)

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.