4 ms·

questerzen (below) is correct: there are 25,309,575 solvable nonograms, not 24,976,511. This is OEIS sequence A242876 — https://oeis.org/A242876 https://oeis.o

questerzen (below) is correct: there are 25,309,575 solvable nonograms, not 24,976,511. This is OEIS sequence A242876 — https://oeis.org/A242876 https://oeis.org/A242876 okayestjoel (below) wrote: > My nonogram solver goes over every possible configuration for each row and column based on the clues, and either fills in squares that must be filled (all possibilities overlap) or marks squares that must be empty. So if the solver reaches a point where there is ambiguity about what the next move is, then it is deemed not solvable (without guessing). It would be (mildly) interesting to see an example of one of the 333064 solvable 5x5 nonograms that cannot be solved by okayestjoel's solver's heuristics.

quuxplusone 1y ago
Here's a reverse example: Nonogram #18,950,614 (in section 759) is "21-1-12-21-12+4-21-1-3-11". If we fill in every cell that absolutely must be filled in based only on the data shown in a single row or column (plus the Xs that the JavaScript shows us), we get to this point: 2 1 41131 1 2 ___#_ 2 1 ##x#x 1 2 #__#_ 1 #xxxx 2 1 _#_x# I believe at this point the tactic of "just find a cell that must be black based only on data from its row or column" fails. We can continue only by "using our heads" (i.e. "backtracking"), or by starting to mark cells that must be empty based on data from only their row or column. The cell with the capital X below must be empty because of data in row 3. But the JavaScript didn't auto-mark it with an X. Maybe this is just a logic bug in the JavaScript?: 2 1 41131 1 2 ___#_ 2 1 ##x#x 1 2 #X_#_ 1 #xxxx 2 1 _#_x# And from there we can solve column 2, row 1, row 3, and row 5, in that order.
- bspammer 1y ago
  Isn't that situation covered in the original description? They said that marking squares that must be empty is fair game. The only thing not permitted is forced backtracking. I don't think it's a bug in the javascript either, it seems intentional that it only fills in the x's automatically if you've filled in the squares for that row/column.
duskwuff 1y ago
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.
    - 1y ago

quuxplusone 1y ago

Here's a reverse example: Nonogram #18,950,614 (in section 759) is "21-1-12-21-12+4-21-1-3-11". If we fill in every cell that absolutely must be filled in based only on the data shown in a single row or column (plus the Xs that the JavaScript shows us), we get to this point: 2 1 41131 1 2 ___#_ 2 1 ##x#x 1 2 #__#_ 1 #xxxx 2 1 _#_x# I believe at this point the tactic of "just find a cell that must be black based only on data from its row or column" fails. We can continue only by "using our heads" (i.e. "backtracking"), or by starting to mark cells that must be empty based on data from only their row or column. The cell with the capital X below must be empty because of data in row 3. But the JavaScript didn't auto-mark it with an X. Maybe this is just a logic bug in the JavaScript?: 2 1 41131 1 2 ___#_ 2 1 ##x#x 1 2 #X_#_ 1 #xxxx 2 1 _#_x# And from there we can solve column 2, row 1, row 3, and row 5, in that order.

bspammer 1y ago
Isn't that situation covered in the original description? They said that marking squares that must be empty is fair game. The only thing not permitted is forced backtracking. I don't think it's a bug in the javascript either, it seems intentional that it only fills in the x's automatically if you've filled in the squares for that row/column.

duskwuff 1y ago

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