6
$\begingroup$

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

m=3

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.

m=2,k=3,n=2

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.

$\endgroup$
4
  • $\begingroup$ why close instead of migrate? $\endgroup$ – BCLC May 9 at 11:44
  • 1
    $\begingroup$ I didn't know that is even possible :-) (Still n00b when it comes to all the SE functionalities...) $\endgroup$ – Hauke Reddmann May 9 at 19:07
  • $\begingroup$ 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? $\endgroup$ – loopy walt May 10 at 23:34
  • 2
    $\begingroup$ @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). $\endgroup$ – Hauke Reddmann May 11 at 13:02
1
$\begingroup$

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)})$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Hauke Reddmann May 11 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.