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

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

      211
1311231
1
3
2 1
1 1
1 2
3
1


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? Jan 9 '16 at 14:25
• The former is better. However, computer algorithm is allowed unless it is just a bruteforce. Jan 9 '16 at 14:31
• With dynamic programming you could presumably spit out all the solutions pretty quickly. But you don't want that? Jan 9 '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 Jan 9 '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). Jan 10 '16 at 20:17