News for hackers. Stuff that matters.
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.