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.
Best Answer
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.