[duskwuff]

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]

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]

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)