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.