# Minimal givens of a Fill-a-Pix/Mosaic Puzzles

Recently, I solved some Fill-a-Pix Puzzles (or also called Mosaic Puzzles) and got fascinated by the techniques to solve a puzzle. For those who don't know the rules to solve such a puzzle, you can follow this link or just comprehend the following mathematical description of the problem (which I need to formulate my problem):

Definition Let $$A = (a_{ij}) \in M_{m,n}(\{0,1\})$$ and $$\mathcal{M}_A = (m_{ij}) \in M_{m,n}(\{0,\dots,9\})$$ be the matrix defined by $$m_{ij} = \Big| \big\{ a_{kl} \, \big| \, |k-i|\leq 1, |l-j|\leq 1, a_{kl} = 1 \big\} \Big|.$$ Let us call $$A$$ the picture matrix and $$\mathcal{M}_A$$ the corresponding data matrix.

Example

If $$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},$$ then $$\mathcal{M}_A = \begin{pmatrix} 2 & 3 & 2 \\ 4 & 5 & 3 \\ 3 & 4 & 2 \end{pmatrix}.$$

Observations and Thoughts

1. Not every matrix can be a data matrix, for instance there is no picture matrix $$A \in M_{1,2}(\{0,1\})$$ such that $$\mathcal{M}_A = \begin{pmatrix} 0 & 2 \end{pmatrix}$$.
2. It is not hard to show that if $$\require{enclose} \enclose{horizontalstrike}{M}$$ is a data matrix, then there is a unique matrix $$\require{enclose} \enclose{horizontalstrike}{A}$$ such that $$\require{enclose} \enclose{horizontalstrike}{M = \mathcal{M}_A}$$. A proof via induction is the key. (This observation is wrong, see 5.)
3. Let $$M$$ be a data matrix. Sometimes it suffices to not even know all entries of $$M$$ and still get a unique picture matrix corresponding to $$M$$ (this is exactly how this puzzle works). For example, if $$M = \begin{pmatrix}* & * & * \\ * & 9 & * \\ * & * & * \end{pmatrix},$$ then the unique matrix $$A$$ with $$M = \mathcal{M}_A$$ is $$A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}.$$
4. This does not always work though. To be more explicit: If we only know few entries of the data matrix, it can correspond to more than one possible picture matrices. An example is $$M = \begin{pmatrix} * & * & * \\ * & 8 & * \\ * & * & * \end{pmatrix}.$$ Here, both $$M = \mathcal{M}_A$$ and $$M = \mathcal{M}_B$$ where $$A = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \quad \text{or} \quad B = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$$ are possible solutions, depending, for instance, on the upper left entry of $$M$$.
5. Even if we know all entries of the data matrix $$M$$, there might be different matrices $$A$$ and $$B$$ with $$\mathcal{M}_A = M = \mathcal{M}_B$$ as Jaap Scherphuis pointed out in the comments (and this is why observation 2. is wrong). I will put his example here: If $$M = \begin{pmatrix} 1 & 1 \end{pmatrix}$$, then both $$A = \begin{pmatrix} 0 & 1 \end{pmatrix}$$ and $$A = \begin{pmatrix} 1 & 0 \end{pmatrix}$$ satisfy $$\mathcal{M}_A = M = \mathcal{M}_B$$ despite $$A \neq B$$.

Assumption: From now on, we suppose $$M$$ is a data matrix for which there is exactly one corresponding picture matrix.

Question Given a data matrix $$M$$, what is the minimal number of entries of $$M$$ I need to know, such that I can find a unique picture matrix $$A$$ such that $$M = \mathcal{M}_A$$?

Is there any mathematics done on this problem already? If not, is there a similar problem where people have done research on it?

• This puzzle is similar to a nonogram, which you can solve via integer linear programming, as described in this blog post. Jan 3, 2020 at 2:16
• Nonograms are similarly interesting and it is good to know how to solve them. However, this does not seem to address my question about the minimality. Jan 3, 2020 at 2:26
• The minimum number of clues has been determined for Sudoku. Minesweeper is also similar to Fill-a-Pix and has been researched with respect to NP-completeness, but I don't know about minimality. Jan 3, 2020 at 2:39
• I don't think observation 2 is correct. For example for $\mathcal{M}_A = \begin{pmatrix} 1 & 1 \end{pmatrix}$ we could have $A = \begin{pmatrix} 0 & 1 \end{pmatrix}$ or $A = \begin{pmatrix} 1 & 0 \end{pmatrix}$, so $A$ is not always unique. Jan 3, 2020 at 10:15
• In fact, with minor exceptions, non-uniqueness applies to any matrix with $2$ rows (or $2$ columns), since $m_{1j} = m_{2j}$ for all $j$ and the $M$ matrix cannot distinguish (resolve) the different rows of $A$. Jan 3, 2020 at 13:49

Not an answer / just a long comment on non-uniqueness.

In fact, if the number of rows $$m$$, or the number of columns $$n$$, is of the form $$3k+2$$, then there exists $$M$$ matrices with multiple $$A$$ solutions. E.g. for $$n=8$$ here are three $$A$$ matrices:

01001001
01001001
01001001
01001001

10010010
10010010
10010010
10010010

10010010
10010010
01001001
10010010


which have the same $$M$$ matrix:

2222222
3333333
3333333
2222222


The underlying reason is that when $$n=3k+2$$, the $$mn$$ equations are not linearly dependent, since a single row (of length $$n$$) can be "decomposed" in two ways:

(..)(...)(...)
vs
(...)(...)(..)


so we have $$M_{i1} + M_{i4} + M_{i7} = M_{i2} + M_{i5} + M_{i8}$$ for every row $$i$$. Now, the $$mn$$ equations being linearly dependent means there can be multiple solutions in $$\mathbb{R}^{m\times n}$$, but the examples show there can also be multiple solutions even in $$\{0,1\}^{m\times n}$$.

Obviously, this doesn't answer the OP question, but in light of this, we might have to find a way to characterize which $$M$$ admits a unique solution $$A$$, before we ask the further question of when a partial view of such an $$M$$ also admits a unique solution $$A$$...?