The Asymptotics of Useless Hint Sequences in Nonograms

Daniel Berend^{1} Departments of Mathematics and Computer Science Ben-Gurion University Beer-Sheva 84105 Israel

                 berend@math.bgu.ac.il

Shira Zucker Department of Computer Science Sapir Academic College M.P. Hof Ashkelon 79165 Israel

                zucker.shira@gmail.com

Abstract

In this paper we consider a question raised by Mullen regarding Nonogram puzzles. An instance of the puzzle consists of a p × n grid, whose cells are to be colored black or white, according to some hints. These hints specify the lengths of the blocks of consecutive black cells in each row and column.

Mullen studied the asymptotic probability that a random hint sequence of a single row uniquely determines the color of at least one cell in that row, and gave lower and upper bounds on this probability. In this paper we tighten his bounds.

1Research supported in part by the Milken Families Foundation Chair in Mathematics.

1 Introduction

A Nonogram is a classic logic puzzle, in which cells in a grid must be colored black or left uncolored (or, equivalently, colored white) according to numbers at the side of the grid. (Wikipedia [9] lists dozens of other names by which the puzzle is known.) In this puzzle, a rectangular grid is given with a finite sequence of numbers alongside each row and above each column. These numbers indicate the lengths of the blocks of consecutive black cells in the rows and columns, respectively. For example, the sequence 3, 2 signifies that in this row (or column) there are three adjacent black cells, a gap of at least one uncolored cell, and then two adjacent black cells. Note that there may be any number of uncolored cells before the first block of black cells and/or any number of uncolored cells after the last block. Thus, if the given sequence is of length k, then in addition to the blocks of black cells, there must be k − 1 uncolored blocks in between, and perhaps one or two uncolored blocks on the sides.

Table 1 provides an example of a small solved puzzle. Initially, we note that the second row needs to contain 5 black cells, and has only 5 places. Therefore, all cells in this row need to be colored black. This completes filling the second and fourth columns, which should contain only one black cell each. Similarly, the third column should contain three black cells and has only three places. Therefore, all cells of the third column are colored black. This completes filling the third row. The first row should contain three black cells, with at least one uncolored cell between each two. Thus there is only one way to color the first row, and we are done.

2 1 3 1 2
1, 1, 1 x x x
5 x x x x x
1  x

Table 1: Example of a small puzzle

Assume, for example, that the given sequence for some row is 2, 1, 4. In this case, if the length of the corresponding row is 9, then we know exactly how the cells are to be colored. If n = 10, then there are four possible configurations, corresponding to the possible locations of the “extra” uncolored cell. However, in all these configurations, the cells in places 2, 7, 8, 9 of the row are colored black. In order to color the remaining cells, we need to use data regarding the rows and the other columns. If n ≥ 13, then we cannot deduce the color of any cell without using data from the rest of the puzzle.

The puzzle was studied from several points of view. The decision problem of unique solvability of a puzzle is NP-complete [8]. Batenburg and Kosters [2] showed that one can find all cells of a partially colored row that must be colored in some way (black or white), according to the hints regarding that row, in polynomial time. Berend, Pomeranz, Rabani, and Raziel [4] showed that, for a large randomly colored puzzle, the probability that even the color of a single cell is uniquely determined, by the hints relating to the corresponding row or column only, is very small. (However, when we do consider all hints simultaneously, the probability of having some cells with a uniquely determined color is bounded away from 0.) It was also proved that such a puzzle usually admits a huge number of solutions. Benton, Snow, and Wallach [3] studied the number of possible puzzles if, instead of recording the length of all blocks of black cells in all rows and columns, one records only the total number of black cells in each row and column.

When solving a nonogram puzzle, it is natural to start by looking for rows (and columns) whose hint sequences determine uniquely the color of some of the cells along the row, without resort to data from the rest of the puzzle. Thus, it is natural to study the number of hint sequences, for rows of any length n, that provide immediate information on at least some of the cells. It follows from Mullen [7] that most hint sequences satisfy this property. Hence it is more convenient to study the complement, namely the number of sequences that give no such information — useless sequences (forceless sequences in Mullen’s terminology). Mullen [7] studied the asymptotics of the number of useless sequences as a function of the row length. More precisely, he first observed that the total number of hint sequences, for a length-n row, is F_{n+2}, where (F_{n})_{n=1}^{∞} is the Fibonacci sequence, defined as follows:

