Do most nonograms not require backtracking?

Question

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, because the process is sequential. Can anyone confirm that this is true? A quick google search tells me that solving the puzzles is NP-Complete, but I don't know if this refers to solving all puzzles (and determining no/unique solutions) or puzzles that are guaranteed a solution. I'm also interested in other types of puzzles that share this quality.

Answer 1

Yes, most nonograms are line solvable. But that is just because most of them are designed in such a way that a human can solve them. There are also examples of nonograms that are not line solvable, see for Example 4 in the section on symmetry on this page. However, these examples often look like they are build artificially and usually do not give nice pictures like the puzzles you find in various magazines.

Answer 2

All the nomograms I have done were line solvable. I have only done them from half a dozen sources, and there are many more available. I suspect that (almost) all the ones posted are line solvable, as it seems much easier to write a program to check that. You create the picture that you want, calculate the clues, and ask your solver to check that the puzzle is solvable. The solver then will insist the puzzle be line solvable. I don't think you can confirm this without checking all the programs out there, but I think it is likely.

It is quite possible that this spoils the NP-completeness of nomograms. One recurring feature to NP-complete problems is nonlocality-that the solution in one region can be forced by the solution in far away regions. As you can still have the solution at one end of a line be driven by the solution at the other, you might maintain NP-completeness.

I have said elsewhere that I don't think making a good puzzle depends on the complexity class. I think it depends on the amount of work to be done and the difficulty of analysis for the size of puzzle presented, not how it scales with size.