Journal of Integer Sequences, Vol. 21 (2018), Article 18.4.2

The Asymptotics of Useless Hint Sequences in Nonograms

Daniel Berend
Departments of Mathematics and Computer Science
Ben-Gurion University
Beer-Sheva 84105

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


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence 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