4 ms·

I don't know exactly how okayestjoel's solver works, but here's an example of a nonogram which I imagine it would consider "difficult": 1 1 1 2 1

I don't know exactly how okayestjoel's solver works, but here's an example of a nonogram which I imagine it would consider "difficult": 1 1 1 2 1 1 2 1 2 . . . . . 2 . . . . . 11 . . . . . 2 . . . . . 11 . . . . . This puzzle has a unique solution (141a706), but none of the clues immediately tell you anything about the state of any specific cell.

gus_massa 1y ago
Thanks, it's a nasty example. [spoiler alert] Naming the coumns ABCDE from left to right, and the rows 12345 from top to bottom. Let's consider B2 near the top left. If B2 full: Then B1 is empty because B has "only" ones. Then the "two" block in row 1 must make D1 full. Then D2 is also full because D has a "two". Now B2 and D2 are full, but that's impossible because B has only a "two". So the B2 must be empty. From that point it's possible to fill all the others without "guessing". So no branches and 3 steps to get a contradiction. I can run that in my head, so I call it "thinking" instead of "backtracking".
- qbane 1y ago
  If you assume that a cell is full and then get a contradiction, this is pretty much a backtracking to a computer. So it is reasonable that the solver does not do this trick.
  - gus_massa 1y ago
    I agree they are the same. It's just that if the try is short enough, I consider it a valid trick.
- duskwuff 1y ago
  Now I wonder if there are any 5x5 nonograms which can be proven to require multiple levels of backtracking, i.e. where you have to make at least two guesses before reaching a contradiction, no matter where you put those guesses.
  - SkiFire13 1y ago
    This nonogram should require at least 2 guesses, no matter where you put them: 1 1 1 1 1 1 2 1 2 . . . . . 2 . . . . . 11 . . . . . 11 . . . . . 1 . . . . .
    - barbarr 1y ago
      That puzzle has two solutions no? 1 1 1 1 1 1 2 1 2 x x . . . 2 . . x x . 11 x . . x . 11 . x . . x 1 . . x . . and 1 1 1 1 1 1 2 1 2 x x . . . 2 . . x x . 11 . x . x . 11 x . . . x 1 . . x . . (found these with an SMT solver :D)
okayestjoel 1y ago
I think you're exactly right. I might be being a little loose with the terminology here. "Well-formed" may be a better term than "solvable" for what I consider a valid puzzle. Even if a computer program can find the solution to one of these difficult puzzles, it would be a very frustrating experience for a human player in most cases. For small 5x5 sizes you could get away with it, though imagine a larger 25x25 puzzle where you have to make one of these branching decisions (a guess) early on. Some may enjoy this challenge, though from my experience of running a nonogram game for 15 years I can tell you most will not. I'm a little underwater handling the surge of traffic to my game, though when I get a quiet moment I'll run my solver so I can give some more precise answers. Basically my solver iterates over every row and column, marking cells that must be empty and painting cells that must be filled by going over every possible configuration for that row or column and finding the overlap. It does this in multiple passes and generally the more passes it takes, the more challenging the puzzle is. If it makes a pass and is unable to mark or paint any additional cells, then it considers the puzzle to be invalid if the end state is not solved (all clues are not satisfied). I do find this discussion really interesting. Maybe I should have reserved "Section 666" for these puzzles with unique solution but require a branching strategy :).
- duskwuff 1y ago
  Out of curiosity, are you familiar with Simon Tatham's Portable Puzzle Collection [1]? It includes a nonogram puzzle, under the name "Pattern" - I believe it guarantees that the puzzles are solveable without backtracking. It can generate puzzles up to 40x40 or so in a reasonable amount of time. [1]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
  - okayestjoel 1y ago
    Yes, I am familiar! I didn't play his games growing up, but I see it as a great reference for various logic puzzle game implementations and one of the few examples of quality logic puzzle collections. I think one thing missing from my 5x5 puzzle thing is that good nonograms are not just those that have a unique solution and require no guessing, but also create a compelling image when the puzzle is complete. My game, Pixelogic, features user-submitted puzzles in addition to in-house ones, and I'm often blown away how creative the pixel art creations are given the constraints of solvability under my game's standards and just on and off pixels. I wrote about what makes a good nonogram puzzle (in my opinion) in my weekly nonogram newsletter, if anyone is interested: https://weekly.pixelogic.app/p/pixelogic-weekly-4 https://weekly.pixelogic.app/p/pixelogic-weekly-4

