Nonograms are logic puzzles that originated in Japan in 1987. Fill an empty rectangular grid according to numeric clues at the sides to reveal a picture.

• To tell you about Nonograms
• To demonstrate an automatic on-line solver
• To allow Nonogram puzzles to be shared
• To record links to other Nonogram sites

For the CGI-based solver, there are two ways to enter it into the form before submitting it:

1. If your browser supports file-upload in forms, download an example puzzle to your machine, then specify it for upload in the field marked ‘Upload file’, and select the button along side it.

2. Use your browser to display the selected puzzle file, then use your local cut-and-paste facilities to copy that into the field marked ‘Use text’, and select the button along side it.

For the Java-based solver, only the second method is relevant. The applet displays a single writeable field into which you should paste the text.

Basically, I don't want you to take details of wholly commercial products (typically books and games) listed on this site as a recommendation from me to buy them. If I haven't seen a particular product, then in the strictest, most anally-retentive sense, I don't know whether it is worth you parting with your cash for.

Shareware isn't such a problem, since you can always try before you buy.

The lists are supposed to be of sites or pages about Nonograms, so I will list another site at Nonogram Solver according to one criterion: whether it has something to do with Nonograms. If you create a good page about Nonograms, I'll link to that.

When suggesting a link, please try to ensure that the Nonogram-related content is not diluted by other content. A visitor to my site does not want to have to wade through such content having been promised something relevant. This is ‘false information scent’ which will only annoy your visitors, and mine. If your Nonogram content must be only part of a page, please give it an id so it can be linked directly, e.g., http://example.com/games.html#nonograms.

If you want to link to my site (e.g., if you think your visitors would also like to look at my site), then feel free to link to it. This is the web — just link to whatever you like!

Please read the two previous answers. Links are not a form of currency, and the existence of a link in one direction does not imply that a reverse link should also exist. Link to my site if it enhances your content by being useful to the sort of people who would read it. Independently, I'll link to your site under a similar condition.

Kindly, no thankyou.

Old puzzles from the archive go to ‘Puzzle Heaven’.

Empty lines are denoted by the rule ‘0’.

No. As far as you (a manual puzzle solver) are concerned, it means nothing. It is only meant to be used by computer programs that read in puzzle files, and need an idea of how much space they should reserve for them. Even then, it's largely redundant.

The standard output of the solver takes the form a grid of ‘#’ and ‘-’ characters, which are the characters that the Unix utility atobm XBM:

$$ nonogram -os -i puzzle.non | atobm > puzzle.xbm

This may only work with a single solution. For multiple solutions, try writing out to multiple files: (bash example)

$$ nonogram -on 'puzzle.%d.txt' -i puzzle.non
$$ for i in puzzle.*.txt ; do
> atobm < "$$i" > "$${i:r}.xbm"
> done

You can convert from XBM format to PBM using xbmtopbm, and then by cjpeg or pnmtopng to convert to JPEG or PNG formats.

Firstly, have you provided a Nonogram puzzle in the correct format?

If you think you have, it's likely that you placed it in the form, but forgot to tell the form which of the two possible sources should be used. Make sure you select Upload file or Use text as appropriate.

Someday, I might make this a bit more user-friendly…

The on-line solver gives up after a minute or so, to avoid consuming too many resources on the server. It's quite possible that it will take many hours, days or longer to find a solution for this sort of puzzle, and it might not be the only solution.

If you really want to find the solution, or check that there is only one, I suggest that you install a solver on a machine of your own, and be prepared to leave it running for a very long time.

My software includes the packages nonolib and nonogram. You can download and compile them to produce a command-line solver, and there are some precompiled versions for some operating systems.

Use the command like this:

nonogram -i puzzle.non -on "solution-%d.txt"

It will read the puzzle from puzzle.non and write solutions as it finds them to solution-1.txt, solution-2.txt, etc. Use the switch -s N to make it stop after N solutions.

You could take a look at Jan Wolter's comparison of solvers, to see if there are faster alternatives.

Maybe you have inverted part of the data.

Row lines should be listed from top to bottom; column lines from left to right.

Column numbers should be listed from top to bottom; row numbers from left to right.

(You can, of course, invert any pair of orders, and produce a reflection or rotation of the solution.)

First, download a copy of the packages nonolib and nonogram.

Unpack and compile the library with:

unzip nonolib-*.zip
cd nonolib
make

Install, possibly as root, with:

make PREFIX=$$HOME/software install

The default value of PREFIX is /usr/local.

Unpack and compile the main program with:

$$ unzip nonogram-*.zip
$$ cd nonogram
$$ make CFLAGS+="-I$$HOME/software/include" \
  LDFLAGS+="-L$$HOME/software/lib"

Install, possibly as root, with:

$$ make PREFIX=$$HOME/software install

Again, the default location is /usr/local.

If you do this often on the same machine (e.g., when upgrading), consider setting up configuration files for the packages to find, for example:

$$ cat ~/software/include/nonolib-env.mk
PREFIX=$$HOME/software

$$ cat ~/software/include/nonogram-env.mk
PREFIX=$$HOME/software
CFLAGS += -I$(PREFIX)/include
LDFLAGS += -L$(PREFIX)/lib

