Conjecture on NP-completeness of tesselation of Wang Tile up to finite size Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
Could we actually show that the problem of trying to tile a finite size square with a given set of Wang tile to be NP-complete?
 A: The problem is also trivially NP-complete without an anchor tile. The trick is that we can easily force any tile to become an anchor tile. First, take a set of tiles that have a unique way of tiling an $n\times n$ square, e.g., by putting (respectively matching) $(i,j)$'s on their sides where $1\le i,j\le n$. Then take the "direct product" of this tile set with, e.g., the tile set described by Joel except for the position where you want your anchor tile, there keep only that. This gives a suitable tile set.
ps. I used to give this as an exercise for undergrads and some of them always solved it.
A: You don't need an anchor tile.  Jed Yang and I recently solved this on the way to stronger NP-completeness results (versions of this result were already known).  We explain it all here.  Similarly, the rectangular tileability problem is undecidable according to Yang's recent result here.
A: If one considers the anchor-tile tiling problem, where the tiling must include a specified anchor tile, then indeed this problem is NP-complete. To see this, suppose that we have a given NP problem, where there is a polynomial time computable Turing machine $M$, such that we want to know on input $x$ whether there is some $y$ such that $M$ accepts $(x,y)$, and $M$ operates in polynomial time $p$ on any input. For any Turing machine, we have a canonical set of Wang tiles, with a specific anchor, such that the tilings extending this anchor correspond in a tight way to the operation of $M$ on a given input, allowing a tiling just in case the machine accepts the given input. If you understand how these tiles are constructed, so as exactly to mimic the operation of the Turing machine, then it is clear that we may also design the tiles so as to allow an arbitrary oracle input for the computation. So for any $x$, we can produce a set of tiles, such that they admit a tiling of the square $p(|x|)\times p(|x|)$ with the anchor if and only if there is some $y$ such that $M$ accepts $(x,y)$. In this way, we reduce the given NP problem to an instance of the tiling problem. So the anchor tiling problem of a given size must be NP complete. 
I'm less sure of what happens when you do not insist on a given anchor tile, but perhaps this issue can be resolved as it is in the case of the halting problem, where one shows that the tiling problem even without anchors is equivalent to (the negation of) the halting problem. 
