I've just started learning CSP and I find it quite exciting. Now I'm facing nonogram solving problem and I want to solve it using backtracking with CSP.

The first problem that I face is that I cannot quite figure out what such variables, domains, and constraints could be. My first thought was to make every field(those squares) a variable with such domain: $D_i = \{1,0\}$, where 1 means that certain field has been colored black and 0 white.

So far I've been mostly learning binary constraints, and I was thinking of using the AC-3 or forward checking algorithm for propagation during the backtracking algorithm.

As far I know constraints of all arity can be represented as a set of binary constraints, so that would enable me to use algorithms I mentioned. But that leads me to the problem of defining constraints. If every field was a variable then each line and column would be a constraint, based on how certain lines should be colored(numbers defining line for example 2,3,2).

But it's all new and quite hard for me to imagine and come up with. I've been reading some articles and papers on that but they were too advanced for me.

So, does anybody have an idea how can I formulate a nonogram problem as a constraint satisfaction problem?

  • $\begingroup$ You are trying to both learn to formulate the problem and write a solver at the same time. Have you tried formulating the problem in an existing solver (eg Minion)? This way you get practice formulating problems before you work on implementing solvers. $\endgroup$ – Nathan S. Mar 31 at 16:35
  • $\begingroup$ I try to implement a simple solver to understand algorithms and heuristics behind. That gave me better understanding how it all works. $\endgroup$ – Karol Apr 1 at 22:50
  • 1
    $\begingroup$ But after all, I decided that, a variable will be a single row or column and their domains are every possible combination od that linę. Not very powerful but you have to start somewhere. $\endgroup$ – Karol Apr 1 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.