This is an attempt to answer your secondary question:
[I]f I choose a random (solvable) starting problem, what's the probability that it will have a unique solution?
One answer is found in the paper On Determining Paint by Numbers Puzzles with Nonunique Solutions by Ryan Mullen (Journal of Integer Sequences, vol. 12, 2009, Article 09.6.5).
A natural starting approach to try to solve a nonogram is to see whether the colors of any cells in a row (or column) are determined by the sequence of numbers given for that row (or column), which shall be called a "hint sequence". The worst-case scenario is that no cell in a row has its color determined by its hint sequence (in which case one is compelled to use the data from the columns and the rest of the rows). With this motivation, the author makes the following definition:
We define a forceless sequence to be a sequence such that no partial coloring can be determined without the aid of the rest of the puzzle.
If a nonogram puzzle has $n$ columns, how many forceless sequences are possible? Denote this number by $G_n$. The first few values of $G_n$ are listed in the OEIS entry A304179. The author also shows (see Theorem 2.1) that the number of hint sequences possible for an $n$ column puzzle is $F_{n+2}$, where $(F_n)_{n \geq 1}$ is the Fibonacci sequence given by
$$
F_1 = F_2 = 1, \quad F_{n} = F_{n - 1} + F_{n - 2} \text{ for all } n \geq 2.
$$
Thus, the probability that a hint sequence of an $n$ column puzzle (picked uniformly at random from the set of all possible $n$-column hint sequences) is a forceless sequence is $G_n/F_{n+2}$.
Now, the author provides estimates for the growth of $G_n$ as follows (see Theorems 3.1 and 3.2): there exist constants $c_1, c_2 > 0$ such that
$$
c_1 \frac{\phi^n}{n} \leq G_n \leq c_2 \frac{\phi^n \ln n}{n}
$$
for all $n \geq 2$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.
In the paper The Asymptotics of Useless Hint Sequences in Nonograms, by Daniel Berend and Shira Zucker (Journal of Integer Sequences, vol. 21, 2018, Article 18.4.2), the authors tightened the above estimates to show that there exist constants $C_1, C_2 > 0$ such that
$$
C_1 \frac{\phi^n}{n} \leq G_n \leq C_2 \frac{\phi^n}{n}
$$
for all $n \geq 1$. Since it is known that the Fibonacci sequence grows as $F_{n} \approx \phi^n / \sqrt{5}$, the probability $G_n / F_{n+2}$ grows as $1/n$ upto some multiplicative constant (i.e., $G_n/F_{n+2} = \Theta(1/n)$).
A different model of randomness is considered in the paper Nonograms: Combinatorial questions and algorithms by Daniel Berend, Dolev Pomeranz, Ronen Rabini, and Ben Raziel (Discrete Applied Mathematics, vol. 169, 2014, pp. 30–42). In this paper, the authors primarily develop an improved algorithm for a "line-solver", that is, an algorithm that takes a row (or column) hint sequence as an input and finds out which cells in that row (or column) have their colors determined, as well as what those colors should be.
Additionally, they establish that for a "randomly" chosen $n \times n$ puzzle, it is highly likely for large $n$ that a line solver is unable to determine the color of even one cell. Specifically, they use the following definition of a "random" puzzle:
Our interpretation is that we start with an uncoloured grid, and colour each cell in white or black with probabilities of $1/2$ each, distinct cells being independent. … Note that this is very different from taking all puzzle descriptions and picking one of them uniformly at random. (The latter possibility is more in line with Mullen’s interpretation of randomness for single lines.) To emphasize the difference, we shall henceforth refer to our version of a random puzzle as a randomly generated puzzle. (Namely, the grid is coloured uniformly at random, but some puzzles have a much larger probability of being obtained than others.)
With the above definition, the authors prove the following:
Theorem 2. Let $C$ be the number of cells of an $n \times n$ randomly generated puzzle whose colour is determined by a line solver. Then $P(C = 0) \underset{n \to \infty}{\longrightarrow} 1$ exponentially fast.
This is obviously a very different estimate from the one mentioned previously due to Mullen and Berend–Zucker, but there is no contradiction because the probability spaces in these two cases are quite different.
The authors also establish a probabilistic estimate for how many $m \times n$ puzzles have multiple solutions.
Theorem 4. There exist effective positive constants $\delta, \varepsilon > 0$ such that the probability of a randomly generated $m \times n$ puzzle
($m, n \geq 2$) to have less than $2^{\delta m n}$ solutions is less than $2^{−\varepsilon m n}$.
In particular, their proof shows that
the theorem is valid with the choices $\delta = 2^{−18}$, $\varepsilon = 2^{−20}$.
So, if a nonogram puzzle is picked randomly by picking a picture in the $m \times n$ grid uniformly at random, then (for large puzzles) it is highly unlikely that a randomly picked puzzle does not have many solutions.
Addendum
This question seems to be fairly complicated. For instance:
- In contrast with Theorem 2 of Berend–Pomeranz–Rabini–Raziel mentioned above, their Theorem 3 shows that if one considers all the hint sequences together, then there is at least one cell whose color can be specified with a probability bounded away from zero:
Theorem 3. For sufficiently large $m$ and $n$, a randomly generated $m \times n$ puzzle has, with probability at least $1/6$, at least one cell whose colour is uniquely determined. Moreover, one can find such a cell (with probability at least $1/6$) in constant time.
- Solving a general nonogram is known to be NP-hard, though it is possible to find fast algorithms in special cases (Kees Joost Batenburg and Walter A. Kosters, Solving nonograms by combining relaxations, Pattern Recognition, vol. 42, 2009, pp. 1672–1683).
- Suppose a specific nonogram is known to have a solution. Determing whether the solution is unique is an NP-complete problem (Nobuhisa Ueda and Tadaaki Nagao, NP-completeness Results for NONOGRAM via Parsimonious Reductions, Technical Report TR96-0008, Tokyo Institute of Technology, 1996).
- To the best of my knowledge, there is no known recurrence (let alone one that is amenable to efficient computation) for the number of $n \times n$ nonograms that have unique solutions, most probably because it is not known how (and whether) one can generate every $n \times n$ nonogram with a unique solution by piecing together information from smaller nonograms. This would explain why there are very few entries in the OEIS entry A242876 mentioned in Gareth McCaughan's answer.
All in all, my intuition is that it is, at best, quite optimistic to hope for an exact count for the number of $n \times n$ nongrams that are uniquely solvable. Probabilistic estimates are more feasible, in my opinion.