gus_massa 1y ago

Thanks, it's a nasty example. [spoiler alert] Naming the coumns ABCDE from left to right, and the rows 12345 from top to bottom. Let's consider B2 near the top left. If B2 full: Then B1 is empty because B has "only" ones. Then the "two" block in row 1 must make D1 full. Then D2 is also full because D has a "two". Now B2 and D2 are full, but that's impossible because B has only a "two". So the B2 must be empty. From that point it's possible to fill all the others without "guessing". So no branches and 3 steps to get a contradiction. I can run that in my head, so I call it "thinking" instead of "backtracking".

qbane 1y ago
If you assume that a cell is full and then get a contradiction, this is pretty much a backtracking to a computer. So it is reasonable that the solver does not do this trick.
- gus_massa 1y ago
  I agree they are the same. It's just that if the try is short enough, I consider it a valid trick.
duskwuff 1y ago
Now I wonder if there are any 5x5 nonograms which can be proven to require multiple levels of backtracking, i.e. where you have to make at least two guesses before reaching a contradiction, no matter where you put those guesses.
- SkiFire13 1y ago
  This nonogram should require at least 2 guesses, no matter where you put them: 1 1 1 1 1 1 2 1 2 . . . . . 2 . . . . . 11 . . . . . 11 . . . . . 1 . . . . .
  - barbarr 1y ago
    That puzzle has two solutions no? 1 1 1 1 1 1 2 1 2 x x . . . 2 . . x x . 11 x . . x . 11 . x . . x 1 . . x . . and 1 1 1 1 1 1 2 1 2 x x . . . 2 . . x x . 11 . x . x . 11 x . . . x 1 . . x . . (found these with an SMT solver :D)

okayestjoel 1y ago

I think you're exactly right. I might be being a little loose with the terminology here. "Well-formed" may be a better term than "solvable" for what I consider a valid puzzle. Even if a computer program can find the solution to one of these difficult puzzles, it would be a very frustrating experience for a human player in most cases. For small 5x5 sizes you could get away with it, though imagine a larger 25x25 puzzle where you have to make one of these branching decisions (a guess) early on. Some may enjoy this challenge, though from my experience of running a nonogram game for 15 years I can tell you most will not. I'm a little underwater handling the surge of traffic to my game, though when I get a quiet moment I'll run my solver so I can give some more precise answers. Basically my solver iterates over every row and column, marking cells that must be empty and painting cells that must be filled by going over every possible configuration for that row or column and finding the overlap. It does this in multiple passes and generally the more passes it takes, the more challenging the puzzle is. If it makes a pass and is unable to mark or paint any additional cells, then it considers the puzzle to be invalid if the end state is not solved (all clues are not satisfied). I do find this discussion really interesting. Maybe I should have reserved "Section 666" for these puzzles with unique solution but require a branching strategy :).

duskwuff 1y ago
Out of curiosity, are you familiar with Simon Tatham's Portable Puzzle Collection [1]? It includes a nonogram puzzle, under the name "Pattern" - I believe it guarantees that the puzzles are solveable without backtracking. It can generate puzzles up to 40x40 or so in a reasonable amount of time. [1]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
- okayestjoel 1y ago
  Yes, I am familiar! I didn't play his games growing up, but I see it as a great reference for various logic puzzle game implementations and one of the few examples of quality logic puzzle collections. I think one thing missing from my 5x5 puzzle thing is that good nonograms are not just those that have a unique solution and require no guessing, but also create a compelling image when the puzzle is complete. My game, Pixelogic, features user-submitted puzzles in addition to in-house ones, and I'm often blown away how creative the pixel art creations are given the constraints of solvability under my game's standards and just on and off pixels. I wrote about what makes a good nonogram puzzle (in my opinion) in my weekly nonogram newsletter, if anyone is interested: https://weekly.pixelogic.app/p/pixelogic-weekly-4 https://weekly.pixelogic.app/p/pixelogic-weekly-4