News for hackers. Stuff that matters.
Re:Every 5x5 Nonogram by curtisf on Saturday May 31, 2025 @01:52AM (#44142131)
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?

Re:Every 5x5 Nonogram by stagger87 on Saturday May 31, 2025 @02:22AM (#44142250)
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.
Re:Every 5x5 Nonogram by vintermann on Saturday May 31, 2025 @03:18AM (#44142546)
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

Re:Every 5x5 Nonogram by jobigoud on Saturday May 31, 2025 @08:00AM (#44143672)
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.
Re:Every 5x5 Nonogram by Ancapistani on Saturday May 31, 2025 @07:48PM (#44147713)
100 puzzles in, and I've not had the need for a manually-placed cross, either.
Re:Every 5x5 Nonogram by jhanschoo on Saturday May 31, 2025 @06:52AM (#44143400)
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.

Re:Every 5x5 Nonogram by curtisf on Saturday May 31, 2025 @09:07AM (#44144042)
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.