When you're solving a puzzle, you normally attempt to extract as much information from each line as possible, and then use this extra information to get more information from perpendicular lines, which in turn gives you more information about the first set of lines, etc.

For some puzzles, you reach a point where you've extracted all the information you can that way, but there are still some cells left undetermined. (I call such a point in the solution process an ambiguity.) Your only recourse at this point is to choose an empty cell, guess its value, then proceed as before. You may yet encounter further ambiguities for which you must make further guesses.

Proceeding from an ambiguity may lead to a correct solution or an inconsistency. Having made one guess from an ambiguity and determined its conclusion, the solver should make an alternative guess from the same state, and proceed to discover other solutions, inconsistencies or more ambiguities (to be handled recursively), until one is satisfied that all possible conclusions have been reached.

For a computer program, this isn't a problem — it can trivially record the state it was in at the ambiguity, and return to it later to make the alternative guess. For a human (well, for me, at least), the best thing to do is to find a guess that quickly leads to an inconsistency, then you can quickly infer that the alternative guess must be true (or there is no solution) — this minimises the amount of state that must be remembered.

1. Does an ambiguity in a correct puzzle (i.e. one that has at least one solution) always lead to two solutions (or a doubling of solutions with each level of ambiguity)? In other words, must the guess always be right (for a correct puzzle)?

2. Does one have to make a pair of guesses for each undetermined cell at an ambiguity, or does guessing for one cell implicitly make a guess for the others (upto the next ambiguity)? Generally, at an ambiguity with n undetermined cells, should a solver make 2n guesses, or just 2?

3. At an ambiguity, suppose we make a guess (a cell location and the new state of that cell) X₁, and from it we can derive another state-location tuple X₂, then there would have been no point in guessing X₂ instead of X₁. Can we work out an algorithm to select/find the better guess X₁, given our initially intended guess X₂, thus reducing the number of guesses we have to recursively make?

4. If we apply that algorithm to its own result repetitively, can we find an optimum guess? Do we get a loop?

The first question may be answered by visiting Hirofumi Fujiwara's Nonogram pages, which include some ambiguous puzzles with only one solution (try ‘Dog’ and ‘Rabbit’), so the answer is “no”. Before I added solution-checking to my solver, it produced numerous solutions for a couple of these puzzles, but I could see that some were wrong. After adding the checker, only one correct solution was produced. The presence of any correct solutions alongside wrong ones proved that some of the guesses were wrong. This leads to a further question: what's the simplest such puzzle that can be constructed?

My solver currently assumes that the second part of the second question is true. But previously, you could reverse this by compiling the library with the C macro nonogram_GUESSAGAIN defined — this isn't possible any more. When I tried that with one of puzzles, it produced several thousand correct solutions, some of which (chosen arbitrarily) were identical. (I didn't feel like checking them all).

An argument for making fewer guesses is that, after making one guess (at cell c₁ to state s₁), we may be able to determine the state s₂ of another cell c₂ which we could have chosen for a guess instead of c₁. Anything we derive from (c₂, s₂)must also be derivable from (c₁, s₁), so when we back-track to try alternative guesses from (c₁, s₁), we know that a guess (c₂, s₂) will provide no information that wasn't provided by (c₁, s₁).

But what about trying (c₂, ¬s₂) in place of (c₁, s₁)? Firstly, since we chose (c₁, s₁), we should also try its opposite, (c₁, ¬s₁), which will produce one of three possibilities:

1. (c₂, s₂)

2. (c₂, ¬s₂)

3. (c₂, ?), i.e. another ambiguity is reached

For case 1, c₂ must be s₂ irrespective of c₁, so guessing (c₂, ¬s₂) must lead to an inconsistency. For case 2, we can determine no more information from guessing (c₂, ¬s₂) instead of (c₁, ¬s₁). For case 3, when another ambiguity is reached, either c₂ will be chosen for another guess, or another cell will be chosen, which may indirectly determine c₂. Therefore, making a guess at c₁ means that no alternative guess at c₂ is required.

In summary, after making a pair of guesses at c₁, there are 3 × 3 combinations of consequences for c₂:

(P is a point of ambiguity; Q_n is some point after making a guess in c₁ at P.)

Each entry gives a reason why each of the guesses for c₂ does not have to be made after trying the guesses for c₁. “NXI” means “no extra information”, i.e. the guess at c₁ would already have derived at least as much information as the guess at c₂. “I” means “inconsistency” — the guess would not lead to any solutions. “WBT” means “will be tried” — another ambiguity was reached by the guess at c₁, so one or more subsequent guesses would have been made that would eventually fill c₂, so a guess there instead of c₁ would imply NXI. If the pair of guesses at a subsequent ambiguity both lead to inconsistency, then the grid was already insoluable at the previous guess.

Here are some rather different ways of solving Nonograms computationally:

Thanks go to James Lundon for pointing out the NP-completeness paper, which may be able to show whether Nonograms can have only one solution, yet the solver will have to make a guess. I haven't read it fully yet, and it's rather going over my head.

