26
$\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?

Improve this question
$\endgroup$
5
  • $\begingroup$ You want an algorithm that you can do with pen and paper or with a computer? $\endgroup$
    – Dr Xorile
    Commented Jan 9, 2016 at 14:25
  • $\begingroup$ The former is better. However, computer algorithm is allowed unless it is just a bruteforce. $\endgroup$
    – Xwtek
    Commented Jan 9, 2016 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
    Commented Jan 9, 2016 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$
    – Ivo
    Commented Jan 9, 2016 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$
    – Mike Earnest
    Commented Jan 10, 2016 at 20:17

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 23, 2016 at 11:18
  • 1
    $\begingroup$ I am on it, I will edit it after I got a solid proof. $\endgroup$
    – Oray
    Commented Jan 23, 2016 at 11:25
  • 1
    $\begingroup$ How about nonsymmetric nonogram. $\endgroup$
    – Xwtek
    Commented Feb 2, 2016 at 12:49
  • 2
    $\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$
    – BlueRaja - Danny Pflughoeft
    Commented Apr 30, 2018 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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