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.

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:

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

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. The co-ordinates of the guess are also recorded with the state on the stack.

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

Whenever a complete solution is found, or if a linesolver detects an inconsistency, the solver consults the stack. If no previous state exists, solving stops, and no more solutions will be sought or found. If a previous state does exist, the cell at the guess co-ordinates is checked to see if another guess can be made there.

(For example, with a two-colour puzzle, only a dot and solid are possible, and one of these will have been tried when the solution state was first recorded on the stack, so there is only one other possibility.)

If no other guess can be made, the state is popped off the stack and discarded. The next state on the stack is consulted, as before.

If another guess can be made at the same location, the current state is restored from the state on top of the stack (but the stack is not popped), the guess is applied to the current state, and the guess is eliminated from the stacked state. Line-by-line solving continues.

(An alternative, and perhaps more elegant approach is to pop and discard the top of the stack as soon as you eliminate the last possibility for the guessed cell. It is elegant since you're immediately getting rid of a state which is no longer useful, because it holds a cell which can't have any value – no need to store any information to say “there are no more possible solutions to try from this point”.)

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).