What Is a Nonogram?
A nonogram (also called a Picross or Griddler) is a logic puzzle played on a rectangular grid. Each row and column carries a list of clue groups: numbers that give the lengths of consecutive filled runs, in order, from left to right or top to bottom. The goal is to determine exactly which cells are filled and which are empty while satisfying every row and column clue.
The classic version is black and white. Colored nonograms add a color to each clue group. Two adjacent groups of the same color must have at least one white cell between them, while groups of different colors may touch.
Problem Framing
A nonogram asks us to assign a value to every cell while satisfying a collection of interacting rules. That makes it a Constraint Satisfaction Problem, or CSP. Other familiar CSPs include Sudoku, N-Queens, and map coloring. Common ways to approach them include backtracking, constraint propagation, and local search.
Where the Puzzles Come From
The app fetches puzzles from nonograms.org by ID. Each page contains an obfuscated JavaScript array representing the published puzzle image. The crawler decodes that grid, derives its row and column clue groups, and passes only those clues and the color palette to the solver.
The source page therefore contains the finished image, but the solver itself does not use it. The decoded image is discarded after clue generation, and the solver reconstructs a result from the derived clues. Custom clue input is not supported by the UI yet, so the current input path targets known-valid puzzles from nonograms.org rather than arbitrary puzzle definitions.
Representing State with Bitmasks
Rather than a simple enum like Filled | Empty | Unknown, every cell holds a u64 bitmask where each bit position represents one possible cell value. Bit 0 is reserved for white, bit 1 is color #1, bit 2 is color #2, and so on.
// A cell that could be white (bit 0) or color-1 (bit 1)
let cell: u64 = 0b0000_0011; // both bits set = still uncertain
// A cell that is definitely color-1
let solved: u64 = 0b0000_0010; // exactly one bit set
// Check if a cell is resolved
fn is_single_bit(mask: u64) -> bool {
mask != 0 && (mask & (mask - 1)) == 0
}
If the palette contains C entries including white, a completely unknown cell starts with (1 << C) - 1: all C bits set. This encodes “I don’t know yet” and enables fast bitwise intersection later:
let color_count = data.color_panel.len();
let full_mask = (1u64 << color_count) - 1;
let mut row_masks = vec![vec![full_mask; n]; m];
Example
For a palette containing white, red, and blue, the initial mask is 0b111. A row pass might reduce it to 0b011, ruling out blue. If a column pass independently produces 0b110, their intersection is 0b010, so the cell must be red.
The Outer Fixed-Point Loop
The top-level solver in nonogram_solver.rs alternates between rows and columns until another pass produces no change:
- Initialize. Give every cell the full uncertainty mask. Store the grid twice: once row-major and once column-major.
- Row pass. Run the line solver on every active row, narrowing each cell to the colors allowed by that row’s clues.
- Column pass. Do the same for every active column.
- Intersect. AND the row and column masks for each cell, then copy the combined value into both mirrors.
- Repeat. Stop when the grid reaches a fixed point.
let mut prev_sum = u64::MAX;
loop {
if !update_groups_state(&mut solver, &mut dead_rows, &row_groups, &mut row_masks) {
return Err(SolveError::Unsolvable);
}
if !update_groups_state(&mut solver, &mut dead_cols, &col_groups, &mut col_masks) {
return Err(SolveError::Unsolvable);
}
let cur_sum = update_cell_values(&mut row_masks, &mut col_masks);
if cur_sum == prev_sum { break; }
prev_sum = cur_sum;
}
The repository currently detects the fixed point using a wrapping sum of all cell masks. Because propagation only removes bits, the ordinary integer sum decreases whenever a possibility disappears. However, a wrapping checksum is not proof that two grids are equal: different totals can collide modulo 2^64. A more robust implementation would have the intersection step return a direct changed flag by comparing every combined mask with its previous value.
Once every cell in a line has a single bit, the solver marks that line as “dead” and skips it in later passes. For valid, consistent puzzles this saves work: a resolved line cannot be narrowed further without producing a contradiction.
The intersection step
The update_cell_values function is the heart of propagation. The bitmask AND combines the knowledge from the row pass and the column pass — only possibilities that satisfy both constraints survive:
fn update_cell_values(row_masks: &mut [Vec<u64>], col_masks: &mut [Vec<u64>]) -> u64 {
let mut total: u64 = 0;
for row in 0..row_masks.len() {
for col in 0..row_masks[row].len() {
let combined = row_masks[row][col] & col_masks[col][row];
row_masks[row][col] = combined;
col_masks[col][row] = combined;
total = total.wrapping_add(combined);
}
}
total
}
Only possibilities accepted by both the row and the column survive. A zero mask means the two sets of constraints contradict one another at that cell and should be treated as an error.
There is one hardening detail still worth adding to the repository. Lines are marked dead before row and column masks are intersected, so arbitrary inconsistent PuzzleData can produce a zero mask after both affected lines have already been retired. Checking combined == 0 during intersection would make contradiction detection reliable for custom inputs too.
The Line Solver: Recursive Placement with Memoization
The per-line logic lives in one_line_solver.rs. Given a sequence of (length, color) groups and the current masks for a row or column, it computes the colors that remain possible at every position. The answer is the union of all valid placements.
Core recursion: CAN_FILL
The recursive function can_fill(groups, cells, cur_group, cur_cell) asks: “Starting at cell index cur_cell, can we successfully place all remaining groups starting from index cur_group?” It explores two choices at each position:
// Option A: place a white cell here, then recurse
if Self::can_place_color(cells, 0, cur_cell, cur_cell)
&& self.can_fill(groups, cells, cur_group, cur_cell + 1)
{
self.set_place_color(0, cur_cell, cur_cell);
answer = true;
}
// Option B: place the next group starting here
if can_place && self.can_fill(groups, cells, cur_group + 1, next_cell) {
answer = true;
self.set_place_color(cur_color, l_bound, r_bound);
if place_white { self.set_place_color(0, r_bound + 1, r_bound + 1); }
}
The result accumulates into result_cell via bitwise OR in set_place_color: a cell gets a color bit set if any valid filling uses that color there. This is the union-of-valid-placements principle: it removes a possibility only when no valid placement uses it.
Same-Color Separation Rule
When two consecutive groups share the same color, a mandatory white separator cell is inserted between them. This is handled by checking groups[cur_group + 1].1 == cur_color and requiring an additional can_place_color(..., 0, ...) check before advancing next_cell by one extra position.
Memoization with a counter trick
Naive recursion over all placements would revisit the same suffix many times. The solver memoizes subproblems using a 2D table, cache[cur_group][cur_cell]. Clearing the whole table on every call would be unnecessary work, so it uses a monotonic generation counter instead:
// Check cache — only valid if the counter matches
if self.cache[cur_group][cur_cell] == self.cache_cnt {
return self.calc_fill[cur_group][cur_cell];
}
// ... compute result ...
self.calc_fill[cur_group][cur_cell] = answer;
self.cache[cur_group][cur_cell] = self.cache_cnt; // "stamp" this entry
At the start of each call to update_state, cache_cnt is incremented. Any cache entry stamped with an older counter value is automatically stale, without zeroing the array. On the rare counter overflow, the array is explicitly cleared and the counter restarts at 1. This is a classic generation-counter cache invalidation pattern.
Placing and checking colors
The two helper functions are deliberately minimal. can_place_color checks that every cell in the range [l_bound, r_bound] has the target color’s bit still set, meaning the current state allows that color there. set_place_color ORs the color bit into result_cell for each cell in that range, recording the possibility. These range scans matter when discussing the implementation’s runtime.
fn can_place_color(cells: &[u64], color: usize, l: usize, r: usize) -> bool {
let mask = 1u64 << color;
(l..=r).all(|i| cells[i] & mask != 0)
}
Putting It All Together
Here’s how the two layers collaborate during a single outer-loop iteration for one row. Take a 5-cell row with clue [(3, black)]. Initially, each cell is fully uncertain (BW: could be black or white).
All three valid placements of a run of 3 on a 5-cell row:
0 1 2 3 4
Placement A B B B W W
Placement B W B B B W
Placement C W W B B B
Union ? ? B ? ?
The ringed cell is filled in every valid placement, so its white bit is dropped.
B means black, W means white, and ? means still uncertain.
Only cell 2 is black in every valid placement, so only that cell loses its white bit. Cells 0, 1, 3, and 4 remain uncertain because each is black in some placements and white in others. This is the classic overlap technique expressed as a union-of-valid-placements bitmask computation.
The outer loop then intersects this row result with column constraints using bitwise AND. If a column pass has independently forced cell 0 to black, that intersection resolves it. If not, it stays uncertain until a future pass. The solver stops when this particular propagation operation reaches a fixed point.
Complexity and Memory
Let N be the line length, G the number of clue groups, and Lmax the longest group.
Memoization ensures that the recursion computes at most \(\mathcal{O}(GN)\) distinct (cur_group, cur_cell) states per call to update_state. The current implementation does not have constant-time transitions, though: checking or recording a group placement can scan up to Lmax cells. A safe upper bound for the implemented line solver is therefore \(\mathcal{O}(G N L_{max})\), rather than simply \(\mathcal{O}(GN)\). Prefix tables or range-difference updates could reduce those range operations if this became a bottleneck.
The cache is allocated as two square tables with side length max(N, G) + 1, so its allocated space is \(\mathcal{O}(\max(N,G)^2)\). The logical dynamic-programming state space is still \(\mathcal{O}(GN)\).
Across the whole puzzle, every productive outer iteration removes at least one candidate bit. If the grid has M × N cells and C palette entries, there are at most MN(C - 1) candidate eliminations before reaching a fixed point. This gives a conservative iteration bound of \(\mathcal{O}(MNC)\), although well-constrained puzzles usually settle in far fewer passes.
The mirrored grids store 2MN masks. For a 100×100 puzzle, that is 20,000 u64 values, or about 156 KiB before Vec overhead. The step-by-step visualizer also retains row-major snapshots: each snapshot adds about 78 KiB for a 100×100 puzzle. Total memory therefore depends on both puzzle size and the number of recorded iterations.
What the Solver Can and Cannot Prove
This solver implements line-by-line constraint propagation, not search. It can reach three practically distinct states:
- A complete fixed point, where every cell has exactly one remaining value.
- A partial fixed point, where some cells still have multiple possible values.
- A contradiction discovered while solving a line.
The current API does not explicitly distinguish the first two. solve_puzzle returns the last fixed point in a type called SolvedPuzzle, even when unresolved masks remain. A future API could make this clearer with a Solved | Partial status.
Unique solvability alone does not guarantee that line propagation will finish a puzzle. A uniquely solvable puzzle can still require deductions that combine information across multiple lines. In the terminology of Batenburg and Kosters, a puzzle solved completely by repeatedly applying the single-line Settle operation is called simple. Those simple puzzles are the natural target for this implementation.
Limitation
When unresolved cells remain at the fixed point, this solver returns the partial grid. Completing every uniquely solvable puzzle would require stronger reasoning or a search layer.
Wrapping Up
This project started as an Advanced Algorithms course project and case study in my final year of university. I chose nonograms because I was genuinely addicted to them at the time, and the project gave me an excuse to spend more time on them than I could otherwise justify.
The original version was written in Python and Processing. I recently rebuilt it in Rust and Dioxus, adding live puzzle fetching and a step-by-step visualizer. The current implementation is deliberately narrower than a complete nonogram engine: it focuses on the interaction between bitmask domains, a memoized line solver, and fixed-point propagation.
The approach is inspired by Batenburg and Kosters’ paper, Solving Nonograms by Combining Relaxations.1 The paper defines a single-line Settle operation that fixes every pixel having the same value in all valid completions of a line. Repeating that operation across rows and columns until nothing else changes is called FullSettle. That is the closest description of the solver implemented here, extended from the paper’s primarily black-and-white presentation to colored clues.
The paper then adds stronger deterministic reasoning: a Discrete Tomography relaxation, clauses harvested from the relaxations and combined through 2-SAT in Solver0, and a single-pixel contradiction probe in Solver1. None of those layers are implemented here. Reaching a FullSettle fixed point means only that repeated single-line reasoning is exhausted, not that every deterministic form of inference is exhausted.
Explore the source code on GitHub, or try the live demo. The demo runs on Render’s free tier, so it may take a moment to start.