The Great Nonogram Hunt

Nonograms are a kind of Japanese image puzzle akin to Soduko, or perhaps Minesweeper. The puzzle solver’s goal is to find an image on a rectangular pixel grid that adheres to certain row and column descriptions.

A Nonogram Puzzle - Solved

A Nonogram Puzzle - Solved

A Nonogram is a square grid, with half the squares blacked in. Looking along a row or column, there will be several blocks of blacked in squares, separated by white. The order and length of these black blocks is used to describe the row or column. For example, look at the second row in the figure which has one black square by itself and then three adjacent black square so it is described as “1,3”.

The description is deliberately ambiguous. It tells nothing about how the white squares are arranged! A row starting with one black square, one white square, then three black squares and finishing with another white square would also be described as “1,3”. This ambiguity is what makes a nonogram an challenging puzzle. The puzzle player is presented with an empty grid and the description of each row and column. The player must then work through the descriptions, filling in the squares as the ambiguity is resolved.

How?

Computer scientists have a lot of fun coming up with clever algorithms to solve nonograms, which you check out in the references given by this paper by K. Joost Batenburg. Human solvers however usually approach the puzzle by looking at individual lines. Although the description is ambiguous, there is sometimes enough information to see that some squares MUST be black, no matter how the white squares are arranged. For example, if the nonogram of size 5 by 5 has a row with the description of “4” then there can be only one white square, either at the beginning or the end of the row, and so the middle three squares must be black. Now we can look at the middle three columns, with the extra knowledge of where one black square must be. Combining this knowledge with the column descriptions should result in finding more unambiguously black squares. So the puzzle solver proceeds step by step, looking at individual rows and columns, chipping away at the ambiguity until all the black squares have been found and the descriptions all match.

Not every possible nonogram can be solved this way. If we look at 15 by 15 square nonograms and consider only those that have exactly 113 ( out of 225 ) black squares there are 10 ^67 possible arrangements ( slighty less than the number of atoms in the galaxy ) then about 1 in 10 of these are soluble using the ‘single line algorithm’.

Working for a client, Raven’s Point has developed a program which works its way through the possible nonograms attempting to solve them by the single line algorithm and outputting each one that is found to be humanly solvable.

Over Easy or Hard Boiled?

A nonogram might be solvable by the single line algorithm, but that doesn’t mean it is easy.  In fact, many of them are insanely difficult.  We need to distinguish between easy and hard, in order to encourage newbies and challenge the jaded.

Batenburg suggests counting the number of steps required to solve a nonogram as a measure of its difficulty.  However, humans can recognize patterns and fill in chunks without taking things step by step.  They will also get lost, or bored where the computer keeps tediously plugging away filling one more black square.  It would be preferable to have a measure of the difficulty level that can take into account human foibles.

Obviously the size of the nonogram is important.  The more pixels, the harder the puzzle will be.

Difficulty is proportional to size * size

Long blocks of black squares are very helpful.  A block of 4 squares in a 5 by 5 nonogram pretty well gives the game away.  However in a  15 by 15 nonogram it is nice to have, but not nearly so significant.  So the ratio between the block length and the size is important, and the more relatively long blocks there are the easier the puzzle will be.  The mathematical trick used to focus on large numbers and more or less ignore small numbers is to square everything and add them together ( 1*1 + 1*1 + 1*1 +1*1 = 4, but 4*4 = 16 )

Difficulty is inversely proportional to the sum of squares of the relative block lengths

Assuming that the largest nonogram we are ever going to trouble ourselves with is 15 by 15, then we can specify the ‘relative block length’  as

15 * blocklength / size

Combining this into one

Difficulty is proportional to size * size / sum (  ( 15 * blocklength / size ) ** 2 )

Now we can multiply by an arbitrary parameter, usually called k, to make everything come out into a convenient range, say 1 ( easy ) to 10 ( hard )

Difficulty = k * size * size / sum(  ( 15 * blocklength / size ) ** 2 )

The really great thing about this is that it can be calculated before the nonogram is solved.   So, although we have reduced the frequency of nonograms, by filtering out any with unwanted difficulty level, we only need to spend time attempting to solve ones we find with the required difficulty level.  We have to hunt through many more nonograms to find the ones we want, but the hunt goes a great deal faster.

Advertisements
This entry was posted in Projects. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s