How many possible starting positions are uniquely solvable for a nonogram puzzle?

Question

This type of puzzle goes by many names: Nonogram, Picross, and Griddlers are all mentioned on the Wikipedia page, Simon Tatham calls it Pattern, I was introduced to it as Descartes Rainbow, ...

The puzzle starts with a given arrangement of numbers around a grid. Let's assume it's a square, $n\times n$ grid, and that the pattern is a simple black and white one, no colours. Every possible pattern of black cells in the $n\times n$ grid gives some arrangement of numbers, but there are some different patterns which give the same arrangement of numbers. A good puzzle starts with an arrangement of numbers which has one unique solution. But if I choose a random (solvable) starting problem, what's the probability that it will have a unique solution?

Among all possible starting positions, how many have a unique solution?

_{Important note: I don't know the answer to this question. I don't even know if anyone knows: it could be an open mathematical problem. I'm also not expecting it to be an easy thing to answer off the cuff: it's more likely to be something found in a mathematical paper or so. But we have a good subcommunity of maths puzzle gurus here, and maybe someone will be better able to find the answer than I.}

Answer 1

Absurdly partial answer

Terminology: an "inner configuration" is an arrangement of filled and empty cells in our $n\times n$ grid; an "outer configuration" is the corresponding arrangement of run-lengths displayed outside the grid. Let $I_n=2^{n^2}$ be the number of possible inner configurations, $O_n$ be the number of distinct outer configurations arising from these, and $U_n$ be the number of these corresponding to a unique inner configuration. The question asks for $p_n:=U_n/O_n$; I suspect $q_n:=U_n/I_n$ may be less impossible to find, though probably both are hard. Obviously $O_n\leq I_n$ and so $q_n\leq p_n$.

For $n=0$: obviously $I_0=O_0=U_0=1$ so $p_0=q_0=1$.

For $n=1$: there are just two inner configurations, and each corresponds to a different outer configuration. So $I_1=O_1=U_1=2$ and $p_1=q_1=1$.

For $n=2$: there are two "bad" configurations, the ones with two diagonally-opposite empty cells. All other configurations either have an asymmetry making them easily solvable, or have all cells in the same state which is also easy. So $I_2=16,O_2=15,U_2=14$ and therefore $p_1=\frac{14}{15},q_1=\frac{7}{8}$.

The sequence of $U_n$ is A242876 in OEIS. Not very many terms are computed there, which suggests (at least) that others agree with my feeling that this is a hard problem.

Answer 2

Answer in construction

From an algorithm point of view, the ways you can attempt to crack the problem are either too strenuous for decent results in an amount of time or redundant in comparison to a decent mathematician... so I don't expect anything useful to be yielded from using a computer algorithm.

That said, I have a simple starting point that may or may not be useful in the long run

