3 ms·

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

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?

stagger87 1y 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.
- vintermann 1y ago
  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
  - jobigoud 1y ago
    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.
    - Ancapistani 1y ago
      100 puzzles in, and I've not had the need for a manually-placed cross, either.
- jhanschoo 1y ago
  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.
  - curtisf 1y ago
    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.
deleted 1y ago
[deleted]

stagger87 1y 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.

vintermann 1y ago
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
- jobigoud 1y ago
  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.
  - Ancapistani 1y ago
    100 puzzles in, and I've not had the need for a manually-placed cross, either.
jhanschoo 1y ago
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.
- curtisf 1y ago
  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.

deleted 1y ago

[deleted]