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.
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.