Index  Comments

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.