3 ms·

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 to

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)