A384764 -id:A384764 - cp's OEIS frontend

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

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

Offset: 0

Charles R Greathouse IV and Sophia Greathouse, May 25 2014

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

			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.

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

Bertram Felgenhauer, Counting Nonograms
Wikipedia, Nonogram

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.

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]);

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]

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

A385862 Number of n X m yesnograms that can be solved uniquely, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 14, 8, 1, 1, 16, 52, 52, 16, 1, 1, 32, 210, 368, 210, 32, 1, 1, 64, 816, 2992, 2992, 816, 64, 1, 1, 128, 3206, 23058, 49578, 23058, 3206, 128, 1, 1, 256, 12536, 179576, 775204, 775204, 179576, 12536, 256, 1, 1, 512, 48962, 1388978, 12129616, 24177516, 12129616, 1388978, 48962, 512, 1

Offset: 0

Karl W. Heuer, Aug 06 2025

In a nonogram puzzle, there is a hidden bitonal grid (or 0/1 matrix), and each row and each column is labeled by the length of each successive block of foreground pixels, but without indication of the number of background pixels separating them; the object is to determine the grid contents. In this variant, called a "yesnogram", the pixel value that represents foreground for row clues is the complement of the value that represents foreground for column clues.

			For the 3 X 4 grid shown below, the row clues (counting runs of 0s) and the column clues (counting runs of 1s) are sufficient to reconstruct the grid, so this is one of the 2992 solvable grids counted in A(3, 4).
       | 1 3 1 2
   ----+--------
   1   | 0 1 1 1
   1 1 | 0 1 0 1
   2   | 1 1 0 0
Top left corner of the array:
  1,  1,   1,     1,      1,        1,         1, ...
  1,  2,   4,     8,     16,       32,        64, ...
  1,  4,  14,    52,    210,      816,      3206, ...
  1,  8,  52,   368,   2992,    23058,    179576, ...
  1, 16, 210,  2992,  49578,   775204,  12129616, ...
  1, 32, 816, 23058, 775204, 24177516, 754845831, ...

Bertram Felgenhauer, Antidiagonals n+m = 0..13, flattened
Bertram Felgenhauer, Counting Nonograms.
Wikipedia, Nonogram.

Cf. A242876 (solvable n X n nonograms), A384764 (solvable n X m nonograms), A383345 (solvable n X 2 nonograms or yesnograms), A385861 (solvable n X n yesnograms).

A(0,n) = 1, and A(1,n) = 2^n. A(n,m) = A(m,n), because a grid is solvable iff its complement-transpose is solvable.

A383345 Number of uniquely solveable n X 2 nonograms (hanjie).

Original entry on oeis.org

1, 4, 14, 52, 210, 816, 3206, 12536, 48962, 191226, 746456, 2913544, 11371040, 44376798, 173181564, 675834086, 2637392942, 10292179494, 40164144690, 156736057740, 611644171812, 2386868430698, 9314465669046

Offset: 0

Bertram Felgenhauer, Jun 11 2025

In this game there is an n X 2 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.

The only ambiguous row hint is 1, which has the same solutions regardless of whether black or white squares are counted. So this is also the number of n X 2 "yesnograms".

			a(2) = 16-2 because out of the possible 2^(2*2) grids, only 10/01 and 01/10 have the same row and column clues.

Bertram Felgenhauer, Counting Nonograms.
Wikipedia, Nonogram.

Column m=2 of A384764. Also column m=2 of A385862 (n X m yesnograms).

Cf. A242876.

A385861 Number of n X n yesnograms that can be solved uniquely.

Original entry on oeis.org

1, 2, 14, 368, 49578, 24177516, 46985524156

Offset: 0

Karl W. Heuer, Aug 06 2025

A nonogram provides row and column clues indicating runs of black pixels, treating white as blank. In this variant (called a "yesnogram"), the row clues instead indicate runs of white pixels, treating black as blank. Column clues remain unchanged from the standard nonogram.

			a(2) = 14 because, of the 16 2 X 2 grids, 10/01 and 01/10 would have the same set of clues; the other 14 are solvable.

Bertram Felgenhauer, Counting Nonograms.
Wikipedia, Nonogram.

Main diagonal of A385862.

Cf. A242876 (solvable n X n nonograms), A384764 (solvable n X m nonograms), A383345 (solvable n X 2 nonograms or yesnograms).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A385862 Number of n X m yesnograms that can be solved uniquely, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A383345 Number of uniquely solveable n X 2 nonograms (hanjie).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A385861 Number of n X n yesnograms that can be solved uniquely.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs