A computer Nonogram solver usually alternates between two jobs: solve individual lines under the current constraints and propagate every newly forced cell into the crossing lines. If that process reaches a fixed point before the grid is complete, stronger solvers can probe assumptions or branch through the remaining possibilities.
Different programs implement the details differently, but that line-analysis → propagation → search structure is a useful model for understanding them.
1. Represent the puzzle as constraints
The solver stores:
- the row clue sequences;
- the column clue sequences;
- the current state of every cell: filled, empty, or unknown.
Each row and column is a one-dimensional problem: find arrangements of its clue blocks that agree with all known cells.
A complete grid is valid only when every line has at least one compatible arrangement and all cells agree at row-column intersections.
2. Solve one line
A line solver tries to determine which cells are forced by that line's clues and current known states.
There are several implementation strategies.
One practical strategy, documented by WebPBN's pbnsolve, finds a legal placement with blocks pushed as far as possible toward one end and another toward the opposite end. Cells occupied by the same block in both extreme placements can be marked filled; cells proven to lie between the same blocks can be marked empty.
More complete line solvers can enumerate or dynamically compute all valid line patterns consistent with the current state and intersect them.
3. Put affected crossing lines back on the work list
Suppose a row solver proves cell R4C7 is filled.
Column 7 now has new information. A good implementation does not need to restart the whole puzzle blindly; it can schedule that affected column for another pass.
If the column then forces cells in rows 2 and 8, those rows become candidates for reprocessing.
This is the programmatic form of the same row-column rhythm human solvers use.
4. Continue until propagation reaches a fixed point
The solver keeps processing useful lines until either:
- every cell is determined;
- a contradiction appears;
- no line can produce another forced cell.
The third state is a fixed point under the current solving method. It does not automatically mean the puzzle has multiple solutions or no logical solution. It means this particular inference engine cannot progress directly.
A stronger line solver might still find a forced state that a cheaper one missed.
5. Detect contradictions
A contradiction occurs when the current assumptions make some constraint impossible.
Examples include:
- a line has no valid placement;
- a confirmed block is longer than its clue;
- a required block cannot fit anywhere;
- a cell has been forced both filled and empty through incompatible branches.
In pattern-based terms, a line with zero valid patterns is impossible.
This makes contradiction detection useful both for validating player states and for search algorithms.
6. Use probing or search when direct logic stalls
A complete general solver may need to explore alternatives.
A simple depth-first approach can:
- choose an unknown cell or block decision;
- assume one legal state;
- run propagation again;
- continue if the branch remains possible;
- backtrack if it reaches a contradiction.
A probing strategy explores candidate assumptions temporarily and measures their consequences before deciding which branch to commit to. WebPBN's pbnsolve documents this approach in detail.
The important distinction is that a computer can use search to guarantee completeness even when human-facing logic has stalled.
7. Check uniqueness
To validate a puzzle, finding one solution is not enough.
A solver can continue searching after the first solution and ask whether a second distinct completion exists.
The outcomes are:
- zero solutions → inconsistent clue set;
- one solution → unique;
- two or more → ambiguous.
This makes automated solvers valuable not only for playing but also for puzzle construction and publishing pipelines.
Not every solver uses the same algorithm
Nonograms can be modeled in several computational frameworks.
Implementations may use combinations of:
- custom line solvers;
- dynamic programming;
- constraint programming;
- SAT-style Boolean constraints;
- integer programming;
- depth-first search;
- heuristic search;
- probing and caching.
Research has compared specialized solvers and proposed alternative mathematical formulations. There is no single required architecture.
What defines correctness is that the algorithm respects the clues and cell constraints and, when it claims completeness or uniqueness, searches enough of the solution space to justify that claim.
Fast line logic vs complete line logic
A subtle implementation tradeoff is that a very fast line routine may not derive every forced cell available from one line.
WebPBN explicitly notes that its left/right overlap routine is fast but not complete, so pbnsolve can perform a more exhaustive check after ordinary line solving stalls.
This mirrors a human distinction:
- a cheap visual technique may reveal many cells quickly;
- full valid-pattern analysis can reveal additional forced cells at greater cost.
How a solver can rate difficulty
Once a solver records its own work, it can produce features such as:
- number of line solves;
- number of propagation rounds;
- strongest inference required;
- number of patterns considered;
- number of probes or branches;
- maximum search depth.
Those features can feed a difficulty model, although they still describe difficulty relative to that solver architecture.
Why general solving can still be hard
A specialized solver can make normal puzzle-book Nonograms feel trivial, yet there is no known polynomial-time method that solves all possible Nonogram instances unless major complexity-theory assumptions collapse.
That is a worst-case statement, not a claim that your daily 15×15 puzzle should take a supercomputer.
What to learn next
For the theory behind worst-case hardness, continue to Why Nonograms Are Computationally Hard. For the human-facing analogue of temporary assumptions, revisit Contradiction Reasoning.
FAQ
Do Nonogram solvers simply brute-force every grid?
Good solvers do not need to. They use line constraints and propagation to eliminate enormous numbers of possibilities before search, and many published puzzles solve without deep branching.
Can a solver prove that a puzzle is unique?
Yes, if it performs a complete enough search to rule out every alternative solution.
Are computer and human solving methods the same?
They overlap conceptually, especially around line logic and propagation, but computers can track far more candidate states and can use systematic search that would be tedious for a person.