24
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ You want an algorithm that you can do with pen and paper or with a computer? $\endgroup$
    – Dr Xorile
    Jan 9 '16 at 14:25
  • $\begingroup$ The former is better. However, computer algorithm is allowed unless it is just a bruteforce. $\endgroup$
    – Xwtek
    Jan 9 '16 at 14:31
  • $\begingroup$ With dynamic programming you could presumably spit out all the solutions pretty quickly. But you don't want that? $\endgroup$
    – Dr Xorile
    Jan 9 '16 at 15:24
  • $\begingroup$ @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 $\endgroup$ Jan 9 '16 at 16:31
  • 2
    $\begingroup$ 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). $\endgroup$ Jan 10 '16 at 20:17
1
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – DrunkWolf
    Jan 23 '16 at 11:18
  • 1
    $\begingroup$ I am on it, I will edit it after I got a solid proof. $\endgroup$
    – Oray
    Jan 23 '16 at 11:25
  • 1
    $\begingroup$ How about nonsymmetric nonogram. $\endgroup$
    – Xwtek
    Feb 2 '16 at 12:49
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 30 '18 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.