<p>... or <strong>if you just want to have fun</strong> you can simply grab a lot of useful tips from other (powerful) Nonogram solvers; you can start from here:</p>

<p><a href="http://webpbn.com/pbnsolve.html" rel="nofollow">http://webpbn.com/pbnsolve.html</a> which will <em>teleport</em> :-) you to:</p>

<p><a href="http://webpbn.com/survey/" rel="nofollow">http://webpbn.com/survey/</a> and ...</p>

<p><a href="http://www.comp.lancs.ac.uk/~ss/nonogram/" rel="nofollow">http://www.comp.lancs.ac.uk/~ss/nonogram/</a> ...</p>

<p><a href="http://www.comp.lancs.ac.uk/~ss/nonogram/list-solvers" rel="nofollow">http://www.comp.lancs.ac.uk/~ss/nonogram/list-solvers</a></p>

<p>You can find detail descriptions of single-line / multi-line solving techniques and descriptions of more complex strategies.</p>

<p>When switching to 3D Nonograms single-line and multi-line strategies are still valid (apply 2D multi-line strategies on each <em>section</em> of your 3D puzzle); but if the 3D puzzle is difficult (or random), an iterated loop with those strategies ends up with many <em>unknown</em> pixels and to proceed you must apply specific 3D strategies. </p>

<p>If your question is more <em>TCS oriented</em>  then there are plenty of references in some public downloadable articles: <a href="http://www.google.it/search?as_q=nonogram+np&amp;as_filetype=pdf" rel="nofollow">http://www.google.it/search?as_q=nonogram+np&amp;as_filetype=pdf</a></p>

CC BY-SA 2.5
2011-01-25T22:58:44.643Z
2011-01-25T23:39:30.660Z
2011-01-25T23:39:30.660Z
Marzio De Biasi
<p>I would suggest to reduce it to a SAT problem (which should be trivial for this game, notice that each cell is a variable and that the constraints will form the clauses) and then use a modern SAT solver. You could search for a SAT solver which is good in solving satisfiable instances fast (this will always be satisfiable and will always have exactly one answer). You could check the <a href="http://www.satcompetition.org/" rel="nofollow">SAT competition website</a> for a fast solver.</p>

<p>Unless I totally misunderstood something, this should be enough for a fast problem solver.</p>

CC BY-SA 2.5
2011-01-25T21:30:49.977Z
2011-01-25T21:30:49.977Z
George
<p>I am currently working on a little project where I would like to write an efficient solver for three-dimensional Nonograms.</p>

<p><a href="http://en.wikipedia.org/wiki/Nonogram" rel="nofollow">http://en.wikipedia.org/wiki/Nonogram</a></p>

<p>So I wanted to ask whether anybody of you know a good way on how to solve a line in a normal 2D Nonogram. The problem is NP-complete btw so finding a robust algorithm that always does it will be quite hard ;-)</p>

<p>But does anybody of you have an idea? It doesn't need to solve everything possible but should do basic checks on a line and see if it can fill out something.</p>

<p>Would be  great if anybody could give me tips on how I could achieve this... thanks!</p>

CC BY-SA 2.5
2011-01-25T17:41:59.680Z
I didn't get it...Are you seeking an approximation algorithm? Or, you don't care if it takes exponential time; you just want it solved?
Sadeq Dousti
CC BY-SA 2.5
2011-01-25T17:57:55.833Z
right, I would like to solve it... and even if it takes exponential time... but I would also be fine with a method that doesn't detect everything possible but most cases where it can fill (parts) of a line...
florianbaethge
CC BY-SA 2.5
2011-01-25T18:20:06.367Z
You could check out this [theory of a nonogram solver](http://www.comp.lancs.ac.uk/~ss/nonogram/theory.html) page. I typed "nonogram solver" into Google and it was one of the first hits.
Aaron Sterling
<ds.algorithms>
Abstract machine or algorithm for line solving a Nonogram
florianbaethge
# Abstract machine or algorithm for line solving a Nonogram

(Asked by: username_0 on 2011-01-25)

I am currently working on a little project where I would like to write an efficient solver for three-dimensional Nonograms.

<http://en.wikipedia.org/wiki/Nonogram>

So I wanted to ask whether anybody of you know a good way on how to solve a line in a normal 2D Nonogram. The problem is NP-complete btw so finding a robust algorithm that always does it will be quite hard ;-)

But does anybody of you have an idea? It doesn't need to solve everything possible but should do basic checks on a line and see if it can fill out something.

Would be great if anybody could give me tips on how I could achieve this... thanks!

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I didn't get it...Are you seeking an approximation algorithm? Or, you don't care if it takes exponential time; you just want it solved?  
> **username_0**: right, I would like to solve it... and even if it takes exponential time... but I would also be fine with a method that doesn't detect everything possible but most cases where it can fill (parts) of a line...  
> **username_2**: You could check out this [theory of a nonogram solver](http://www.comp.lancs.ac.uk/~ss/nonogram/theory.html) page. I typed "nonogram solver" into Google and it was one of the first hits.  

---

## 2 answers

### Answer by username_3 on 2011-01-25. Score: 2 | Accepted answer

... or **if you just want to have fun** you can simply grab a lot of useful tips from other (powerful) Nonogram solvers; you can start from here:

<http://webpbn.com/pbnsolve.html> which will *teleport* :-) you to:

<http://webpbn.com/survey/> and ...

<http://www.comp.lancs.ac.uk/~ss/nonogram/> ...

<http://www.comp.lancs.ac.uk/~ss/nonogram/list-solvers>

You can find detail descriptions of single-line / multi-line solving techniques and descriptions of more complex strategies.

When switching to 3D Nonograms single-line and multi-line strategies are still valid (apply 2D multi-line strategies on each *section* of your 3D puzzle); but if the 3D puzzle is difficult (or random), an iterated loop with those strategies ends up with many *unknown* pixels and to proceed you must apply specific 3D strategies.

If your question is more *TCS oriented* then there are plenty of references in some public downloadable articles: <http://www.google.it/search?as_q=nonogram+np&as_filetype=pdf>


---

### Answer by username_4 on 2011-01-25. Score: 1

I would suggest to reduce it to a SAT problem (which should be trivial for this game, notice that each cell is a variable and that the constraints will form the clauses) and then use a modern SAT solver. You could search for a SAT solver which is good in solving satisfiable instances fast (this will always be satisfiable and will always have exactly one answer). You could check the [SAT competition website](http://www.satcompetition.org/) for a fast solver.

Unless I totally misunderstood something, this should be enough for a fast problem solver.


---

