Out of curiosity, are you familiar with Simon Tatham's Portable Puzzle Collection [1]? It includes a nonogram puzzle, under the name "Pattern" - I believe it guarantees that the puzzles are solveable without backtracking. It can generate puzzles up to 40x40 or so in a reasonable amount of time.
[1]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/