\begin{matrix}F_{1} = F_{2} = 1, \\ F_{n} = F_{n−1} + F_{n−2}, n ≥ 3. \end{matrix}

Note that there are obviously 2^{n} ways to color a length-n row, but we care only about hint sequences. As many distinctly colored rows give rise to the same hint sequence, the total number of hint sequences is much smaller than 2^{n}. Recall that F_{n} behaves asymptotically as ϕ^{n}/\sqrt{5}, where ϕ = (1 + \sqrt{5}) /2 is the golden ratio. Letting G_{n} denote the number of useless sequences for rows of length n, Mullen [7] proved

Theorem 1. For appropriate constants c_{1}, c_{2} > 0,

G_{n} ≥ c_{1} · \frac{ϕ^{n}}{n}  (1)

and

G_{n} ≤ c_{2} · \frac{ϕ^{n} ln n}{n},  (2)

for all n ≥ 2.

The sequence (G_{n}) is sequence \underline{A304179} in the On-Line Encyclopedia of Integer Sequences. In this paper we show that the right-hand side of (1) provides the correct order of

magnitude of G_{n}. In Section 2 we state this result formally, and in Section 3, we prove it. Section 4 presents a heuristic discussion that tries to explain even better the asymptotic behavior of G_{n}, and in particular that this behavior is somewhat irregular.

An abridged version of this paper was presented at the 28th Canadian Conference on Computational Geometry [5]. We express our gratitude to the editor and to the referee for their helpful comments on the initial version of the paper.

2 The main result

Our main result, employing the notations in the preceding section, is

Theorem 2. There exist two constants C_{1}, C_{2} > 0 such that

C_{1} · \frac{ϕ^{n}}{n} ≤ G_{n} ≤ C_{2} · \frac{ϕ^{n}}{n} , n ≥ 1.

Theorem 2 can be interpreted as giving an asymptotic estimate of the probability of a random hint sequence being useless. In fact, as the total number of hint sequences is F_{n+2}, the probability of a random hint sequence being useless is G_{n}/F_{n+2}. Since F_{n+2} ≈ ϕ^{n+2}/\sqrt{5}, the probability in question is approximately \frac{G_{n}\sqrt{5}}{ϕ^{n+2}}, which by the theorem is Θ(\frac{1}{n}).

Note, however, the difference between this result, and the previously mentioned result of Berend et al. [4], according to which a random coloring usually gives rise to a useless hint sequence. In the model of Berend et al. [4], one selects randomly a coloring of the row out of all 2^{n} colorings, and considers the corresponding hint sequence. Here, as in Mullen’s results [7], we pick randomly one of all F_{n+2} hint sequences and consider it. The two probability spaces are very different, and thus the difference in the outcome is not contradictory.

In Table 2 we provide the value of G_{n}/F_{n+2}, normalized by multiplying it by n, for several n’s up to 6000. (The computations were carried out using Formulas (3) and (4) below.) According to Theorem A, these values are bounded. A quick glance at Table 2 may lead one to believe that nG_{n}/F_{n+2} increases to some limit as n → ∞. In Section 4 we will argue heuristically that, in fact, the sequence oscillates between two very close values, but does not actually converge.

\begin{matrix}n & G_{n} & nG_{n}/F_{n+2} \\ 10 & 33 & 2.2917 \\ 20 & 2258 & 2.5498 \\ 50 & 1.8 · 10^{9} & 2.7331 \\ 100 & 2.6 · 10^{19} & 2.8007 \\ 200 & 1.0 · 10^{40} & 2.8358 \\ 500 & 2.1 · 10^{102} & 2.8573 \\ 1000 & 3.3 · 10^{202} & 2.8646 \\ 2000 & 1.6 · 10^{415} & 2.8682 \\ 3000 & 1.0 · 10^{624} & 2.8694 \\ 4000 & 7.5 · 10^{832} & 2.8700 \\ 5000 & 5.8 · 10^{1041} & 2.8704 \\ 6000 & 4.7 · 10^{1250} & 2.8706 \end{matrix}

Table 2: The probability of being useless for some small n

3 Proof of Theorem 2

Following Mullen’s paper [7], let the norm of a hint sequence be the maximal term in that sequence, i.e., the maximal length of a block of cells to be colored black in a row. The length of a hint sequence is the least number of columns needed for that sequence to fit in a puzzle. (For example, the norm of the hint sequence 3, 10, 5, 10, 2 is 10 and its length is 34.) Let A_{m,k} denote the number of hint sequences of length m with norm at most k.