…and then ensure that make can find these automatically:

$$ export MAKEFLAGS="-I$$HOME/software/include"

Fuller details at ‘How it works’

The solver functionality is divided into three sections:

• a line solver which takes a single, partially completed line and its rule, and works out as much information about the incomplete parts of the line as it can;

• a heuristic line-selector to determine the order that the rows and columns should be passed to the line solver;

• a recursive guesser/bifurcator for when the above methods don't give a complete solution. (This is absent from the Java applet.)

Line solvers

Ideally, a line solver should try all possible arrangements of solid blocks described by the rule that fit with what's already there — if any cell only works in all arrangements as a solid, then it must be a solid (and similarly, if any cell only works as a dot, then it must be a dot). Re-applying the line solver to a line it has just done does not produce any more information, but if the states of some of the cells that were left by the line solver can be determined by other means (e.g. by applying the line solver to a perpendicular line), then it's worth trying again.

Line selectors

The simplest line selector is one that iterates through each row and column continuously until no new information can be gathered (hopefully, by this time, you should have a solution). More complicated selectors involve ignoring lines that haven't developed new information since they were last processed by the line solver (which wouldn't be able to get any more information from them anyway).

The selector in use by this solver also estimates the complexity of each line, and skips the more complicated ones until it has eliminated the others. It computes a score for each line (the score having the opposite sense of complexity) using the expression:

T=(n+1)*sum(i=1,n,a[i])+n*(n-L-1)

…where n is the number of blocks in the line, L is the line length, and a[1] to a[n] are the lengths of each block. When non-negative, the score is the number of solid cells that can be determined from an empty line. A negative value indicates a shortfall of pre-determined cells, although it has no strict meaning (that I have worked out). Note that when n=1, and a[1]=L, then T=L, and this should be the maximum score.

Exceptionally, if n=0 (an empty line):

T=L

Recursive guessing/bifurcation

If the line selector stops with only a partial solution, the recursive guesser stirs it back to life by finding one of the undetermined cells and guessing its value. The selector now has (a little bit of) new information which may help it to solve the rest of the grid. However, the solution it produces may be incorrect, or may not be the only solution. So, after reporting the solution (if correct), the recursive guesser must track back to before the guess, make the opposite guess, and pass it to the line selector, possibly giving a new solution.

The guesser must be recursive because, after making the first guess, the line selector may stop again, and another guess must be taken, while still remembering the state before the previous guess. After deducing everything possible from that second guess (i.e. exhausting it), we still have to do its opposite guess before being able to go back to the previous guess to fully exhaust that.

In this algorithm, we try to push all blocks as far to one end as we can – without contradicting the rule or the known cells – and note the positions of the blocks. Then we do the same, but pushing to the other end of the line. Now, for each block, we look for an overlap of the same block in its two extreme positions — cells in this region must be solids belonging to that block. Similarly, we look for an overlap of the same gap in each of its extreme positions — such cells must be dots.

That's it! It's fairly simple, and fast, and gets most of the information that can be deduced. But it isn't guaranteed to get everything. Not infrequently, it will miss one or two cells from a line. This usually doesn't matter, as such a cell will likely be deduced from other information to be found later. But it does mean that occasionally bifurcation will occur when it's not really necessary.

Note that the ‘fast’ algorithm can always detect a contradiction in a line, so it can be used to determine the correct value for a ‘missed’ cell, so long as you can identify that cell.

This line solver exhaustively, and rather inefficiently, goes through all combinations of block positions, and merges all the results together. If a cell can only be (say) a dot in all of these combinations, it can be determined as a dot. I call the algorithm ‘complete’ because it will deduce everything which can be deduced from a single line, when applied.

This approach guarantees that the minimum amount of bifurcation will be necessary, but it's also very slow. However, there is one small optimization. It keeps track of the number of unknown cells which could not be both dots and solids in all the combinations tried so far — if this count reaches zero, the solver gives up. This is useful for quickly abandoning (say) long, empty lines with rules like ‘1.1’.

There are certainly better algorithms out there, i.e., ones that are both ‘complete’ and fast, and I am searching for them.

This is based on my understanding of the algorithm given here:

Like the ‘fast’ algorithm, it compares the positions of blocks pushed fully to one end of the line with positions of blocks pushed to the other. Where the two extremes agree (e.g., they both say that a solid is present), the algorithm makes an in-line conjecture for the opposite state (e.g., a dot), and checks for inconsistency. If it is inconsistent, the algorithm can eliminate the guessed state and (in a two-colour puzzle) deduce the other.

The algorithm is almost as fast as the ‘fast’ algorithm. It appears to be almost complete, but that might be because I haven't fully understood the Olšáks' real algorithm yet.

The solver can solve any correct puzzle (one derived from a bitmap image) that doesn't involve guessing and has only one solution (it can be derived from only one image). It can solve some (perhaps all, but not proven, possibly?) correct puzzles that have more than one solution. It won't necessarily solve correct puzzles where some guesses lead to incorrect solutions, and it won't correctly solve incorrect puzzles. Gibberish'R'Us!