Lets consider that a Nonogram can be represented as bits where $1=coloured$ etc. Nonagrams contain numbers outside the grid (lets casually call this $A_x$, where $A_x$ is an array of $S$ length) which validly represent the bits in the respective row or column. It is possible to determine if a Nonogram is unique by finding if there are other solutions that have the exact same $A_x$. Obviously, it is difficult to do this mathematically, lets break the problem down and see if it gets us anywhere {I intend for my answer to help others reach a final, accepted answer (if that even exists). I probably won't be able to continue past a certain level of maths}

---

Lets start by just thinking of a single trail of bits (called $B_i$). This trail is of length $N$ and can be represented by $A_x$. How many combinations of $B_i$ share $A_x$? It is easy to see that for $A_x$ with $S = 1$ there are $N-A_1+1$ of $B_i$. For $S>1$ it gets complicated since there can be a variable number of $0$ bits padding between $1$ clusters. What is certain is that there is always at least one $0$ bit between clusters. Consider a strategy where the padding can be distributed in many combinations. Let $T = \sum\limits_{r=1}^{S}A_r$ and $D=N-T$. The difference $D$ represents the total padding between clusters, it can be distributed for the $S+1$ paddings in between clusters in different ways. There are $S-1$ paddings that must be a size of at least one. This leaves $D-S+1$ to be distributed between all $S+1$ padding. The formula for this would then be ${D+1} \choose {S}$

So $A_x$ has ${N+1-\sum\limits_{r=1}^{S}A_r} \choose {S}$ corresponding $B_i$ of length $N$.

This also implies that $N+1-\sum\limits_{r=1}^{S}A_r=S$ when there is only one unique $B_i$. This tells us that ALL valid Nonograms, where all of the rows and columns satisfy this rule, have a unique solution! (for future reference, lets call these stuffed Nonograms)

---

Lets have a closer look into the stuffed Nonograms since it may give us a very vague idea of what the final function (if it exists) will look like. An equation to identify stuffed Nonograms can be derived if we rearrange the rule to $N=S-1+\sum\limits_{r=1}^{S}A_r$. The square Nonogram will have $2N$ of $B_i$ that follows this rule so by summing everything, $2N^2=\sum\limits_{i=1}^{2N}(S_i-1+\sum\limits_{r=1}^{S_i}A_{i_r})$ or the nicer equation $2N^2+2N=S_T+A_T$ using $S_T$ and $A_T$ to represent the amount of total items $A_x$ and the summation of all of them respectively. There is a constraint that $S_T\geq2N$ and $A_T\geq2N$.

Logically it can be concluded that stuffed Nonograms are Nonograms that have a completely/almost full unique grid as the solution. They have peppered padding of length one (single holes). This can be proven by revisiting $B_i$. Let $B_i$ have $C$ padding of one so that $T = N - C$ and $S = C + 1$. Subbing into $N+1-T=S$ we see no contradiction since $N+1-(N-C)=C+1$ so $C+1=C+1$ $\therefore$ peppered padding of one is always unique! There is an indirect implication that there cannot be any front or back padding (since it creates more solutions) so stuffed Nonograms must at least have a full outer rim of one. It is for this reason that the only area of stuffed Nonograms with importance is $(N-2)^2$. Now consider this; if the area is unwound to become many $B_i$ and the placement of the peppered padding is considered in a converse way of thinking then the amount of corresponding $B_i$ from $A_x$ formula can be repurposed to count the total amount of stuffed Nonograms possible. The formula will initially over approximate since the rewrapping of some $B_i$ configurations will lead to alignment of padding resulting in padding of length greater than one which is invalid. To overcome this, an extra formula that counts the number of invalid wraps must be developed.

Edit: The following two paragraphs are now redundant since I've managed to find what appears to be the solution by changing my approach. The paragraphs are still necessary to fully understand the tech used in my new approach so for historic reasons I'm keeping them for the now. (Thinking of shortening this answer by moving the "holes in grid" problem into its own Q&A question)

Lets over approximate. Consider a single $B_i$, the padding is all of length one so all of $A_x$ (in this perspective) will contain $1$. $S$ can vary from $0\to \lceil\frac{N-2}{2}\rceil$ (thanks odd numbers) and $T=S$. The formula for the amount of possible $B_i$ must then be $\sum\limits_{r=0}^{\lceil\frac{N-2}{2}\rceil} {{(N-2)+1-r} \choose {r}}$. This is actually equivalent to the Fibonacci series (thanks to @justhalf's insight). The function $Fi(x)$ will be used to represent the series from now on. There is $N-2$ of $B_i$ in the relevant area which can have different combinations at once. This is the same as a combination lock of length $N-2$ so the overall formula for the amount of configurations in this case is $Fi^{(N-2)}(N)$.

Now to count all of the invalid wraps. Lets use an easy model and say that the $B_i$ are stacked on top of each other. Invalid wraps must occur when a padding of length greater than one is created from stacking $B_i$ that have padding which align. Alignment can only happen between neighbour $B_i$ and all that is required is for padding to exist at the same position locally within the two $B_i$. Take $G$ to equal the amount of $B_i$ and $L$ to equal the length of all $B_i$ (just incase we can revisit this formula). There are $G-1$ seams between $B_i$ where alignment can occur and it is possible for more than one set of neighbour $B_i$ to align at once.

Edit: This is the new approach

Lets consider the valid combinations at one seam. In order for valid combinations to happen the padding must never overlap. Lets say that the top $B_i$ at this seam can be anything where it is valid within itself. It is logical to conclude that the bottom $B_i$ must only be valid when its own padding is contained within the clusters of the top $B_i$ whilst still being internally valid. It is for this reason that the bottom $B_i$ can be considered as any $A_x$ that fragments into small locally valid $B_i$! We can now further abuse the $A_x$ formula! The formula currently depends on arrangement of $A_x$ so to fix that to make the combinations countable it is now ${{L+1-\sum\limits_{r=1}^{S}A_r} \choose {S}}S!$ (permutations). The clusters can all be any combination of locally valid $B_i$ so this is $\prod\limits_{i=1}^{S}Fi(A_i+2)$. This gives us the final formula for the seam combinations (for $A_x$) to be ${{L+1-\sum\limits_{r=1}^{S}A_r} \choose {S}}S!\prod\limits_{i=1}^{S}Fi(A_i+2)$. The total combinations can be found by summing combinations for $A_x$'s. Initially, I thought it wouldn't be possible to account for multi-seam combinations however I think that by inversion, the next seam in the stack has the same possible combinations regardless of the affects of the seam beforehand. This would create a simple combination lock of length $G$. I will be thoroughly impressed if anyone manages to put the whole formula together!

---

Another group of unique, valid Nonograms exists that can immediately be counted. The group consists of Nonograms where the rows/columns can only be completely full, empty or something inbetween (the latter arises from the overlap of rows and columns that are full or empty which creates a 'different image'). For future reference, lets call these net Nonograms.

Anyone familiar with solving Nonograms will know how useful completely full/empty rows/columns are. It is a good idea to take this concept to its extremes because it may be used as a part of the final solution to split Nonograms into smaller Nonograms (well, it is way more complicated than that but still). Consider just the rows of net Nonograms, it is possible to use binary to represent the information. It is for this reason that $2^N$ is the amount of combinations of rows. The same can be said for the columns. If the information for the rows and columns is 'overlapped' then we have $2^{2N}-2$ total net Nonograms! The $-2$ takes into account the two repeated combinations (all full or all empty). Gonna need proof for how overlap is resolved and why it still leads to unique, valid Nonograms but I think it is safe to say that this was a simple idea for the books...

---

Ideas

This section is going to be used to document facts/ideas ranging from basic to abstract, I just want to put concepts on the record so that this can be used as a helpful guide when looking for the answer.

• The final function will be a recurrence relation.
• The answer to "How many invalid solutions exist for $A\times B$ Nonograms with a specific set of $A_x$?" will inevitably lead to the answer for "How many valid solutions for an $N\times N$ Nonogram exists?" and "How many unique $N\times N$ Nonograms exist?"
• The answer to the above "invalid solutions exist..." will likely contain recursion.
• The groups of Nonogram currently defined in my 'answer' both tend to zero as $N\to \infty$ when considering the approximate probability of the groups out of all possible random configurations $2^{N^2}$

Answer 3

This is an attempt to answer your secondary question:

[I]f I choose a random (solvable) starting problem, what's the probability that it will have a unique solution?

---

One answer is found in the paper On Determining Paint by Numbers Puzzles with Nonunique Solutions by Ryan Mullen (Journal of Integer Sequences, vol. 12, 2009, Article 09.6.5).

A natural starting approach to try to solve a nonogram is to see whether the colors of any cells in a row (or column) are determined by the sequence of numbers given for that row (or column), which shall be called a "hint sequence". The worst-case scenario is that no cell in a row has its color determined by its hint sequence (in which case one is compelled to use the data from the columns and the rest of the rows). With this motivation, the author makes the following definition:

We define a forceless sequence to be a sequence such that no partial coloring can be determined without the aid of the rest of the puzzle.

If a nonogram puzzle has $n$ columns, how many forceless sequences are possible? Denote this number by $G_n$. The first few values of $G_n$ are listed in the OEIS entry A304179. The author also shows (see Theorem 2.1) that the number of hint sequences possible for an $n$ column puzzle is $F_{n+2}$, where $(F_n)_{n \geq 1}$ is the Fibonacci sequence given by $$ F_1 = F_2 = 1, \quad F_{n} = F_{n - 1} + F_{n - 2} \text{ for all } n \geq 2. $$ Thus, the probability that a hint sequence of an $n$ column puzzle (picked uniformly at random from the set of all possible $n$-column hint sequences) is a forceless sequence is $G_n/F_{n+2}$.

Now, the author provides estimates for the growth of $G_n$ as follows (see Theorems 3.1 and 3.2): there exist constants $c_1, c_2 > 0$ such that $$ c_1 \frac{\phi^n}{n} \leq G_n \leq c_2 \frac{\phi^n \ln n}{n} $$ for all $n \geq 2$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. In the paper The Asymptotics of Useless Hint Sequences in Nonograms, by Daniel Berend and Shira Zucker (Journal of Integer Sequences, vol. 21, 2018, Article 18.4.2), the authors tightened the above estimates to show that there exist constants $C_1, C_2 > 0$ such that $$ C_1 \frac{\phi^n}{n} \leq G_n \leq C_2 \frac{\phi^n}{n} $$ for all $n \geq 1$. Since it is known that the Fibonacci sequence grows as $F_{n} \approx \phi^n / \sqrt{5}$, the probability $G_n / F_{n+2}$ grows as $1/n$ upto some multiplicative constant (i.e., $G_n/F_{n+2} = \Theta(1/n)$).

---

A different model of randomness is considered in the paper Nonograms: Combinatorial questions and algorithms by Daniel Berend, Dolev Pomeranz, Ronen Rabini, and Ben Raziel (Discrete Applied Mathematics, vol. 169, 2014, pp. 30–42). In this paper, the authors primarily develop an improved algorithm for a "line-solver", that is, an algorithm that takes a row (or column) hint sequence as an input and finds out which cells in that row (or column) have their colors determined, as well as what those colors should be.

Additionally, they establish that for a "randomly" chosen $n \times n$ puzzle, it is highly likely for large $n$ that a line solver is unable to determine the color of even one cell. Specifically, they use the following definition of a "random" puzzle:

Our interpretation is that we start with an uncoloured grid, and colour each cell in white or black with probabilities of $1/2$ each, distinct cells being independent. … Note that this is very different from taking all puzzle descriptions and picking one of them uniformly at random. (The latter possibility is more in line with Mullen’s interpretation of randomness for single lines.) To emphasize the difference, we shall henceforth refer to our version of a random puzzle as a randomly generated puzzle. (Namely, the grid is coloured uniformly at random, but some puzzles have a much larger probability of being obtained than others.)

With the above definition, the authors prove the following:

Theorem 2. Let $C$ be the number of cells of an $n \times n$ randomly generated puzzle whose colour is determined by a line solver. Then $P(C = 0) \underset{n \to \infty}{\longrightarrow} 1$ exponentially fast.

This is obviously a very different estimate from the one mentioned previously due to Mullen and Berend–Zucker, but there is no contradiction because the probability spaces in these two cases are quite different.

The authors also establish a probabilistic estimate for how many $m \times n$ puzzles have multiple solutions.

Theorem 4. There exist effective positive constants $\delta, \varepsilon > 0$ such that the probability of a randomly generated $m \times n$ puzzle ($m, n \geq 2$) to have less than $2^{\delta m n}$ solutions is less than $2^{−\varepsilon m n}$.

In particular, their proof shows that

the theorem is valid with the choices $\delta = 2^{−18}$, $\varepsilon = 2^{−20}$.

So, if a nonogram puzzle is picked randomly by picking a picture in the $m \times n$ grid uniformly at random, then (for large puzzles) it is highly unlikely that a randomly picked puzzle does not have many solutions.

---

Addendum

This question seems to be fairly complicated. For instance:

• In contrast with Theorem 2 of Berend–Pomeranz–Rabini–Raziel mentioned above, their Theorem 3 shows that if one considers all the hint sequences together, then there is at least one cell whose color can be specified with a probability bounded away from zero:

  Theorem 3. For sufficiently large $m$ and $n$, a randomly generated $m \times n$ puzzle has, with probability at least $1/6$, at least one cell whose colour is uniquely determined. Moreover, one can find such a cell (with probability at least $1/6$) in constant time.

• Solving a general nonogram is known to be NP-hard, though it is possible to find fast algorithms in special cases (Kees Joost Batenburg and Walter A. Kosters, Solving nonograms by combining relaxations, Pattern Recognition, vol. 42, 2009, pp. 1672–1683).
• Suppose a specific nonogram is known to have a solution. Determing whether the solution is unique is an NP-complete problem (Nobuhisa Ueda and Tadaaki Nagao, NP-completeness Results for NONOGRAM via Parsimonious Reductions, Technical Report TR96-0008, Tokyo Institute of Technology, 1996).
• To the best of my knowledge, there is no known recurrence (let alone one that is amenable to efficient computation) for the number of $n \times n$ nonograms that have unique solutions, most probably because it is not known how (and whether) one can generate every $n \times n$ nonogram with a unique solution by piecing together information from smaller nonograms. This would explain why there are very few entries in the OEIS entry A242876 mentioned in Gareth McCaughan's answer.

All in all, my intuition is that it is, at best, quite optimistic to hope for an exact count for the number of $n \times n$ nongrams that are uniquely solvable. Probabilistic estimates are more feasible, in my opinion.

Answer 4

I doubt it could be calculated exactly except for very small grids, but it should be possible to Monte Carlo it.

One has to be careful about bias. I don't think there is any way to choose the numbers directly such that all solvable number patterns are equally likely.

Instead you could choose a random grid picture such that every picture is equally likely (i.e. each cell 50% probability of black). Take the corresponding number pattern, and see how many solutions it has by running it through a solver. Of course this selection method will be biased towards number patterns with multiple solutions, so to compensate you can give this a weight of $1/k$, where $k$ is the number of solutions.

Then you just generate lots of random bit grid patterns. Let $t$ be the total weight of all the patterns produced, and $u$ the total weight of the uniquely solvable patterns encountered. Then $u/t$ should approach the probability you are looking for if you go on long enough.