# Jigsaw Puzzle Puzzle

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

1. 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.

• why close instead of migrate?
– BCLC
May 9 '21 at 11:44
• I didn't know that is even possible :-) (Still n00b when it comes to all the SE functionalities...) May 9 '21 at 19:07
• Merely out of curiosity, how is the pun supposed to work in German, as I take it puzzle only means jigsaw puzzle and nothing else? May 10 '21 at 23:34
• @loopywalt: I wanted to title "Puzzle Puzzle" as mixed German/English, but nobody would have parsed it to "a puzzle considering jigsaw puzzles". So the pun works only when mixing languages (what I constantly do for fun). May 11 '21 at 13:02

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)})$$.
• Maybe you should attack it slightly differently in the same vein: use (as $m=2$) a different coloring $k1,k2$ for any border (as we only want an upper bound for now). There are $(n-1)^2$ that must match, tiles will be automatically different (?). Thus $O(n)$ colors will suffice. This is higher than your $O(sqrt(n))$, but avoids the matching problem. May 11 '21 at 13:13