Nonograms are not bad but I wouldn’t consider them either crosswords or puzzles. There’s a cap on how much skill is needed to solve one (of a reasonable size) based on the need to make a solvable piece of art.

(Nonograms in general - without the need for a pictoral reward - might well be NP hard or even able to encrypt information. I’m not at all sure.)