Jigsaw Puzzle Puzzle

Question

(In German a Jigsaw is simply called Puzzle, the pun is lost in English...)

A jigsaw has to match by form and (mostly!) by color at the tile borders. Assume your basic jigsaw tile consists of $m*m$ squares. Any square of the tile may have any of $k$ colors (obviously, only colors on the border of a tile are relevant). Also, any square may be "donated" to another tile. We want to build a jigsaw with $n*n$ tiles, all different from each other, with an unique solution (modulo rotation and possibly mirroring). Two questions:

1. Assume we just want to match form, color is irrelevant. Example:

This is a "classical" style $m=3,n=2$ jigsaw. (Uniqueness of fit is obvious.) If we loosen the form requirement a bit (here I additionally assumed that all corners of a tile may not be donated), $m=2$ might even suffice. Question: given $n$, what is the minimal $m$ required? (A good $O(n)$ bound is already acceptable as solution, since a function $m=f(n)$ might be too hard to derive.)

2. Assume we have straight squares as tiles, and only require matching borders by color.

Here is a $k=3,m=2,n=2$ example, again with easy to see uniqueness of fit. Same question: Given $n$, which combination $m,k$ suffices? (Concentrate on the extreme cases $k=const.$ and $m=const.$ first, they seem fairly easy to me.)

Disclaimer: If you find that the question better belongs on one of the Math SE, feel free to close it without further ado.

Answer 1

Partial answer for problem 2

Suppose $n$ is fixed and $m=2$. Excluding rotations and mirroring there are $k^4/8$ different tiles. So we want $k^4/8 \geq n^2$. So the smallest $k$ needs to be $ceiling((8n^2)^{(1/4)})$. We still need to show that these tiles can form a valid tiling and I don't know how to do that. But for the example you showed we obtain $k=3$, which works. For arbitrary $m$, the smallest $k$ will be $ceiling((8n^2)^{(1/m^2)})$.