Is there an algorithm to decide that the nonogram puzzle is unique

Question

A good nonogram puzzle has a unique solution. However, some nonograms do not. For example, this puzzle:

Has at least two solutions, shown below:

      211 
    1311231
  1 *------
  3 --***--
2 1 -**--*-
1 1 -*---*-
1 2 -*--**-
  3 --***--
  1 ------*
  211 
1311231

1 ------
  3 ----
2 1 ----
1 1 -----
1 2 ----
  3 ----
  1 ------

Is there an algorithm to decide that the puzzle has a unique solution that is more efficient than trying to solve it?

You want an algorithm that you can do with pen and paper or with a computer? — Dr Xorile, Jan 09 '16 at 14:25
The former is better. However, computer algorithm is allowed unless it is just a bruteforce. — Xwtek, Jan 09 '16 at 14:31
With dynamic programming you could presumably spit out all the solutions pretty quickly. But you don't want that? — Dr Xorile, Jan 09 '16 at 15:24
@DrXorile I think the OP is looking for algorithms or formulae that don't actually solve it. Just like for example this formula for checking for solvability of slide puzzles — Ivo, Jan 09 '16 at 16:31
Probably not, since determining whether a Nonogram has a solution is NP complete, as is determining whether a Nonogram had an additional solution given a puzzle and a solution (see here, page 29). — Mike Earnest, Jan 10 '16 at 20:17

score 1 · Answer 1 · answered Jan 23 '16 at 10:33

1

if the rows and columns are symmetric and you cannot find any black square from a row and from a column only, it is not unique and there is at least one more solution.

answered Jan 23 '16 at 10:33

Oray

30,307
6
61
215

3

It would be nice if you could edit your statement to include proof that this is the case, and that this covers all the cases (if it does) and how you got to it. – DrunkWolf Jan 23 '16 at 11:18
1

I am on it, I will edit it after I got a solid proof. – Oray Jan 23 '16 at 11:25
1

How about nonsymmetric nonogram. – Xwtek Feb 02 '16 at 12:49
2

What does "find any black square from a row and from a column only" mean? It is trivial to generate a symmetric puzzle with a unique solution (ex. every square is black). – BlueRaja - Danny Pflughoeft Apr 30 '18 at 13:50

Is there an algorithm to decide that the nonogram puzzle is unique

1 Answers1