cp's OEIS Frontend

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

%I A242876 #60 Aug 06 2025 20:19:36
%S A242876 1,2,14,384,52362,25309575,49745060669
%N A242876 Number of n X n nonograms (hanjie) which can be solved uniquely.
%C A242876 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.
%C A242876 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.
%C A242876 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
%C A242876 Ueda & Nagao show that determining uniqueness for a nonogram, given its hint sequence, is NP-complete. - _Charles R Greathouse IV_, Oct 28 2022
%D A242876 N Ueda and T Nagao, NP-completeness results for NONOGRAM via parsimonious reductions, unpublished technical report (1996).
%H A242876 Bertram Felgenhauer, <a href="https://int-e.eu/nono">Counting Nonograms</a>
%H A242876 Wikipedia, <a href="https://en.wikipedia.org/wiki/Nonogram">Nonogram</a>
%F A242876 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]
%e A242876 There are two 1 X 1 grids, filled and unfilled, and both can be distinguished, so a(1) = 2.
%e A242876 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.
%o A242876 (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);
%o A242876 nonomat(M)=vector(matsize(M)[1],i,nono(M[i,]));
%o A242876 nono2(M)=[nonomat(M),nonomat(M~)];
%o A242876 num2mat(d,n)=matrix(d,d,i,j,bittest(n,(i-1)*d+j-1));
%o A242876 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]);
%Y A242876 Cf. A384764 (number of n X m nonograms which can be solved uniquely).
%Y A242876 Cf. A002416 (number of n X n nonograms).
%Y A242876 Cf. A000079 (number of 1 X n nonograms which can be solved uniquely; they are fully determined by the n column hints).
%Y A242876 Cf. A000045.
%K A242876 nonn,hard,more
%O A242876 0,2
%A A242876 _Charles R Greathouse IV_ and Sophia Greathouse, May 25 2014
%E A242876 a(5) from _Mark E. Shoulson_, Aug 13 2014
%E A242876 a(6) from _Karl W. Heuer_, Jan 29 2015
%E A242876 a(0) = 1 prepended and a(6) corrected by _Bertram Felgenhauer_, Jun 08 2025