12
$\begingroup$

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, $n\times n$ grid, and that the pattern is a simple black and white one, no colours. Every possible pattern of black cells in the $n\times 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.

$\endgroup$
  • $\begingroup$ Just to check I understand: you're looking at numbers-around-the-outside that correspond to some configuration within the grid, and asking what fraction of those correspond to exactly one configuration? I wonder whether the following related question might be more approachable: consider all within-the-grid configurations; what fraction of those have around-the-grid numbers that correspond to just one within-the-grid configuration? (Probably both are very tough, though.) $\endgroup$ – Gareth McCaughan Jun 13 at 13:20
  • $\begingroup$ @Gareth Yes, but both problems are interesting, and potentially mutually entangled (a solution to one, or its proof, might quickly yield a solution to the other). I'd consider an answer to the second question at least a partial answer to this one. $\endgroup$ – Rand al'Thor Jun 13 at 13:22
  • $\begingroup$ I don't even have a confident guess at whether either Rand's fraction or mine (1) -> 0 as n->oo, (2) -> 1 as n->oo, (3) -> something else as n->oo, (4) doesn't converge but is bounded away from 0 and 1, or (5) doesn't converge and is sometimes close to 0 or 1 for large n. I'd guess either 1 or 3. $\endgroup$ – Gareth McCaughan Jun 13 at 13:35
  • 1
    $\begingroup$ This is a very great question, I hope there would be progress on this. (And if your colleague does find a solution, please update us here, too!) $\endgroup$ – justhalf Jun 13 at 14:02
8
$\begingroup$

Absurdly partial answer

Terminology: an "inner configuration" is an arrangement of filled and empty cells in our $n\times 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_n\leq I_n$ and so $q_n\leq 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=\frac{14}{15},q_1=\frac{7}{8}$.

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.

$\endgroup$
  • $\begingroup$ The way I read the question, it seems to be asking for $U_n$ instead of $p_n$. (And did you mean $O_n \leq I_n$ instead of $U_n \leq I_n$?) $\endgroup$ – justhalf Jun 13 at 14:07
  • $\begingroup$ And thanks for posting the OEIS number. Seems like a hard problem indeed. $\endgroup$ – justhalf Jun 13 at 14:13
  • 1
    $\begingroup$ @justhalf It asks for both $U_n$ ("how many have ...") and $p_n$ ("what's the probability ..."). But you're right that I meant O not U when comparing the fractions; I'll fix that. [EDITED to add:] Done now. $\endgroup$ – Gareth McCaughan Jun 13 at 14:21
  • $\begingroup$ Is there OEIS for $O_n$? Maybe that is easier. $\endgroup$ – justhalf Jun 13 at 14:38
4
$\begingroup$

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 Nonogram 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 Nonogram 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 = \sum\limits_{r=1}^{S}A_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-\sum\limits_{r=1}^{S}A_r} \choose {S}$ corresponding $B_i$ of length $N$.

This also implies that $N+1-\sum\limits_{r=1}^{S}A_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! (for future reference, lets call these stuffed Nonograms)


Lets have a closer look into the stuffed Nonograms since it may give us a very vague idea of what the final function (if it exists) will look like. An equation to identify stuffed Nonograms can be derived if we rearrange the rule to $N=S-1+\sum\limits_{r=1}^{S}A_r$. The square Nonogram will have $2N$ of $B_i$ that follows this rule so by summing everything, $2N^2=\sum\limits_{i=1}^{2N}(S_i-1+\sum\limits_{r=1}^{S_i}A_{i_r})$ or the nicer equation $2N^2+2N=S_T+A_T$ using $S_T$ and $A_T$ to represent the amount of total items $A_x$ and the summation of all of them respectively. There is a constraint that $S_T\geq2N$ and $A_T\geq2N$.