Suppose we describe the ‘thoughts’ of a Nonogram solver graphically. We draw a tree with its root at the top, denoted by a square outline. Logical, line-by-line processing is then represented by a vertical line projecting down below it. A complete solution is then denoted by a solid square. An ambiguity could be shown as the vertex formed by the base of a processing line and two diagonally downward lines representing the two guesses made at that point. (The vertex should be labeled with the details of the guess.) These guesses then continue as vertical lines to show further processing. An inconsistency can be shown as a square outline containing a cross.

We can use this puzzle trace to summarise the nature the puzzle (it gives the number of solutions, the amount of guesswork involved, whether any guesses can be wrong), and so we can describe its complexity and difficulty.

If we consider a puzzle with a number of ambiguities, we can see that many similar trees may be generated from it, depending on what guesses are made, and in what order. Are there any rules that allow two such trees to be equated with each other? For example, they should both have the same number of solutions, but are there any transformations that allow one tree to be converted to any other from the same puzzle, while not becoming a tree from a different puzzle? Can we ‘define’ a canonical representation, and therefore give a canonical measure of complexity?

My Nonogram-solving software tackles a puzzle by considering only one line at a time, and attempting to partially solve that line. Information it gets from one line can be fed into the processing of a perpendicular line, and so on, until the puzzle is solved.

Until recently, I've been using two algorithms to partially solve lines.

The original algorithm is called ‘complete’. It systematically finds all valid arrangements of solids, and generates a complete result from that. That is, a certain amount of information can be obtained logically from a line in a given state and its clue, and this algorithm gets all of that. (It doesn't mean that it necessarily determines the states of all unknown cells!)

But it is a little too diligent, wasting time on arrangements which do not need to be considered.

Consider a line of 10 cells, all unknown, and the clue 3.3. The first block has 4 possible positions, and in each of these, it leaves the second 4, 3, 2 and 1 positions, hence 10 arrangements in total:

  1       >###-###---<
  2       >###--###--<
  3       >###---###-<
  4       >###----###<
  5       >-###-###--<
  6       >-###--###-<
  7       >-###---###<
  8       >--###-###-<
  9       >--###--###<
 10       >---###-###<

This pattern has an arithmetic progression on the length of the line minus the minimum space required by the blocks, x, so the algorithm has complexity O(x²) for two blocks, and probably turns into O(xⁿ) for n blocks. Consequently, the algorithm can be very slow on the more difficult lines.

In fact, we only need to consider the following seven arrangements:

  1       >###-###---<
  2       >###--###--<
  3       >###---###-<
  4       >###----###<
  7       >-###---###<
  9       >--###--###<
 10       >---###-###<

Note that no block needs to move leftwards.

I realised that another algorithm existed, that would be much simpler and faster. I refer to it as the ‘fast’ algorithm.

This pushes all blocks to their left-most positions, then to their right-most, and compares these two extremes. Consider a line of 10 unknown cells, and the clue 4.4:

leftwards  >####-####-<
rightwards >-####-####<
solution   > ###  ### <

Where a block overlaps itself in its extremes, the algorithm can deduce a solid; similarly, dots, where the same gap overlaps itself.

This is much faster than the ‘complete’ algorithm, but it can miss some dots occasionally.

So, which algorithm should we choose? Here are some options:

• Use ‘fast’ alone, but back it up with bifurcation.

  I implemented this ages ago, since bifurcation is necessary in general anyway, even when using a complete linesolver.

• Use ‘fast’ first, then ‘complete’ only if ‘fast’ failed to determine anything.

  I also implemented this some time ago, partly to make it easier to replace and combine as-yet unwritten algorithms. You can configure the software to use a stack of any number of linesolvers.

• Write a new complete algorithm which avoids many arrangements by not moving any blocks towards the left (except at the start). It should be similar to ‘fast’ in speed.

I've been struggling to realise the third option for some time, while requesting ideas and help here. Over the years, a number of people have offered their thoughts (or implementations) on the matter:

• Mikael Lagerkvist suggested the use of regular expressions as a comprehensive implementation.

  Gecode: Nonogram Class Reference — A Nonogram-solving part of a constraint library in C++

  

• Petr & Mirek Olšák adapted the fast algorithm to make it complete by making extra guesses locally within the line.

  Griddlers solver, nonogram solver — A solver by Czechs Petr Olšák and Mirek Olšák (does colours too!) — portable GPL C source and Windows binary

  

• Most recently, Thomas Nygreen sent me some ideas which helped an implementation to crystalize in my mind.

• I recall that a number of others have emailed in the past, with ideas, or with implementations in Haskell or OCaml (which, I regret, I'm still not familiar with), but there are too many details to go over here!

My thanks go to all those people, along with my apologies for not responding in all (a lot of) cases!

Anyway, I have now implemented what appears to be a fast and complete algorithm, which I have named ‘fast-complete’, and labelled fcomp:

It is already incorporated into the software, including the on-line solver, but not the Java applet.