By Mullen [7, p. 6],

A_{m,k} = \begin{cases}F_{m}, & m ≤ k; \\ ∑_{j=m−k−1}^{m−2} A_{j,k}, & m > k. \end{cases}  (3)

To count all useless sequences, we need only sum A_{m,n−m} over all possible lengths [7], that is

G_{n} = ∑_{m=0}^{n−1} A_{m,n−m}.  (4)

For a fixed k, let ϕ_{k} be the largest zero of the characteristic polynomial of (A_{m,k})_{m=1}^{∞}, namely x^{k+1} − x^{k−1} − x^{k−2} − ⋯ − 1. Mullen [7] noted that this is in fact the only positive zero larger than 1.

We will first establish an upper bound on A_{m,k}.

Proposition 3. A_{m,k} ≤ 2ϕ_{k}^{m} for every m, k ≥ 1.

Proof. For m ≤ k, by (3) and the definition of ϕ, we know that A_{m,k} = F_{m} ≤ ϕ^{m}. Now, [7, Prop. 5.3] gives

ϕ ≤ ϕ_{k} (1 + \frac{1}{\sqrt{5}ϕ^{k+1} − (k + 2)}) ,

which implies

ϕ ≤ ϕ_{k} (1 + \frac{1}{2ϕ^{k+1}} ) , k ≥ 8.

Thus,

ϕ^{m} ≤ ϕ_{k}^{m} (1 + \frac{1}{2ϕ^{k+1}} )^{m} ≤ ϕ_{k}^{m} (1 + \frac{1}{2k} )^{k} ≤ ϕ_{k}^{m} · \sqrt{e} ≤ 2ϕ_{k}^{m}, m ≤ k.

For m > k we proceed by induction. If m = k + 1 then

A_{m,k} = ∑_{j=k+1−k−1}^{k+1−2} A_{j,k} = ∑_{j=0}^{k−1} A_{j,k} ≤ 2 ∑_{j=0}^{k−1} ϕ_{k}^{j}.

Since ϕ_{k} is a zero of the polynomial x^{k+1} − x^{k−1} − x^{k−2} − ⋯ − 1, we have ∑_{j=0}^{k−1} ϕ_{k}^{j} = ϕ_{k}^{k+1} and therefore

A_{m,k} ≤ 2ϕ_{k}^{k+1} = 2ϕ_{k}^{m},

as required.

Now suppose that the inequality holds for each m′ such that m′ < m. By the induction hypothesis, we have

\begin{matrix}A_{m,k} = ∑_{j=m−k−1}^{m−2} A_{j,k} ≤ ∑_{j=m−k−1}^{m−2} 2ϕ_{k}^{j} \\ = 2ϕ_{k}^{m−k−1} · ∑_{j=0}^{k−1} ϕ_{k}^{j} = 2ϕ_{k}^{m−k−1} · ϕ_{k}^{k+1} = 2ϕ_{k}^{m}. \end{matrix}  (5)

This proves the proposition.

Lemma 4. For each k ≥ 1

ϕ_{k} ≤ ϕ − \frac{1}{\sqrt{5}ϕ^{k}} .  (6)

Proof. Multiplying the characteristic polynomial of A_{m,k} (for a fixed k) by x − 1, we obtain the polynomial P_{k} = x^{k+2} − x^{k+1} − x^{k} + 1, of which ϕ_{k} is also a zero. Note that ϕ_{k} is the only real zero greater than 1 of P_{k}.

If we calculate P_{k} at the point ϕ−\frac{L}{ϕ^{k}} instead of ϕ_{k}, where L > 0, and recall that ϕ^{2} = ϕ+1, we obtain

