Constraint Propagation and Cascades

Constraint propagation is the repeated process of applying newly confirmed cell states to their crossing lines, finding any consequences there, and continuing until no immediate deduction remains.

A cascade is the visible chain of deductions produced by that process.

A five-by-five cascade example

Consider a 5×5 monochrome Nonogram with these clues:

Rows: 1, 3, 5, 3, 1

Columns: 1, 3, 5, 3, 1

Row 3 is an exact fit because clue 5 fills the whole row. Mark all five cells filled.

Now propagate:

1. columns 1 and 5 each have clue 1, already satisfied by the filled center cell, so every other cell in those columns is empty;
2. column 3 has clue 5, so it fills completely;
3. rows 1 and 5 now have their single required filled cell at column 3, so their other cells become empty;
4. columns 2 and 4, each with clue 3, are now forced to fill rows 2–4;
5. rows 2 and 4 become complete blocks of three.

One initial exact-fit line solves the entire grid through propagation.

Propagation is not a separate source of truth

Every individual step still uses ordinary valid deductions: exact fit, completed blocks, overlap, gap elimination, pattern filtering, and so on.

Propagation describes how those deductions are scheduled and chained across the shared grid.

Why cascades feel faster than rescanning

After a cell changes, only its row and column gain new information directly.

So rather than scanning the whole puzzle from the top every time, follow the affected lines. If they change another cell, follow that cell's crossing line next.

This concentrates attention where the constraint system has actually changed.

Propagate both kinds of certainty

A cascade can be driven by fills or X marks.

For example:

• a filled cell may anchor a block;
• an X may split a segment;
• that segment split may assign a clue;
• the assignment may create an exact fit;
• the exact fit may complete a crossing block;
• its separator may eliminate another gap.

There is no hierarchy where filled cells are “real progress” and empty cells are secondary. Both reduce the set of legal patterns.

Stop only at a stable state

A propagation pass is complete when every line affected by new cells has been reconsidered and no further certain state follows.

Computer solvers often call this a fixed point: repeating the same line deductions would no longer change the grid.

At that point, choose a new promising unresolved line or, on genuinely hard puzzles, consider stronger reasoning.

A cascade can start without an exact-fit line

The diamond example begins with an obvious full line. More interesting cascades start from a weaker consensus deduction.

Consider this 5×5 puzzle:

Rows: 2 1, 1 1, 2, 2, 1 1

Columns: 1 2, 1 2, 2, 1, 2

No row or column is an exact fit at the start. Yet row 1 with clue 2 1 has only one cell that is filled in every valid opening pattern: cell 2.

Mark R1C2 filled and propagate only consensus states. The new information restricts column 2; that column creates new states in rows 2 and 4; those rows constrain more columns; the process continues until every cell is fixed.

The unique solution is:

■■××■

××■×■

×■■××

■■×××

■××■×

This example shows why propagation is more than “solve all the easy rows first.” A modest one-line deduction can become decisive because the grid repeatedly amplifies it through perpendicular constraints.

Use a changed-line queue instead of rescanning everything

A precise way to think about manual propagation is a queue:

1. when a cell changes, add its row and column to the queue;
2. take one changed line and solve it against the current states;
3. if that line changes cells, enqueue their perpendicular lines;
4. remove the processed line;
5. continue until the queue is empty.

A line may return to the queue several times as new crossing information arrives. That is normal.

Computer solvers often use the same scheduling idea because an unchanged line has received no new information and therefore does not need immediate reconsideration.

A fixed point is relative to the strength of your line solver

There is an important advanced nuance.

If your line analysis only checks simple overlap, you may reach a state where simple overlap produces nothing. That does not mean the puzzle has reached a true logical fixed point.

A stronger line solver that considers every valid pattern may still find new cells, and those cells can restart propagation.

So when you say “propagation is exhausted,” be clear about the deduction engine you are propagating:

• basic overlap fixed point;
• full valid-line-pattern fixed point;
• or a stronger multi-line/global fixed point.

This explains why a puzzle can feel stuck even though no guessing is actually necessary.

Propagation and valid line patterns

Pattern reasoning gives a clean formal view.

Each row and column has a set of valid patterns. When one cell becomes filled or empty:

1. incompatible patterns disappear from the crossing line;
2. the surviving patterns may now agree on another cell;
3. that new forced cell filters another perpendicular line;
4. the process repeats.

This is exactly what a logical cascade does.

A practical propagation workflow

1. maintain a small mental queue of lines changed by your latest moves;
2. process one changed line using the strongest applicable line technique;
3. whenever you mark a new cell, add its perpendicular line to the queue;
4. avoid repeatedly rechecking unchanged lines;
5. continue until the queue produces no new states;
6. then resume broader scanning for the next entry point.

On large puzzles, this workflow is much more efficient than restarting from row 1 after every deduction.

Common mistakes

Stopping after the first consequence

A new cell may trigger several more steps. Follow the chain until it settles.

Propagating an uncertain assumption as if it were fact

Ordinary propagation uses confirmed states. If you deliberately test an assumption, keep that branch clearly separate; that is contradiction reasoning.

Ignoring empty-cell cascades

X marks can be the key step that splits a line or closes a block.

Rechecking every line indiscriminately

Prioritize lines touched by changed cells.

What to learn next

If propagation reaches a stable state with unresolved cells, some expert puzzles require a controlled assumption: test one candidate state, propagate only logical consequences, and reject it if it creates an impossibility. That is contradiction reasoning.

FAQ

Is constraint propagation the same as cross-referencing?

Cross-referencing is one transfer between perpendicular lines. Propagation is the repeated system of transfers until no immediate consequence remains.

Does propagation involve guessing?

No. Standard propagation uses already proven cell states.

Can one simple deduction solve a whole puzzle?

Yes. Some puzzles contain long cascades where one early forced line triggers enough consequences to finish the grid.