5
$\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.

Improve this question
$\endgroup$
4
  • $\begingroup$ why close instead of migrate? $\endgroup$ Commented May 9, 2021 at 11:44
  • 1
    $\begingroup$ I didn't know that is even possible :-) (Still n00b when it comes to all the SE functionalities...) $\endgroup$ Commented May 9, 2021 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$ Commented May 10, 2021 at 23:34
  • 3
    $\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$ Commented May 11, 2021 at 13:02

1 Answer 1

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

Improve this answer
$\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$ Commented May 11, 2021 at 13:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.