\begin{matrix}P_{k} (ϕ − \frac{L}{ϕ^{k}} ) = (ϕ − \frac{L}{ϕ^{k}})^{k+2} − (ϕ − \frac{L}{ϕ^{k}})^{k+1} − (ϕ − \frac{L}{ϕ^{k}})^{k} + 1 \\ = (ϕ − \frac{L}{ϕ^{k}})^{k} · [(ϕ − \frac{L}{ϕ^{k}})^{2} − (ϕ − \frac{L}{ϕ^{k}}) − 1] + 1 \\ = (ϕ − \frac{L}{ϕ^{k}})^{k} · [ϕ^{2} − ϕ − 1 + \frac{L}{ϕ^{k}} − \frac{2L}{ϕ^{k−1}} + \frac{L^{2}}{ϕ^{2k}}] + 1 \\ = (1 − \frac{L}{ϕ^{k+1}} )^{k} · L(1 − 2ϕ + \frac{L}{ϕ^{k}}) + 1 \\ = 1 − L(2ϕ − 1 − \frac{L}{ϕ^{k}})(1 − \frac{L}{ϕ^{k+1}} )^{k} \\ = 1 − L(\sqrt{5} − \frac{L}{ϕ^{k}})(1 − \frac{L}{ϕ^{k+1}} )^{k}, \end{matrix}  (7)

which is positive for L = \frac{1}{\sqrt{5}}. Since ϕ_{k} is a zero of P_{k}, this completes the proof of the lemma.

3.1 Conclusion of the proof of Theorem 2

By Proposition 3 and Lemma 4:

A_{m,k} ≤ 2ϕ_{k}^{m} ≤ 2(ϕ − \frac{1}{\sqrt{5}ϕ^{k}})^{m}, m, k ≥ 1.

In particular,

A_{m,n−m} ≤ 2(ϕ − \frac{1}{\sqrt{5}ϕ^{n−m}})^{m} = 2ϕ^{m}(1 − \frac{1}{\sqrt{5}ϕ^{n−m+1}} )^{m}, 1 ≤ m ≤ n.

As will become evident in the sequel, for a fixed large n, the significant terms A_{m,n−m} on the right-hand side of (4) are those with m close to n − log_{ϕ} n, while the other terms are relatively negligible. Hence we will write m in the form m = n − log_{ϕ} n + d, where d varies between approximately −n + log_{ϕ} n and log_{ϕ} n. (Note that d is non-integer.) We have

ϕ^{m}(1 − \frac{1}{\sqrt{5}ϕ^{n−m+1}} )^{m} = ϕ^{n−log_{ϕ} n+d} · (1 − \frac{1}{\sqrt{5}ϕ^{log_{ϕ} n−d+1}} )^{m}

= \frac{ϕ^{n}}{ϕ^{log_{ϕ} n}} · ϕ^{d} · (1 − \frac{1}{\sqrt{5}n/ϕ^{d−1}} )^{m}

= \frac{ϕ^{n}}{n} · ϕ^{d} · (1 − \frac{1}{\sqrt{5}n/ϕ^{d−1}} )^{\frac{\sqrt{5}n}{ϕ^{d−1}} · \frac{ϕ^{d−1}}{\sqrt{5}n} ·m} .

(8)

For d ≥ 0 (and n sufficiently large) this gives

ϕ^{m} (1 − \frac{1}{\sqrt{5}ϕ^{n−m+1}} )^{m} ≤ \frac{ϕ^{n}}{n} · \frac{ϕ^{d}}{e^{ϕ^{d−1}/3}} .

Hence

∑_{m≥n−log_{ϕ} n} A_{m,n−m} ≤ \frac{ϕ^{n}}{n} · 2 ∑_{d=0}^{∞} \frac{ϕ^{d+1}}{e^{ϕ^{d−1}/3}} .

As the series on the right-hand side converges, this means

∑_{m≥n−log_{ϕ} n} A_{m,n−m} = O (\frac{ϕ^{n}}{n} ) .  (9)

For d < 0 we obtain by (8)

ϕ^{m} (1 − \frac{1}{\sqrt{5}ϕ^{n−m+1}} ) ≤ \frac{ϕ^{n}}{n} · ϕ^{d},

so that

∑_{m<n−log_{ϕ} n} A_{m,n−m} ≤ \frac{ϕ^{n}}{n} · ∑_{d=−∞}^{0} ϕ^{d} = O (\frac{ϕ^{n}}{n} ) .  (10)

According to (4), (9) and (10), we have

G_{n} = O (\frac{ϕ^{n}}{n} ) .

Together with Theorem A, this completes the proof.

4 Does the sequence nG_{n}/F_{n+2} converge?

As mentioned in Section 2, a plausible conjecture is that the sequence (G_{n})_{n=1}^{∞} behaves “regularly”, so that nG_{n}/F_{n+2} ⟶_{n→∞} C for some constant C. This conjecture seems to be supported by the data in Table 2. In this section we explain why we believe this conjecture is false.

