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.
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.
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.
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.
vintermann|9 months ago
* 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|9 months ago
jhanschoo|9 months ago
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|9 months ago
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.