# Abstract machine or algorithm for line solving a Nonogram

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!

• 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? Jan 25, 2011 at 17:41
• 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... Jan 25, 2011 at 17:57
• You could check out this theory of a nonogram solver page. I typed "nonogram solver" into Google and it was one of the first hits. Jan 25, 2011 at 18:20

... 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/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.