How it works
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.
Partial solving of lines
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.
- A fast linesolver which gets most of the available information
- A diligent linesolver which gets everything logically deducable, but very slowly due to inefficiency
- A variation of fast which gets everything by looking more closely in the places which fast often misses
- 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:
n is the number of blocks in the
L is the line length, and
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
T=L, and this
should be the maximum score.
n=0 (an empty
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.
Concurrent line processing
(This already exists in the Java solver, but I disabled it because it was unreliable.)
It is possible to solve more than one line of a puzzle at once. Solving two parallel lines is straight-forward, but what if you choose two perpendicular ones?
It depends on where they cross. If the cell is already known, there's no problem; neither thread will alter that cell. Otherwise, the first thread to finish might invalidate the work of the second, which then has to be discarded.
For this reason, it should be better not to allow a thread to work on a line if it crosses another line that is already being processed, unless their common cell is already fully known.
In practice, this doesn't work too well. The first line to be processed will block the processing of all perpendicular lines because all its cells are incomplete. All other threads will then settle on parallel lines, which reinforces the blockade on the perpendicular lines; They can't easily be selected because there tends to be at least one line being processed that intersects them at an unknown cell. As a result, the solver fixates on just one dimension, even when lines in the other dimension might be heuristically preferable.
Perhaps threads should try not to choose parallel lines unless they are heuristically much better than the best perpendicular lines, even if the perpendicular lines are currently blocked.
Concurrent processing of guesses
When a pair of complementary guesses is made, you push one onto the stack, and continue processing the other one. Eventually, you'll finish processing it (and any subsequent guesses), discard it (and the other fully processed guesses), and start processing the other.
But why process that other one then? What about the others pushed onto the stack earlier? They all represent complementary guesses to be investigated, so why do them in any particular order? In fact, this set of states is not really a stack at all! Indeed, if you have the parallelism available, why not do several at once?
Instead of a stack, regard the states as a collection of outstanding jobs, and get several threads to consume them as they become idle.
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.