Logically it can be concluded that stuffed Nonograms are Nonograms that have a completely/almost full unique grid as the solution. They have peppered padding of length one (single holes). This can be proven by revisiting $B_i$. Let $B_i$ have $C$ padding of one so that $T = N - C$ and $S = C + 1$. Subbing into $N+1-T=S$ we see no contradiction since $N+1-(N-C)=C+1$ so $C+1=C+1$ $\therefore$ peppered padding of one is always unique! There is an indirect implication that there cannot be any front or back padding (since it creates more solutions) so stuffed Nonograms must at least have a full outer rim of one. It is for this reason that the only area of stuffed Nonograms with importance is $(N-2)^2$. Now consider this; if the area is unwound to become many $B_i$ and the placement of the peppered padding is considered in a converse way of thinking then the amount of corresponding $B_i$ from $A_x$ formula can be repurposed to count the total amount of stuffed Nonograms possible. The formula will initially over approximate since the rewrapping of some $B_i$ configurations will lead to alignment of padding resulting in padding of length greater than one which is invalid. To overcome this, an extra formula that counts the number of invalid wraps must be developed.

Edit: The following two paragraphs are now redundant since I've managed to find what appears to be the solution by changing my approach. The paragraphs are still necessary to fully understand the tech used in my new approach so for historic reasons I'm keeping them for the now. (Thinking of shortening this answer by moving the "holes in grid" problem into its own Q&A question)

