The puzzle appears regularly in the Sunday Telegraph (UK) and irregularly in Games Magazine (US). It is also very popular in Japan. Our experience is that most puzzles set for humans can be solved by constraint propagation alone. However the second solution problem: i.e. find a second solution to a puzzle given a first one, is known to be NP-complete. The regular puzzle must be also, but we have not seen a reference that confirms that fact.
Robert Bosch’s description of the problem, and an integer programming model.
Toby Walsh’s teaching pages have a project description for a nonogram solver with many useful links.