# 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. Commented 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. Commented 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. Commented 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. Commented 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$. Commented 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$$...?