Lets over approximate. Consider a single $B_i$, the padding is all of length one so all of $A_x$ (in this perspective) will contain $1$. $S$ can vary from $0\to \lceil\frac{N-2}{2}\rceil$ (thanks odd numbers) and $T=S$. The formula for the amount of possible $B_i$ must then be $\sum\limits_{r=0}^{\lceil\frac{N-2}{2}\rceil} {{(N-2)+1-r} \choose {r}}$. This is actually equivalent to the Fibonacci series (thanks to @justhalf's insight). The function $Fi(x)$ will be used to represent the series from now on. There is $N-2$ of $B_i$ in the relevant area which can have different combinations at once. This is the same as a combination lock of length $N-2$ so the overall formula for the amount of configurations in this case is $Fi^{(N-2)}(N)$.

Now to count all of the invalid wraps. Lets use an easy model and say that the $B_i$ are stacked on top of each other. Invalid wraps must occur when a padding of length greater than one is created from stacking $B_i$ that have padding which align. Alignment can only happen between neighbour $B_i$ and all that is required is for padding to exist at the same position locally within the two $B_i$. Take $G$ to equal the amount of $B_i$ and $L$ to equal the length of all $B_i$ (just incase we can revisit this formula). There are $G-1$ seams between $B_i$ where alignment can occur and it is possible for more than one set of neighbour $B_i$ to align at once.

Edit: This is the new approach

Lets consider the valid combinations at one seam. In order for valid combinations to happen the padding must never overlap. Lets say that the top $B_i$ at this seam can be anything where it is valid within itself. It is logical to conclude that the bottom $B_i$ must only be valid when its own padding is contained within the clusters of the top $B_i$ whilst still being internally valid. It is for this reason that the bottom $B_i$ can be considered as any $A_x$ that fragments into small locally valid $B_i$! We can now further abuse the $A_x$ formula! The formula currently depends on arrangement of $A_x$ so to fix that to make the combinations countable it is now ${{L+1-\sum\limits_{r=1}^{S}A_r} \choose {S}}S!$ (permutations). The clusters can all be any combination of locally valid $B_i$ so this is $\prod\limits_{i=1}^{S}Fi(A_i+2)$. This gives us the final formula for the seam combinations (for $A_x$) to be ${{L+1-\sum\limits_{r=1}^{S}A_r} \choose {S}}S!\prod\limits_{i=1}^{S}Fi(A_i+2)$. The total combinations can be found by summing combinations for $A_x$'s. Initially, I thought it wouldn't be possible to account for multi-seam combinations however I think that by inversion, the next seam in the stack has the same possible combinations regardless of the affects of the seam beforehand. This would create a simple combination lock of length $G$. I will be thoroughly impressed if anyone manages to put the whole formula together!


Another group of unique, valid Nonograms exists that can immediately be counted. The group consists of Nonograms where the rows/columns can only be completely full, empty or something inbetween (the latter arises from the overlap of rows and columns that are full or empty which creates a 'different image'). For future reference, lets call these net Nonograms.

Anyone familiar with solving Nonograms will know how useful completely full/empty rows/columns are. It is a good idea to take this concept to its extremes because it may be used as a part of the final solution to split Nonograms into smaller Nonograms (well, it is way more complicated than that but still). Consider just the rows of net Nonograms, it is possible to use binary to represent the information. It is for this reason that $2^N$ is the amount of combinations of rows. The same can be said for the columns. If the information for the rows and columns is 'overlapped' then we have $2^{2N}-2$ total net Nonograms! The $-2$ takes into account the two repeated combinations (all full or all empty). Gonna need proof for how overlap is resolved and why it still leads to unique, valid Nonograms but I think it is safe to say that this was a simple idea for the books...


Ideas

This section is going to be used to document facts/ideas ranging from basic to abstract, I just want to put concepts on the record so that this can be used as a helpful guide when looking for the answer.

  • The final function will be a recurrence relation.
  • The answer to "How many invalid solutions exist for $A\times B$ Nonograms with a specific set of $A_x$?" will inevitably lead to the answer for "How many valid solutions for an $N\times N$ Nonogram exists?" and "How many unique $N\times N$ Nonograms exist?"
  • The answer to the above "invalid solutions exist..." will likely contain recursion.
  • The groups of Nonogram currently defined in my 'answer' both tend to zero as $N\to \infty$ when considering the approximate probability of the groups out of all possible random configurations $2^{N^2}$
$\endgroup$
  • $\begingroup$ You don't seem to mention the relation between row and column anywhere in your answer, which is necessary in any answer, I believe. I'm not sure if I follow your argument. $\endgroup$ – justhalf Jun 17 at 1:41
  • $\begingroup$ I'm responding to your second section (where you defined stuffed Nonogram). I feel like it is a simplification to try to answer How many combinations of Bi share Ax? simply by looking at a column or a row independently (which to my reading is what you seem to be doing), because uniqueness is also determined by the interaction between the numbers in the rows and in the columns. But it is also possible that I misunderstood your explanation. Hope you can clarify. $\endgroup$ – justhalf Jun 17 at 17:16
  • $\begingroup$ What you call stuffed Nonograms seems to be simply the number of possible bit arrangement of length $N$, and you count it by separating the cases on the number of partitions (running sequence of colored boxes) it has. So your final sum would be equal to $2^N$. Or, since you add padding, it would be $2^{N-2}$. $\endgroup$ – justhalf Jun 17 at 18:19
  • $\begingroup$ Ahh, I got what your stuffed Nonogram means. It is referring to the case where just based on looking at only the numbers at a given row/column, we can determine the solution for that row/column. This would be the same as the number of ways to put any number of uncolored boxes on the grid, such that no uncolored boxes touch each other or the boundary. This is a very specific case of Nonogram. Then the sequence cannot be 1, 1, 1, 6. As for $N=3$ there are two possibilities (one hole and no hole). $\endgroup$ – justhalf Jun 17 at 20:44
  • 1
    $\begingroup$ Just to let you know, in 1D, the solution to number of possible ways to put boxes that do not touch each other is the Fibonacci series. So I'm guessing in 2D it would be much more complicated. $\endgroup$ – justhalf Jun 17 at 22:52
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "I doubt it could be calculated exactly except for very small grids" - why? This seems like exactly the type of problem that could potentially be approached using mathematical techniques of combinatorics. (If an answer doesn't exist in the literature and nobody on PSE can find it, I will literally ask a colleague mathematician who may be able to solve it and publish the result.) $\endgroup$ – Rand al'Thor Jun 13 at 13:27
  • 1
    $\begingroup$ It feels hard to me too. The unique-solution constraint is a complicated one. Compare with the problem of enumerating partitions, which seems kinda related but much much easier; there's an explicit formula for that but it took Hardy and Ramanujan to find it. (In fact they didn't quite find the explicit formula; Rademacher found that by improving on their work.) $\endgroup$ – Gareth McCaughan Jun 13 at 13:33
  • 1
    $\begingroup$ @Randal'Thor The problem of deciding whether or not a number pattern has a unique solution has the feel of an NP-hard problem to me. If you have an ambiguous number pattern, and want to apply a tweak to make it uniquely solvable, such a tweak can be done almost anywhere on the grid. The fact that local changes have global effects is one feature usually seen in NP-hard problems. $\endgroup$ – Jaap Scherphuis Jun 14 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.