We start by looking more carefully at the statistics of hint sequences of length at most n. Recall that the total number of such sequences is F_{n+2}. Since, by the same token, F_{n+1} of these are of length at most n − 1, the number of hint sequences of length n is F_{n+2} − F_{n+1} = F_{n} ≈ ϕ^{n}/\sqrt{5}. Thus, the probability that a random hint sequence for a row of length n does not correspond to strictly shorter rows is asymptotically 1/ϕ^{2}. In other words, the probability, that a random hint sequence of length at most n, is actually of length n, is about 1/ϕ^{2}. Similarly, the probability that the length of such a random hint sequence is n − 1 is about 1/ϕ^{3}. In general, if h is any non-negative integer, then the probability that the length of a random hint sequence is n−h is approximately 1/ϕ^{h+2} for large n. (Note that ∑_{h=0}^{∞} 1/ϕ^{h+2} = 1.) Equivalently, letting H be the random variable measuring the “loss” of a random hint sequence, i.e., such that its length is n − H, we have

P (H = h) ≈ 1/ϕ^{h+2}, h = 0, 1, 2, ….

Thus, H + 1 is asymptotically G (1/ϕ^{2})-distributed, that is geometric with parameter 1/ϕ^{2}. In particular, P (H ≥ h) becomes arbitrarily small as h grows.

Also, when deleting from a hint sequence, corresponding to a row of length n, its first term, and assuming this term is π, we obtain a hint sequence corresponding to a row of length n − π − 1. The statistics of hint sequences, as discussed above, implies that the first term of a random hint sequence is also asymptotically G (1/ϕ^{2})-distributed. Of course, the same holds for all terms of the hint sequence. Since, as noted above, the loss of a random hint sequence is o(n) with high probability, and after each block of black cells corresponding to a term in the hint sequence there is a white block, the number of blocks in a random hint sequence behaves as \frac{n}{1+ϕ^{2}} = \frac{n}{ϕ\sqrt{5}} up to a 1 + o(1) factor. Letting N denote the norm of a random hint sequence, it follows that N is distributed approximately as the maximum of \frac{n}{ϕ\sqrt{5}} random variables, each G (1/ϕ^{2})-distributed. Moreover, it is natural to assume that these variables are nearly independent.

By Mullen [7, p. 5], a hint sequence is useless if and only if its norm and its length sum up to at most n. In terms of the variables H and N, this is the case if and only if N + (n − H) ≤ n, or, equivalently N ≤ H. To calculate the probability of this event, we first note that we must have H ≥ 1 for the event to occur. Thus

P (N ≤ H) = P (H ≥ 1) · P (N ≤ H|H ≥ 1) ≈ \frac{1}{ϕ} · P (N ≤ H|H ≥ 1).

One readily verifies that, in general, if X + 1 ∼ G(p), then (X|X ≥ 1) ∼ G(p). Hence P (N ≤ H) ≈ \frac{1}{ϕ}P (N ≤ H′), where H′ ∼ G (1/ϕ^{2}) . Now, as N is the maximum of about \frac{n}{ϕ\sqrt{5}} approximately G (1/ϕ^{2})-distributed random variables, and H′ is also G (1/ϕ^{2})-distributed, P (N ≤ H′) should be about \frac{1}{\frac{n}{ϕ\sqrt{5}} +1} ≈ \frac{ϕ\sqrt{5}}{n}. In fact, if all variables here were continuous,

this would be correct, as all the variables in the maximum defining N, as well as H′, are identically distributed. However, as these variables are discrete, we need to multiply the \frac{ϕ\sqrt{5}}{n} term by the expected number of variables assuming the maximal value. By Brands, Steutel, and Wilms [6, Remark 1], letting K_{n} denote the number of maxima in a sample of n independent identically distributed G(p)-distributed random variables, we have

EK_{n} = \frac{p}{1 − p} ∑_{ℓ=−∞}^{∞} e^{− ln(1−p)(ℓ−\{log_{1−p} n\})}e^{−e^{ln(1−p)(ℓ−\{− log_{1−p} n\})}} + O (\frac{1}{n}) ,  (11)

(where we let {t} denote the fractional part of a real number t). Letting μ_{n} denote the right-hand side of (11) in our case, with p replaced by 1/ϕ^{2} and n by n/ϕ\sqrt{5}, we obtain

