The solver software takes a fairly conventional approach of solving a whole Nonogram puzzle by tackling just one line at a time. The intention is not necessarily to solve each line completely in one go, but to partially solve it in several turns, each time determining none, some or all of the remaining unknown cells' states.

Note that this doesn't mean that you just keep applying this operation to the same line continuously. Subsequent applications will have no further effect on the state of the line, i.e., the operation is idempotent. Instead, knowledge of the state of the line must be increased between these operations by some other operation. In practice, that means applying the operation to a perpendicular line (or occasionally guessing).

The partial solutions of one line will almost always be interleaved with the partial solutions of other lines. After a cell's state is determined while working on one line, that information is available to the perpendicular line which crosses the first line through that cell, so each partial solution fuels subsequent perpendicular attempts, until either a complete solution to the puzzle is found, or the ‘fuel’ runs out.

A linesolver is an algorithm applied to a line to partially solve it. It is supplied with the line's current state (made up of dots, solids and unknown cells), plus the rule or clue applying to the line, and generates a new line state.

A linesolver may detect and report that the current state of the line is inconsistent with the clue. Indeed, it must do so if the line appears to be complete, as the over-all solver relies on this to check the final answer.

The solver can use several different linesolvers, even on the same puzzle. They are arranged in some rank order (e.g., with 1 being the highest rank), and the solver will not apply a linesolver to any given line until all lower-ranking linesolvers have been applied in sequence and have failed to yield more ‘fuel’.

A linesolver is not required to get all information logically deducable from a line – it may omit some or even all of the information. Higher-ranking linesolvers are usually expected to get more information than lower-ranking ones, which are conversely expected to be faster.

fast

A fast linesolver which gets most of the available information

complete

A diligent linesolver which gets everything logically deducable, but very slowly due to inefficiency

olsak

A variation of fast which gets everything by looking more closely in the places which fast often misses

fcomp

A revised version of complete which gets everything while carefully avoiding inefficient duplication of work

The solver does not simply iterate over each row and column applying linesolvers, but keeps track of which lines contain ‘fuel’ – cells which were determined since the line was last processed. Per line, it records the rank of the lowest-ranking linesolver which has not been applied to that line since cells were determined. The solver will not choose a line of a higher rank if a lower one exists.

Furthermore, the solver makes a heuristic evaluation of each line, estimating how much fuel it will produce after a single turn of line-solving. When several lines of the lowest rank exist, it chooses the line with the highest heuristic evaluation, which is given initially by:

…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):

It is possible that the solver will run out of fuel before completing the solution, i.e., all linesolvers have been applied to all lines, yet there are still unknown cells. In this case, the solver applies bifurcation.

The current state of the solution is recorded on a stack, then a guess is made, according to some heuristic. A guess consists of the co-ordinates of an unknown cell, and a possible state for it. The guess is applied to the current state as if it were true, but it is also applied to the stacked state as if it were false. Line-selection heuristics also need to be stored in both states.

The change made by the guess on each state acts as new fuel for the linesolvers, so the solver can return to line-by-line partial solving.

Whenever a complete solution is found, or if a linesolver detects an inconsistency, the solver consults the stack, and can discard the current state. If no previous state exists, solving stops, and no more solutions will be sought or found. Otherwise, the previous state is restored as the current state.

(For example, with a two-colour puzzle, only a dot and solid are possible, and one of these has just been explored to completion. The other awaits on the stack to be tried.)

From any particular guess, if no more guesses are necessary, the solver will work its way through all possible solutions which are consistent with that guess, even if that is none.

By induction, even if further guesses are necessary (i.e., the stack grows further), the solver will go through all such solutions, so there is no need to try guesses that parallel the first guess (i.e., in other cells from the same state).

Here are some unimplemented ideas about using multithreading to exploit multiple processor cores.

Jan Wolter talks about how his solver tries to speed up finding the first solution by probing several guesses before committing to one. He raises the point that, while this does seem to help, it wastes the information learned from the probes, and his efforts to re-use some of that information were in vain.

Perhaps the concurrency plan above could help here. Not only could we start solving any stacked state when we have exhausted a guess, but we could also stop working on a guess temporarily if it seems to be getting nowhere. How could we determine this condition, and how would we choose another state?

Let each state include a count of how many guess have been involved so far; this is zero for the original state. When bifurcating, that count is incremented just before the state is duplicated.

Now, at any time, you can compute the ratio of guesses against the number of cells determined. As this increases, the state is seen to be less productive; if it exceeds a threshold, put it aside and choose something else. Which to choose? — one with the lowest ratio.

(It might help to give a guess more significance in this ratio by raising it to a certain power (e.g., squaring it), or using it as a power.)

Perhaps this will avoid the deep guessing down the wrong paths that delays the finding of the first solution so much. Instead, the solver will jump sideways occasionally and choose something else to do, without forgetting the work it's already done.