19
$\begingroup$

A good nonogram puzzle have unique solution. However, some nonogram is not. For example

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

Have at least two solutions

      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 algorithm to decide that the puzzle have unique solution that is more efficien than trying to solve nonogram? Give me the proof/algorithm

$\endgroup$
  • $\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$ – Akangka 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$ – Ivo Beckers 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$ – Mike Earnest Jan 10 '16 at 20:17
2
$\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$
  • 2
    $\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$ – Akangka Feb 2 '16 at 12:49
  • $\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 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.