Mfcttrf

This type of puzzle goes by many names: Nonogram, Picross, and Griddlers are all mentioned on the Wikipedia page, Simon Tatham calls it Pattern, I was introduced to it as Descartes Rainbow, ...

The puzzle starts with a given arrangement of numbers around a grid. Let's assume it's a square, $ntimes n$ grid, and that the pattern is a simple black and white one, no colours. Every possible pattern of black cells in the $ntimes n$ grid gives some arrangement of numbers, but there are some different patterns which give the same arrangement of numbers. A good puzzle starts with an arrangement of numbers which has one unique solution. But if I choose a random (solvable) starting problem, what's the probability that it will have a unique solution?

Among all possible starting positions, how many have a unique solution?

_{Important note: I don't know the answer to this question. I don't even know if anyone knows: it could be an open mathematical problem. I'm also not expecting it to be an easy thing to answer off the cuff: it's more likely to be something found in a mathematical paper or so. But we have a good subcommunity of maths puzzle gurus here, and maybe someone will be better able to find the answer than I.}

Absurdly partial answer

Terminology: an "inner configuration" is an arrangement of filled and empty cells in our $ntimes n$ grid; an "outer configuration" is the corresponding arrangement of run-lengths displayed outside the grid. Let $I_n=2^n^2$ be the number of possible inner configurations, $O_n$ be the number of distinct outer configurations arising from these, and $U_n$ be the number of these corresponding to a unique inner configuration. The question asks for $p_n:=U_n/O_n$; I suspect $q_n:=U_n/I_n$ may be less impossible to find, though probably both are hard. Obviously $O_nleq I_n$ and so $q_nleq p_n$.

For $n=0$: obviously $I_0=O_0=U_0=1$ so $p_0=q_0=1$.

For $n=1$: there are just two inner configurations, and each corresponds to a different outer configuration. So $I_1=O_1=U_1=2$ and $p_1=q_1=1$.

For $n=2$: there are two "bad" configurations, the ones with two diagonally-opposite empty cells. All other configurations either have an asymmetry making them easily solvable, or have all cells in the same state which is also easy. So $I_2=16,O_2=15,U_2=14$ and therefore $p_1=frac1415,q_1=frac78$.

The sequence of $U_n$ is A242876 in OEIS. Not very many terms are computed there, which suggests (at least) that others agree with my feeling that this is a hard problem.

I doubt it could be calculated exactly except for very small grids, but it should be possible to Monte Carlo it.

One has to be careful about bias. I don't think there is any way to choose the numbers directly such that all solvable number patterns are equally likely.

Instead you could choose a random grid picture such that every picture is equally likely (i.e. each cell 50% probability of black). Take the corresponding number pattern, and see how many solutions it has by running it through a solver. Of course this selection method will be biased towards number patterns with multiple solutions, so to compensate you can give this a weight of $1/k$, where $k$ is the number of solutions.

Then you just generate lots of random bit grid patterns. Let $t$ be the total weight of all the patterns produced, and $u$ the total weight of the uniquely solvable patterns encountered. Then $u/t$ should approach the probability you are looking for if you go on long enough.

Answer in construction

From an algorithm point of view, the ways you can attempt to crack the problem are either too strenuous for decent results in an amount of time or redundant in comparison to a decent mathematician... so I don't expect anything useful to be yielded from using a computer algorithm.

That said, I have a simple starting point that may or may not be useful in the long run

Lets consider that a Nonagram can be represented as bits where $1=coloured$ etc. Nonagrams contain numbers outside the grid (lets casually call this $A_x$, where $A_x$ is an array of $S$ length) which validly represent the bits in the respective row or column. It is possible to determine if a Nonagram is unique by finding if there are other solutions that have the exact same $A_x$. Obviously, it is difficult to do this mathematically, lets break the problem down and see if it gets us anywhere I intend for my answer to help others reach a final, accepted answer (if that even exists). I probably won't be able to continue past a certain level of maths

---

Lets start by just thinking of a single trail of bits (called $B_i$). This trail is of length $N$ and can be represented by $A_x$. How many combinations of $B_i$ share $A_x$? It is easy to see that for $A_x$ with $S = 1$ there are $N-A_1+1$ of $B_i$. For $S>1$ it gets complicated since there can be a variable number of $0$ bits padding between $1$ clusters. What is certain is that there is always at least one $0$ bit between clusters. Consider a strategy where the padding can be distributed in many combinations. Let $T = sumlimits_r=1^SA_r$ and $D=N-T$. The difference $D$ represents the total padding between clusters, it can be distributed for the $S+1$ paddings in between clusters in different ways. There are $S-1$ paddings that must be a size of at least one. This leaves $D-S+1$ to be distributed between all $S+1$ padding. The formula for this would then be $D+1 choose S$

So $A_x$ has $N+1-sumlimits_r=1^SA_r choose S$ corresponding $B_i$ of length $N$.

This also implies that $N+1-sumlimits_r=1^SA_r=S$ when there is only one unique $B_i$. This tells us that ALL valid nonograms, where all of the rows and columns satisfy this rule, have a unique solution!

---