Problem Breakdown
Nonogram Solver
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
You're given a grid with r rows and c columns. For each row and each column you get a clue, which is a list of integers describing the run lengths of consecutive filled cells on that line, in order. A clue like [3, 1] means "a block of three filled cells, at least one empty cell, then a block of one filled cell." The special clue [0] means the line is entirely empty.
Here's a 5x5 whose solution spells out a heart. The left panel is what you receive, showing empty cells with the clues on each axis, while the right panel shows the solved grid.
Row clues run along the left of each grid, column clues along the top. Every filled run in the solution matches its clue from left to right for rows and top to bottom for columns. If no valid filling exists, the solver returns null.
The test suite runs four sizes, starting at 5x5, then 10x10, then 15x15, and finishing with a single 25x25. Each timed test has its own budget, and the wrinkle is that an approach that passes 10x10 can blow the budget on 15x15 by orders of magnitude.
Pattern: Backtracking
You fill the grid by guessing a row, recursing to the next, and backing out when the clues stop lining up. Propagating the forced cells first just trims the search before backtracking takes over.
Solution 1, cell-by-cell backtracking
The most direct way to attack this is backtracking. Walk the cells left-to-right across each row, top row first, then the next row, and so on. At each cell, try FILLED, recurse into the next cell, and if that sub-search fails, try EMPTY instead. When the recursion reaches the bottom-right corner, check whether every row's and every column's runs agree with their clues. If yes, you're done. If no, unwind.
To prune early, you can check a row's runs as soon as you fill its last cell and check a column's runs only on the bottom row, since a column isn't complete until then. A row whose runs already disagree with its clue can't lead to a valid grid no matter what happens below, so you skip the rest of that branch.
The diagram shows a mid-recursion state on the 5x5 heart puzzle. Rows 0 and 1 are fully placed and both pass the row-clue check. Row 2 is in progress and the recursion is at cell (2, 1) with FILLED pending. Rows 3 and 4 haven't been touched yet.
public Nonogram solve() {
Nonogram puzzle = this.puzzle.clone();
return cellBacktrack(puzzle, 0) ? puzzle : null;
}
private boolean cellBacktrack(Nonogram p, int idx) {
if (idx == p.getRows() * p.getCols()) return p.isSolved();
int r = idx / p.getCols(), c = idx % p.getCols();
for (Nonogram.CellState state : new Nonogram.CellState[] { Nonogram.CellState.FILLED, Nonogram.CellState.EMPTY }) {
p.setCell(r, c, state);
boolean valid = true;
if (c == p.getCols() - 1) {
if (!p.extractRuns(p.getRow(r)).equals(p.getRowClues(r))) valid = false;
}
if (valid && r == p.getRows() - 1) {
if (!p.extractRuns(p.getCol(c)).equals(p.getColClues(c))) valid = false;
}
if (valid && cellBacktrack(p, idx + 1)) return true;
}
p.setCell(r, c, Nonogram.CellState.UNKNOWN);
return false;
}
The clone at the top keeps the caller's grid intact; the solver works on a copy so a failed search doesn't leave the original grid in a half-filled state. The end-of-line check validates a row only when the last cell of that row was just set, and validates a column only when the last cell of that column was just set, which is the bottom row, because checking mid-line would be wasted work since a partial line's runs don't have to match the clue yet. Finally, the reset on unwind restores a cell to UNKNOWN after both FILLED and EMPTY fail for it; skip this and stale values in the grid will break sibling branches of the search.
Complexity
Time is in the worst case. Every cell has two choices, and there are r · c cells, so the tree has up to leaves. The line-check pruning helps a lot in practice but doesn't change the worst-case bound. Space is O(r · c) for the grid plus O(r · c) for the recursion stack.
The numbers escalate quickly. On a 5x5 grid the search tree is bounded by 2²⁵, roughly 33 million leaves. On a 10x10 it's 2¹⁰⁰, which is 10³⁰. Pruning cuts a huge slice off that tree, but it can't turn 10³⁰ into anything that finishes.
Where it breaks
This solution cleans up the 5x5 puzzles in about 1.5ms total across all three. A single 10x10 medium puzzle runs past 300000ms (five minutes) of wall time without returning. The test budget is 5000ms, so the solver overshoots it by orders of magnitude. Cell-by-cell backtracking ignores the clues entirely. Consider a row of length 10 with clue [8]. There are only three valid fills (runs starting at columns 0, 1, or 2), and all three put FILLED in columns 2 through 7, meaning six of ten cells are forced before you guess anything. Cell-by-cell doesn't see this. It tries FILLED at column 0, FILLED at column 1, then EMPTY at column 2, and only discovers the row-clue violation after recursing all the way to the last cell of the row. Every rejection costs an entire sub-tree of wasted work.
Solution 2, row-by-row backtracking
The fix is to stop choosing cells and start choosing whole rows. Every row has a clue, and every clue admits a finite number of valid fills. If you enumerate those up front, you never place a row that violates its own clue. The search tree is then much shallower, with one branch per row instead of one branch per cell.
The helper that does this work is a line-possibility generator. Given a clue and a line length, it returns every way the runs can be laid out. For clue [2, 1] with length 5, there are three valid placements.
![Clue [2, 1] on length 5 with three valid fills stacked vertically](/content-assets/90bc7d1d4b64ab31a17dc8bdca3902db4d8a12dd2d8d07e4aef8caa9bdceea26.svg)
The diagram shows all three. The minimum length for clue [2, 1] is 2 + 1 + 1 = 4, where the + 1 accounts for the mandatory gap between runs. In general, for a clue with runs [r1, r2, ..., rk], the minimum line length is sum(runs) + k - 1, where the k - 1 term counts the one mandatory gap between each consecutive pair of runs. The line has 5 cells, so there's one cell of slack, which is why there are three placements and not one or ten.
The solver runs this helper once per row to get a list of per-row candidate fills. Then it backtracks over rows. For each row, it tries each candidate fill, places it into the grid, and checks the columns for consistency. If every column's runs so far are compatible with that column's clue, it recurses into the next row. If a column has already gone off track, it skips this row fill and tries the next.
private static List<List<Nonogram.CellState>> generateLinePossibilities(List<Integer> clues, int length) {
List<List<Nonogram.CellState>> results = new ArrayList<>();
if (clues.size() == 1 && clues.get(0) == 0) {
List<Nonogram.CellState> line = new ArrayList<>();
for (int i = 0; i < length; i++) line.add(Nonogram.CellState.EMPTY);
results.add(line);
return results;
}
int nRuns = clues.size();
int sum = 0;
for (int x : clues) sum += x;
if (sum + nRuns - 1 > length) return results;
placeRuns(results, clues, length, 0, 0, new ArrayList<>());
return results;
}
private static void placeRuns(List<List<Nonogram.CellState>> results, List<Integer> clues, int length,
int runIdx, int pos, List<Nonogram.CellState> line) {
int nRuns = clues.size();
if (runIdx == nRuns) {
List<Nonogram.CellState> out = new ArrayList<>(line);
while (out.size() < length) out.add(Nonogram.CellState.EMPTY);
results.add(out);
return;
}
int remain = 0;
for (int k = runIdx; k < nRuns; k++) remain += clues.get(k);
int latest = length - (remain + (nRuns - runIdx - 1));
for (int start = pos; start <= latest; start++) {
List<Nonogram.CellState> next = new ArrayList<>(line);
for (int k = 0; k < start - pos; k++) next.add(Nonogram.CellState.EMPTY);
for (int k = 0; k < clues.get(runIdx); k++) next.add(Nonogram.CellState.FILLED);
if (runIdx < nRuns - 1) next.add(Nonogram.CellState.EMPTY);
placeRuns(results, clues, length, runIdx + 1, next.size(), next);
}
}
public Nonogram solve() {
Nonogram puzzle = this.puzzle.clone();
List<List<List<Nonogram.CellState>>> rowPoss = new ArrayList<>();
for (int r = 0; r < puzzle.getRows(); r++) {
rowPoss.add(generateLinePossibilities(puzzle.getRowClues(r), puzzle.getCols()));
}
return rowBacktrack(puzzle, rowPoss, 0) ? puzzle : null;
}
private boolean columnConsistent(Nonogram p, int colIdx, int filledRows) {
List<Integer> clues = p.getColClues(colIdx);
List<Integer> runs = new ArrayList<>();
int length = 0;
boolean trailing = false;
for (int r = 0; r < filledRows; r++) {
Nonogram.CellState cell = p.getCell(r, colIdx);
if (cell == Nonogram.CellState.FILLED) { length++; trailing = true; }
else if (cell == Nonogram.CellState.EMPTY) {
if (length > 0) { runs.add(length); length = 0; }
trailing = false;
}
}
if (trailing && length > 0) {
if (runs.size() >= clues.size()) return false;
if (length > clues.get(runs.size())) return false;
} else if (!trailing && length > 0) runs.add(length);
for (int i = 0; i < runs.size(); i++) {
if (i >= clues.size() || !runs.get(i).equals(clues.get(i))) return false;
}
if (filledRows == p.getRows()) {
if (!p.extractRuns(p.getCol(colIdx)).equals(clues)) return false;
}
return true;
}
private boolean rowBacktrack(Nonogram p, List<List<List<Nonogram.CellState>>> rowPoss, int rowIdx) {
if (rowIdx == p.getRows()) return p.isSolved();
for (List<Nonogram.CellState> poss : rowPoss.get(rowIdx)) {
for (int c = 0; c < p.getCols(); c++) p.setCell(rowIdx, c, poss.get(c));
boolean ok = true;
for (int c = 0; c < p.getCols(); c++) {
if (!columnConsistent(p, c, rowIdx + 1)) { ok = false; break; }
}
if (ok && rowBacktrack(p, rowPoss, rowIdx + 1)) return true;
}
for (int c = 0; c < p.getCols(); c++) p.setCell(rowIdx, c, Nonogram.CellState.UNKNOWN);
return false;
}
The possibility generator walks runs left to right, placing the first run at the earliest position it can take (starting at column 0), then the next run at the earliest position after a mandatory gap, and so on until all runs are placed and the tail is padded with EMPTY. latest is the rightmost column index placed so far within the current recursive frame, used to enforce that each subsequent run starts after the last finished run plus its mandatory gap. That guarantee keeps the tree from exploring layouts that were doomed from the start. On top of that, the column consistency check has to be partial because a column isn't done until every row is placed. A FILLED tail means the column is still inside a run, so the last run in the clue could still be growing; an EMPTY tail means no run is currently open, so every run in the partial column must have already been placed and closed, and the prefix of completed runs must match the clue exactly (getting that trailing-run case wrong is the usual bug here). The row reset on unwind matters for the same reason it did with cell backtracking. When all candidate fills for a row fail, the solver resets that row's cells back to UNKNOWN, and skipping this leaves the last attempted fill in place, so when the parent row unwinds after one of our row's successes, the caller sees whatever was left behind.
Complexity
If a row has P valid fills on average and there are r rows, the search tree has up to Pʳ leaves. The cost per leaf is O(r · c) for the column scan. That's much better than when P is small, and it holds up well on 10x10 grids where most rows have a handful to a few dozen possible fills.
Where it breaks
For 10x10, row backtracking finishes the medium puzzles in under 10ms total. For 15x15 it's a different story. A 15-cell row with a middling clue can have thousands of valid fills, and P¹⁵ with P in the thousands is astronomical even before pruning. On the large dataset, the first 15x15 puzzle solves in about 9000ms and the second takes 59000ms, both way past the 5000ms budget.
Row backtracking only uses column clues to reject bad branches, never to choose them. Columns carry just as much information as rows, and we're ignoring half of it until the placement is in.
Solution 3, propagation with search as a fallback
Enumerate possibilities for both rows and columns. Filter each line's list of possibilities against the cells that are already known. If every remaining possibility agrees on the value of a specific cell, that cell is forced to that value regardless of which fill is eventually chosen.
When every valid fill of a line agrees on the same value for a particular cell, that cell is forced regardless of which fill is eventually chosen; this is called the overlap argument because it identifies the cells where all candidate fills "overlap" on the same value. Take a single line of length 5 with clue [4], where only two fills satisfy the clue.
![Two valid fills for clue [4] on length 5, with the three overlap cells highlighted as forced](/content-assets/cf22c6e71255703b48ad3e83eab5ca5183161c38d08b7680a920bdba0d15f979.svg)
Both fills put FILLED in columns 1, 2, and 3. Columns 0 and 4 disagree between the two fills, so neither is forced. We can mark columns 1, 2, and 3 as FILLED immediately and keep going.
For every row and every column, filter the candidate fills against the known cells, look for cells where all remaining candidates agree, and commit those cells. Fixing a cell in row r changes what's valid for the column crossing r, which may force more cells, which in turn constrain more rows. Keep looping until a pass over the grid produces no new forced cells. Each pass either fixes at least one new cell or changes nothing, and the grid has finitely many cells, so the loop terminates after at most rows * cols passes that actually fix something.
After propagation finishes, one of two things has happened. In the happy case, every cell is known and the puzzle is solved with no search needed at all. More often, propagation runs out of forced moves while some cells are still UNKNOWN. At that point the puzzle is locally ambiguous, and pure deduction can't determine those remaining cells without trying a guess.
That's where backtracking comes back, but in a much smaller role than in solutions 1 and 2. Pick any unknown cell and tentatively guess that it's FILLED. Clone the current state (both the grid and each line's candidate-fill list) so you can roll back if the guess is wrong, set that cell to FILLED in the clone, and run propagation again. If propagation now derives a contradiction, meaning some row or column has zero valid fills left, the guess was wrong. Back out to the pre-guess state, try EMPTY for the same cell, and propagate again. If EMPTY also contradicts, the path above this guess is doomed and you unwind to the next level up.
Propagation does most of the checking for you. A single wrong guess usually cascades into a contradiction within a pass or two, so each failed branch dies quickly. The search tree stays shallow even on the 25x25 puzzle because every node in the tree has a full propagation pass bolted to it, and the propagation pass rejects bad branches long before they'd need to expand any further.
private static List<List<Nonogram.CellState>> generateLinePossibilities(List<Integer> clues, int length) {
List<List<Nonogram.CellState>> results = new ArrayList<>();
if (clues.size() == 1 && clues.get(0) == 0) {
List<Nonogram.CellState> line = new ArrayList<>();
for (int i = 0; i < length; i++) line.add(Nonogram.CellState.EMPTY);
results.add(line);
return results;
}
int nRuns = clues.size();
int sum = 0;
for (int x : clues) sum += x;
if (sum + nRuns - 1 > length) return results;
placeRuns(results, clues, length, 0, 0, new ArrayList<>());
return results;
}
private static void placeRuns(List<List<Nonogram.CellState>> results, List<Integer> clues, int length,
int runIdx, int pos, List<Nonogram.CellState> line) {
int nRuns = clues.size();
if (runIdx == nRuns) {
List<Nonogram.CellState> out = new ArrayList<>(line);
while (out.size() < length) out.add(Nonogram.CellState.EMPTY);
results.add(out);
return;
}
int remain = 0;
for (int k = runIdx; k < nRuns; k++) remain += clues.get(k);
int latest = length - (remain + (nRuns - runIdx - 1));
for (int start = pos; start <= latest; start++) {
List<Nonogram.CellState> next = new ArrayList<>(line);
for (int k = 0; k < start - pos; k++) next.add(Nonogram.CellState.EMPTY);
for (int k = 0; k < clues.get(runIdx); k++) next.add(Nonogram.CellState.FILLED);
if (runIdx < nRuns - 1) next.add(Nonogram.CellState.EMPTY);
placeRuns(results, clues, length, runIdx + 1, next.size(), next);
}
}
private static List<List<Nonogram.CellState>> filterAgainst(List<List<Nonogram.CellState>> possibilities, List<Nonogram.CellState> line) {
List<List<Nonogram.CellState>> out = new ArrayList<>();
for (List<Nonogram.CellState> poss : possibilities) {
boolean ok = true;
for (int i = 0; i < line.size(); i++) {
if (line.get(i) != Nonogram.CellState.UNKNOWN && line.get(i) != poss.get(i)) { ok = false; break; }
}
if (ok) out.add(poss);
}
return out;
}
private boolean propagate(Nonogram p, List<List<List<Nonogram.CellState>>> rowPoss, List<List<List<Nonogram.CellState>>> colPoss) {
boolean changed = true;
while (changed) {
changed = false;
for (int r = 0; r < p.getRows(); r++) {
List<Nonogram.CellState> row = p.getRow(r);
List<List<Nonogram.CellState>> filtered = filterAgainst(rowPoss.get(r), row);
rowPoss.set(r, filtered);
if (filtered.isEmpty()) return false;
for (int c = 0; c < p.getCols(); c++) {
if (row.get(c) != Nonogram.CellState.UNKNOWN) continue;
Nonogram.CellState v = filtered.get(0).get(c);
boolean same = true;
for (List<Nonogram.CellState> poss : filtered) if (poss.get(c) != v) { same = false; break; }
if (same) { p.setCell(r, c, v); changed = true; }
}
}
for (int c = 0; c < p.getCols(); c++) {
List<Nonogram.CellState> col = p.getCol(c);
List<List<Nonogram.CellState>> filtered = filterAgainst(colPoss.get(c), col);
colPoss.set(c, filtered);
if (filtered.isEmpty()) return false;
for (int r = 0; r < p.getRows(); r++) {
if (col.get(r) != Nonogram.CellState.UNKNOWN) continue;
Nonogram.CellState v = filtered.get(0).get(r);
boolean same = true;
for (List<Nonogram.CellState> poss : filtered) if (poss.get(r) != v) { same = false; break; }
if (same) { p.setCell(r, c, v); changed = true; }
}
}
}
return true;
}
private Nonogram search(Nonogram p, List<List<List<Nonogram.CellState>>> rowPoss, List<List<List<Nonogram.CellState>>> colPoss) {
if (!propagate(p, rowPoss, colPoss)) return null;
if (!p.hasUnknownCells()) return p.isSolved() ? p : null;
for (int r = 0; r < p.getRows(); r++) {
for (int c = 0; c < p.getCols(); c++) {
if (p.getCell(r, c) == Nonogram.CellState.UNKNOWN) {
for (Nonogram.CellState state : new Nonogram.CellState[] { Nonogram.CellState.FILLED, Nonogram.CellState.EMPTY }) {
Nonogram np = p.clone();
List<List<List<Nonogram.CellState>>> nrp = new ArrayList<>();
for (List<List<Nonogram.CellState>> x : rowPoss) nrp.add(new ArrayList<>(x));
List<List<List<Nonogram.CellState>>> ncp = new ArrayList<>();
for (List<List<Nonogram.CellState>> x : colPoss) ncp.add(new ArrayList<>(x));
np.setCell(r, c, state);
Nonogram res = search(np, nrp, ncp);
if (res != null) return res;
}
return null;
}
}
}
return null;
}
public Nonogram solve() {
Nonogram puzzle = this.puzzle.clone();
List<List<List<Nonogram.CellState>>> rowPoss = new ArrayList<>();
for (int r = 0; r < puzzle.getRows(); r++) {
rowPoss.add(generateLinePossibilities(puzzle.getRowClues(r), puzzle.getCols()));
}
List<List<List<Nonogram.CellState>>> colPoss = new ArrayList<>();
for (int c = 0; c < puzzle.getCols(); c++) {
colPoss.add(generateLinePossibilities(puzzle.getColClues(c), puzzle.getRows()));
}
return search(puzzle, rowPoss, colPoss);
}
The filter pass trims the existing possibility list for each line instead of regenerating from scratch, because the generator is only called once at the start of the solve. Filtering is cheap because it walks the existing list and keeps the entries that still match the known cells, whereas regenerating would re-enumerate all line possibilities (up to in the worst case), while filtering only walks the existing list (at most the current candidate count), doing orders of magnitude less work per pass. Alongside that, the contradiction check is what lets the fallback search terminate quickly. If any line's filtered list ever becomes empty, there's no way to fill that line consistent with the known cells, so the propagation function returns false immediately and the caller treats that like a failed guess. The clone step before a guess also has to copy both the grid and the per-row and per-column possibility lists, because cloning only the grid leaves both branches sharing the same list objects, and filtering on one branch corrupts the other, which is the single most common bug when writing this solver.
Why this is so much faster than row backtracking
The crucial shift is that propagation does arithmetic, not search. Each propagation pass is roughly linear in the sum of remaining candidates across all lines, since each candidate is tested once per cell of its line, and each pass either makes progress or the loop exits. A well-designed puzzle, which is what most of these tests are, is mostly solvable by propagation alone. The backtracking fallback only kicks in for the cells that have no logical determination, and because propagation runs after every guess, wrong guesses die fast.
Where it lands
On the 15x15 large puzzles, propagation resolves most of the grid logically, a handful of guesses close the remainder, and both puzzles finish in about 16ms total. On the 25x25 huge puzzle, propagation gets most of the way there on its own and a few guesses with re-propagation finishes it in about 187ms. Every test in the suite clears its budget with plenty of headroom.
If you cloned only the grid and forgot the possibility lists, your solver will still return correct answers on the small and medium puzzles because the shared-state bug rarely bites at those sizes. It shows up as intermittent infinite loops or wrong answers on 15x15 and 25x25, because propagation starts mutating lists that a parent call is still counting on.
Benchmarks
Python wall time, total across all puzzles in each dataset. N/A means the solver exceeded the 5000ms budget without returning.
| Dataset | Puzzles | Grid | cell_bt | row_bt | propagate_bt |
|---|---|---|---|---|---|
| small | 3 | 5x5 | 1.5ms | 0.2ms | 0.2ms |
| medium | 3 | 10x10 | N/A | 9.4ms | 1.9ms |
| large | 2 | 15x15 | N/A | 68000ms | 16ms |
| huge | 1 | 25x25 | N/A | N/A | 187ms |
propagate_bt is the only solver that clears every budget, and it does so by more than an order of magnitude on the large and huge datasets.
Takeaways
The ladder here is a compact version of the same move that shows up in a lot of constraint-satisfaction work. Start with raw backtracking. Then change the unit of work so each step uses more of the problem's structure. Then change the approach from "search with pruning" to "deduce first, search only when deduction stops."
Propagation works because it's the same thing humans do when they solve a nonogram on paper. Looking at a clue of [8] on a 10-wide line and marking the middle six cells as definitely filled, without enumerating anything, is exactly the overlap argument. Mechanizing that habit is what turns an NP-complete problem into something a computer finishes in milliseconds.
The next time you run into a problem shaped like this, there are three things to ask before you write any search code. You want to know whether the inputs carry constraints from more than one axis, whether you can enumerate valid options per line cheaply, and whether fixing one line meaningfully constrains another. If the answer to all three is yes, reach for propagation before you reach for clever pruning.