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.

  • 1
    $\begingroup$ 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. $\endgroup$ Apr 23, 2019 at 20:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.