Thoughts Concerning Nonograms

This writing is a collection of my ideas that have not been written down before now.         I'll be
listing some basic rules for solving and validating nonograms and whatnot that I've thought of and I
will add to this article as I think of more and feel the want.


I  intend to  write a nonogram game  soon for an event  and so nonograms  have been  in my  thoughts
lately.   When playing a nonogram game and mulling over how to complete it while contributing little
thought, I noticed the rules that may be derived for completing such a puzzle, based entirely around
determining those values which must be filled in.   In mulling over writing an automatic solver, the
matter of validating that a nonogram puzzle description is valid is also an important one.  I wonder
if a nonogram could be solved entirely with a small set of rules, without the need for any manner of
backtracking approach  that would speculatively fill in values and determine if the puzzle  could be
solved from such a point.   I've also been giving good thought to implementation strategies that are
simplest in computing and storage requirements, with the small virtual machine targeted being a good
testing grounds for such thinking.

A  nonogram description  will be composed from three integral values X,  Y,  and Z,  which  form the
horizontal length, vertical length, and value depth of the puzzle, respectively; there would then be
a  ZX  +  ZY  values which indicate the main components of the puzzle,  those integral values  which
indicate  the contiguous segments for the rows and columns.   The value N will be used for  X  or  Y
where  the particulars aren't important,  as rules typically work equally well with rows or columns.

I will firstly be discussing validation.      Complete validation of a nonogram specification may be
equivalent to solving it.          Spurious zeroes in the segment values can be ignored well enough.
Firstly,  the segment values not equal to zero should be counted,  this count decremented,  and this
count  added to the sum of the segment values should not exceed N;  that is to simply write that the
holes between each segment is at least one and, clearly, a nonogram description in which the segment
lengths  and holes  is larger  than can fit  in a row or column  is invalid.   Secondly, the row and
column segment values  must agree;  a trivial figuring  for a subset  of possible  disagreements  is
merely determining that,  for any row demanding V filled values, there are W columns that supply any
filled values,  and  vice-versa;  more complex  rule-based  figuring  on this could be done,  but is
perhaps  best employed  between  rule applications,  once a suitable  amount of always or never used
values have been determined.

I will secondly be discussing automatic solving.         A valid nonogram can clearly be solved by a
machine,  even if only by testing every possible combination;  for that matter,  an invalid nonogram
could be ruled invalid by such a method.      A nonogram doesn't necessarily have a unique solution.
Firstly,  a rather simple  rule is when there  is one segment  specifying a length N;  clearly,  the
entire row or column is filled as the only solution.   Secondly, when the segment length is N-1,  it
is known that all but the first or last values are filled.   There are many similar rules that could
be specified, but are best shown through visual methods.

Visual proofs will be added to this document shortly.
.