Hacker News new | ask | show | jobs
by stagger87 381 days ago
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.
2 comments

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

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.
100 puzzles in, and I've not had the need for a manually-placed cross, either.
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.