1
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Jan 25, 2011 at 17:41
  • $\begingroup$ 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... $\endgroup$ Jan 25, 2011 at 17:57
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 25, 2011 at 18:20

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 for a fast solver.

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

$\endgroup$

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.