Proof by contradiction

The difference from guessing

Guessing is placing a queen on a plausible square and continuing as though it were true, intending to back out if the board falls apart. Proof by contradiction is placing a queen on a square specifically to demonstrate that the board falls apart, and then crossing that square out. The moves look similar for the first few seconds and could not be more different in what they leave behind.

The practical distinction is what you do with a branch that does not collapse. A guesser keeps it and builds on it. Someone working by contradiction abandons it — a branch that fails to produce a contradiction has told you nothing, and you move on to the next candidate. You never keep the work; you only keep the eliminations that failed branches produce.

That is why this remains deduction. At no point is anything placed on the board that has not been proved. On a single-solution puzzle, that distinction is what stops a solve from quietly going wrong ten moves before you notice.

Running the test

Pick a colour with few open squares — two or three is ideal — and take its candidates one at a time. For each, imagine the queen there and apply the consequences: its row, its column, the rest of its colour and the eight neighbouring squares all go. Then keep going with the cheap techniques only: any colour or line reduced to one square gets a queen, and any resulting shadows get marked.

You are looking for one specific outcome: some colour, row or column left with no open square at all. That is the contradiction. It proves the original placement impossible, so the candidate is eliminated for good and you return to the real board with one fewer square to worry about.

Keep the test shallow. Three or four consequences deep is the useful range. Beyond that you are effectively running a search in your head, the error rate climbs sharply, and any elimination you derive is one you cannot really check. If a branch has not produced a contradiction within a few steps, drop it.

Choosing which square to test

The choice of candidate determines whether this technique is useful or a waste of two minutes. Test squares whose consequences are large: a candidate in a crowded part of the board, near several unresolved colours, or on a row or column that several colours are still competing for. Those branches either collapse quickly or not at all.

Testing a candidate in an empty corner of the board, where its row and column touch almost nothing unresolved, will produce a long inconclusive branch every time. The square is in a quiet neighbourhood; nothing it eliminates matters yet.

A useful heuristic: test the candidate that overlaps the most other unresolved colours. If placing a queen there would take squares away from four different colours, one of those four has a decent chance of being stranded. If it takes squares from one, it will not.

Keeping the board clean

The practical hazard is contaminating the real board with marks from a hypothetical branch. On paper, work the test in your head or on a copy. In the browser, the safest method is to reason the branch out before touching anything, and only mark the one elimination the test produces.

If you do work a branch out on the live board, undo it completely before continuing — including the eliminations the hypothetical queen caused, which are the easy ones to leave behind. A board carrying stale marks from an abandoned branch will produce deductions that look valid and are not, and that failure is much harder to diagnose than an ordinary mistake because every individual step will seem justified.