A242876 Number of n X n nonograms (hanjie) which can be solved uniquely.

1, 2, 14, 384, 52362, 25309575, 49745060669

Offset: 0

Author

Charles R Greathouse IV and Sophia Greathouse, May 25 2014

Keywords

• nonn
• hard
• more

Comments

In this game there is an n X n grid where each square may or may not be filled. Each column and each row is labeled by the length of each successive block of filled squares, but without indication of the number of unfilled squares in between. The object is to determine which squares are filled.

100% of the 1 X 1 grids can be solved uniquely. 87.5% of the 2 X 2 grids can be solved uniquely. 75% of the 3 X 3 grids can be solved uniquely. About 80% of the 4 X 4 grids can be solved uniquely.

About 75% of the 5 X 5 grids can be solved uniquely, and about 72% of the 6 X 6 grids can be solved uniquely. - Charles R Greathouse IV, Apr 22 2015

Ueda & Nagao show that determining uniqueness for a nonogram, given its hint sequence, is NP-complete. - Charles R Greathouse IV, Oct 28 2022

Examples

			There are two 1 X 1 grids, filled and unfilled, and both can be distinguished, so a(1) = 2.
Of the 16 2 X 2 grids, only 10/01 and 01/10 cannot be distinguished (both have one block of length 1 for each row and column) and so a(2) = 14.
		

References

• N Ueda and T Nagao, NP-completeness results for NONOGRAM via parsimonious reductions, unpublished technical report (1996).

Links

• Bertram Felgenhauer, Counting Nonograms
• Wikipedia, Nonogram

Crossrefs

Cf. A384764 (number of n X m nonograms which can be solved uniquely).

Cf. A002416 (number of n X n nonograms).

Cf. A000079 (number of 1 X n nonograms which can be solved uniquely; they are fully determined by the n column hints).

Cf. A000045.

Programs

PARI

nono(v)=my(u=List(),t); for(i=1,#v,if(v[i],t++,if(t,listput(u,t);t=0))); if(t,listput(u,t)); Vec(u);
nonomat(M)=vector(matsize(M)[1],i,nono(M[i,]));
nono2(M)=[nonomat(M),nonomat(M~)];
num2mat(d,n)=matrix(d,d,i,j,bittest(n,(i-1)*d+j-1));
a(n)=my(v=vector(2^n^2,i,nono2(num2mat(n,i)))); v=vecsort(v,lex); sum(i=2,#v-1,v[i]!=v[i-1] && v[i]!=v[i+1])+(v[1]!=v[2])+(v[#v]!=v[#v-1]);

Formula

a(n) >= F(n)^2 * a(n-1), since there are F(n) ways to fill the last row (resp., column) such that the first and last squares are filled and no consecutive squares are unfilled. These configurations can be solved without looking at the other rows or columns and so allow expanding an (n-1) X (n-1) configuration to an n X n configuration. Thus a(n) >> phi^(n*(n+1))/5^n. (F(n) is the n-th Fibonacci number, A000045.) - Charles R Greathouse IV, Sep 02 2014 [Corrected by Bertram Felgenhauer, Jun 09 2025]

Extensions

a(5) from Mark E. Shoulson, Aug 13 2014

a(6) from Karl W. Heuer, Jan 29 2015

a(0) = 1 prepended and a(6) corrected by Bertram Felgenhauer, Jun 08 2025