Contradiction Method

Advanced technique

The contradiction method (also called proof by contradiction or hypothetical reasoning) is used when all simpler techniques have stalled and cells remain unknown. It works by assuming a cell's state, propagating the consequences, and checking for impossibility.

How it works

Pick an unknown cell.
Temporarily assume it is filled. Apply all constraint propagation techniques (overlap, capping, exhaustion, etc.).
If a contradiction results — a line has no valid arrangement — then the cell cannot be filled. Mark it empty and continue solving.
If no contradiction, undo the assumption and try the opposite: assume the cell is empty. If that leads to a contradiction, the cell must be filled.
If neither assumption leads to a contradiction immediately, try a different cell or go deeper (depth-2 probing).

What counts as a contradiction?

A contradiction occurs when a line has no valid arrangement of its clue given the current cell states. For example, if a row's remaining unknown cells cannot possibly fit its remaining unplaced runs — the spaces are too small or the filled cells can't be reconciled with the clue — that's a contradiction.

Choosing which cell to probe

Not all cells are equally useful to probe. Focus on cells that are:

Highly constrained — part of a line with few unknown cells remaining.
At intersections of two constrained lines — filling/emptying such a cell propagates changes in both directions simultaneously.
Adjacent to a known run boundary — probing the cell just after a known run often immediately confirms or denies whether that run is capped.

Depth and limits

Depth-1 probing (the method above) resolves most hard published puzzles. Depth-2 means: assume cell A is filled, then within that assumption, assume cell B is filled, and check for contradiction. This is much slower but necessary for the hardest puzzles.

Our solver applies depth-1 contradiction probing automatically after simpler techniques stall. The step log will label these steps as contradiction-probe.

Is it really "logic"?

Some purists argue that contradiction probing is "trial and error" rather than pure logic. In practice, the distinction is philosophical — the result is the same certainty. All major competitive nonogram solvers use it for hard puzzles, and most published hard nonograms require it. Well-designed "no-guess" puzzles are resolvable with depth-1 probing but not always with pure line-by-line overlap.

Related techniques

Simple overlap — always try this first
Block capping
Clue exhaustion

Try the solver — it applies contradiction probing automatically →