Are all Nonograms / griddlers uniquely solvable?

Question

A Nonogram (also called a Griddler) is a popular puzzle in which you are given a matrix of size $n \times m$ filled with zeros, and you are also given that in row $i$ there are $a_i$ ones and in column $j$ there are $b_j$ ones.

This is explained more throughly here https://en.wikipedia.org/wiki/Nonogram It is a fun, popular, and rather simple to understand puzzle.

My question is a simple one - Are all (legit) Griddlers uniquely solvable? Do all such matrices correspond to one picture? or is it possible to construct a grid that corresponds to more than one picture?

By legit grids, I mean that it is possible to find at least one solution. It is a proper grid. There is no situation for example where we have a matrix with $10$ and $10$ columns but we are given that in the first row there are $11$ ones.

Also, are there Grids where a solution exists but it is impossible to find it?

Edit: If a solution exists, it is always possible to find it. The reason is that in a $n$ by $m$ grid there are $2^{nm}$ possible states. At least one of them will be a solution if a solution exists.

Answer 1

For a grid with even side lengths a checkerboard pattern is not uniquely defined by the clues - both checkerboard colourings give the same clues.

If there is a unique solution it is possible to find it by exhaustive search. Only one pattern will fit.

Answer 2

The row and column descriptions of the following two grids are the same: $$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. $$

Answer 3

The likelihood of unique solution increases with the degree to which it is populated, i.e. the fraction of the grid that has 1's. The level of difficulty follows the same trajectory: the more 1's, and the more long runs of 1's, the easier it is to solve.

Consider a trivial example, one row of 10 squares. If the description is (10), (1,8), (2,7), (3,6), (4,5), or more, smaller runs (e.g. 1,3,4), there is only one way to fill the row.

If there are just small numbers, there will be many ways to place the 1's. (e.g. (1,1) has 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 ways.)

Based on a fairly limited sample of randomly generated puzzles, I would give the following guidelines:

• Under 50% 1's - very high probability of ambiguity, very hard to solve.
• 50-55% 1's - reasonable chance of unique solution
• 55%-60% 1's - high probability of unique solution
• Above 60% - unique solution is almost certain, fairly easy to solve.

In many cases, you can get a "nearly unique" solution, such as one or two embedded 1 - 0 / 0 - 1 possibilities across two rows and two columns, which need not be adjacent. (In other words, a generalization of the answer by Chappers.)

Answer 4

I have found plenty of examples while playing popular Google Play Store versions of Nonograms that there are often scenarios where working toward a solution results in 4 unchecked grid spaces, that form the corners of a square or rectangle. Sometimes these can be solved by filling 'either' pair of opposite corners.

Most are unique but the opposite corner scenario is one I come across frequently.