🧩 Constraint Solving POTD:Problem of the Day: Nonogram (Picross)

[github-actions[bot]]

Problem Statement

A nonogram (also called Picross) is a binary-grid puzzle. Each row and column has a clue such as 2,1: fill two consecutive cells, leave at least one blank, then fill one more cell. The order of the runs is fixed, but their positions are unknown.

A 5×5 instance

Row clues, top to bottom:

[1,1]  [2]  [3]  [1,1]  [2,1]

Column clues, left to right:

[1,1]  [2,1]  [1,1]  [1,1]  [1,1]

One valid output is:

#..#.
.##..
..###
.#.#.
##..#

For example, the final row is ##..#, which has runs 2,1; the second column is .##.#, which has runs 2,1. In general, the input is a grid size plus one run-length list per row and column. The output is a grid of filled (#) and empty (.) cells satisfying every clue; a solver may also report that no such grid exists.

Why It Matters

Nonograms are a compact laboratory for global constraint propagation: a local decision in one line immediately changes the possible patterns in perpendicular lines. The same interaction appears in pixel reconstruction, fault diagnosis, bitmap recovery, and inference from partial observations.

Puzzle and game developers use these models to generate and verify instances, while AI and operations-research practitioners use them as approachable benchmarks for constraint programming, SAT, and hybrid search. The problem is also useful for teaching why a strong global constraint can outperform many individually simple constraints.

Modeling Approaches

1. Constraint programming with line automata or tables

Let x[r,c] ∈ {0,1} indicate whether cell (r,c) is filled. For each row, constrain its Boolean sequence to the regular language

0* 1^a1 0+ 1^a2 0+ ... 0+ 1^ak 0*

where a1,...,ak is that row's clue. Apply the analogous constraint to every column. A practical alternative precomputes every legal length-W bit pattern for a row clue and posts a table constraint over that line.

This model is concise and usually propagates well: a regular or table constraint can remove whole line patterns after only one cell is fixed. It also handles arbitrary clue lengths naturally. The cost is solver-dependent global-constraint machinery and potentially many candidate tuples for wide lines.

2. SAT with candidate-pattern variables

Enumerate the legal patterns P_r for each row and P_c for each column. Introduce Boolean variables R[r,p] and C[c,p], selecting exactly one pattern for each line. Link them to the cell variables with equivalences such as

x[r,c] ↔ OR { R[r,p] : p[c] = 1 }
x[r,c] ↔ OR { C[c,p] : p[r] = 1 }

Encode the exact-one constraints and equivalences into CNF, using a cardinality encoding when a line has many candidates. Modern CDCL SAT solvers provide clause learning and restarts, which can be excellent on large, tightly constrained puzzles. However, candidate enumeration grows with line width, and a weak cardinality encoding can produce more clauses than the CP model needs.

Example Model (pseudo-code)

model Nonogram:
  x[1..H, 1..W] in 0..1

  for r in 1..H:
    patterns = legal_patterns(W, row_clue[r])
    table([x[r,c] | c in 1..W], patterns)

  for c in 1..W:
    patterns = legal_patterns(H, col_clue[c])
    table([x[r,c] | r in 1..H], patterns)

  solve satisfy with first_fail(x)

Here legal_patterns inserts at least one zero between consecutive runs. The table constraints may be replaced by regular constraints when the solver supports them.

Key Techniques

Candidate intersection and bounds consistency

For a line of length L, the minimum occupied span is sum(clue) + number_of_runs - 1. Enumerate only placements that fit, then intersect all surviving patterns: cells filled in every pattern are forced to 1, and cells empty in every pattern are forced to 0. Alternating this process over rows and columns is a lightweight form of arc consistency.

First-fail search on line patterns

When propagation stalls, branch on the row or column with the fewest remaining patterns, not necessarily on the first unknown cell. Trying the most-constraining pattern first often causes a quick contradiction in a perpendicular line. Restarts and learned nogoods are natural additions in SAT or CP-SAT implementations.

Safe symmetry breaking

If the clue set is invariant under a reflection or transpose, solutions may occur in symmetric pairs. A lexicographic ordering between a grid and its reflected image can remove duplicate search branches—but only after checking that the symmetry preserves both row and column clues. For non-symmetric clues, ordinary propagation is safer than imposing an invalid canonical order.

Challenge Corner

Can you replace one candidate variable for every legal line pattern with a smaller encoding based only on run start positions, while preserving strong propagation? As an extension, how would you model a noisy nonogram in which a few clues may be wrong—hard constraints with an edit budget, or a weighted MaxSAT/optimization objective minimizing corrections?

References

• K. R. Apt, Principles of Constraint Programming, Cambridge University Press, 2003.
• F. Rossi, P. van Beek, and T. Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006.
• MiniZinc Handbook, sections on the table and regular global constraints: (docs.minizinc.dev/redacted).
• Google OR-Tools, CP-SAT documentation on Boolean, table, and cardinality constraints: (developers.google.com/redacted).

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: gpt56 max · ~3 AIC · ⌖ ~1 AIC · ⊞ 3.1K · ◷

• expires on Nov 10, 2026, 1:52 PM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #74835.