[curtisf]

What do you mean by "purely with logic, no guessing"?

"Guess and backtrack" is a totally valid form of deduction for pen-and-paper puzzles, it's just not very satisfying. But often (always?) there is a satisfying deduction technique that could have replaced the guess-and-check, it may just be fairly obtuse.

Or do you just mean where the clues for the raster don't result in a unique solution?

[stagger87]

Not OP, but you don't ever have to guess and backtrack, you can always work out the next move. After playing about 100 boards several simple "rules" emerge which allow for this.

[vintermann]

Yes, 5x5 is small enough that all backtracking can be codified into easily human-accessible rules.

* 5, 0, 1 1 1, 2 2, 3 1 and 3 1 are immediately solved

* 4 lets you set 3 squares immediately

* 3, 2 1 and 1 2 let you set 1 square immediately

[jobigoud]

In summary the only ones that don't let you put a square immediately are "0", "1", "2" and "1, 1". And as soon as you put a square you can put some crosses (right click). In the end it becomes fairly mechanic.

[Ancapistani]

100 puzzles in, and I've not had the need for a manually-placed cross, either.

[jhanschoo]

Hot take: Some valid rules are just brute-force search in an altered state space.

For example, a valid "advanced" rule is this: consider a line, then consider all permutations of ways to complete it given the current state of the line. If a square is filled in/crossed out in all these permutations, then it you may fill it in/cross it out.

This is an O(n!) algorithm! In practice you only have <5 permutations.

[curtisf]

If I recall correctly, it's actually possible to implement this in O(n) (or maybe O(n^2)) time and space using a "dynamic programming" algorithm.

But in general, Nonogram solving, like most pen-and-paper puzzles, is NP-Complete for large enough puzzles, so even such a high-powered rule isn't guaranteed to completely solve a (large) puzzle.