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