μ_{n} = \frac{1}{ϕ} ∑_{ℓ=−∞}^{∞} (\frac{1}{ϕ})^{ℓ−\{log_{ϕ} n/ϕ\sqrt{5}\}} e^{−(1/ϕ)^{ℓ−\{− log_{ϕ} n/ϕ\sqrt{5}\}}} + O (\frac{1}{n}) .  (12)

Finally,

P (N ≤ H) ≈ \frac{1}{ϕ} · \frac{μ_{n}}{\frac{n}{ϕ\sqrt{5}}} = \frac{μ_{n} · \sqrt{5}}{n}.

Now the sequence (\{log_{ϕ} n/ϕ\sqrt{5}\})_{n=1}^{∞} is dense in the interval [0, 1]. Consequently, as n varies, μ_{n} oscillates (when ignoring the O (\frac{1}{n}) term in (12)) between the minimum and the maximum of the function f : [0, 1] → R, given by

f(t) = \frac{1}{ϕ} ∑_{ℓ=−∞}^{∞} (\frac{1}{ϕ})^{ℓ−t} e^{−(1/ϕ)^{ℓ−t}}, 0 ≤ t ≤ 1.

Note that the oscillations are not periodic. Rather, starting with a large n, we need to go to about ϕn to complete “a whole cycle”. For a similar phenomenon, for a very different problem, we refer for example, to Barbolosi and Grabner [1].

Why does Table 2 not reflect these oscillations? It turns out that the amplitude of f is very small. A numerical calculation of the values of f at the points j/100 for 0 ≤ j ≤ 100 shows that max_{t∈[0,1]} f(t) − min_{t∈[0,1]} f(t) is about 6 · 10^{−8}. (Compare with [6, Remark 2].) Thus, we believe that, if one could calculate nG_{n}/F_{n+2} for values of n much larger than the values in Table 2, it would be possible to observe that the sequence is oscillating rather than convergent.

In any case, as the values of f, rounded to 6 places after the decimal point, are all 1.284328, the value of nG_{n}/F_{n+2} for large n, rounded similarly, should be about 1.284328 · \sqrt{5} = 2.871844. We do not know whether the deviation from the value of 2.8706, calculated in Table 2 for n = 6000, should be attributed to the O(1/n) term in (12), and would disappear if we could continue the table for much larger n, or something is still missing in the heuristics.

Finally, we note that the bounds in the proof of Theorem 2 are very similar to the main term on the right-hand side of (12). More careful estimates of ϕ_{k} than those of Section 3 could perhaps prove rigorously the heuristics indicated in this section.

References

[1] D. Barbolosi and P. J. Grabner, Distribution des coefficients multinomiaux et gbinomiaux modulo p, Indag. Math. 7 (1996) 129–135.

[2] K. J. Batenburg and W. A. Kosters, Solving Nonograms by combining relaxations, Pattern Recognit. 42 (2009) 1672–1683.

[3] J. Benton, R. Snow, and N. Wallach, A combinatorial problem associated with nonograms, Linear Algebra Appl. 412 (2006) 30–38.

[4] D. Berend, D. Pomeranz, R. Rabani, and B. Raziel, Nonograms: Combinatorial questions and algorithms, Discrete Appl. Math. 169 (2014) 30–42.

[5] D. Berend and S. Zucker, On the Number of Forceless Hint Sequences in Paint-by-Numbers Puzzles, in Proceedings of the 28th Canadian Conference on Computational Geometry, Vancouver, Canada, 2016, pp. 266–269.

[6] J. J. A. M. Brands, F. W. Steutel, and R. J. G. Wilms, On the number of maxima in discrete sample, J. of Statist. and Probab. Lett. 20 (1994) 209–217.

[7] R. Mullen, On determining paint by numbers puzzles with nonunique solutions. J. Integer Seq. 12 (2009), Article 09.6.5.

[8] N. Ueda and T. Nagao, NP-completeness results for Nonogram via parsimonious reductions, technical report, 1996, available at

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5277&rank=1.

[9] Wikipedia, entry on Nonogram, available at https://en.wikipedia.org/wiki/Nonogram.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A16, 60C05. Keywords: logic puzzle, nonogram, paint-by-numbers, number puzzle, multiple solutions, hint sequence.

(Concerned with sequence \underline{A304179}.)

Received January 17 2017; revised version received April 18 2018. Published in Journal of Integer Sequences, May 7 2018.

Return to Journal of Integer Sequences home page.