# Computational complexity of Wang tiling of a finite plane

For a given set of Wang tiles on an $$L \times L$$ plane (where a tile is $$1\times 1$$) we first need to determine whether a tiling of the plane is possible. If so, we can then consider the problem of how to construct such a tiling.

Is it known what the computational complexity of these problems are (i.e., how they scale with $$L$$)?

I've searched and found a lot of interesting info about the problem. But I've seen no statement of a complexity.

• I don't have a full answer on this, but in case this information is useful to you: There are some references to this problem in erikdemaine.org/papers/Jigsaw_GC/paper.pdf, specifically to Garey/Johnson: "Computers and Intractability", p. 257, where the problem is classified as NP-complete for the case that the number of colors grows with $L$. I guess you are also interested in the case where the number of colors is constant, I do not have references for that. – f9c69e9781fa194211448473495534 Apr 23 at 20:57