Comment by gus_massa | Hacker News Reader

Comment by gus_massa | Hacker News Reader

Parent Full thread

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

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.

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

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)

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.

I agree they are the same. It's just that if the try is short enough, I consider it a valid trick.

Reply on news.ycombinator.com