(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:
- 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.)
- 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.