THE WHY BEHIND EVERY DSA PROBLEM
SHEET: STRIVER A2Z · REV 0.1
UNDERSTOOD: 0 / 79 DRAFTED
STEP 7 · RECURSION · FAIL FAST, GUESS LAST · HARD

Sudoku Solver

WHAT IT SAYS

Fill every empty cell of a 9x9 Sudoku so that each row, column and 3x3 box contains the digits 1 to 9 exactly once.

WHAT IT'S REALLY ASKING

"You must eventually fill every blank, so the ORDER you fill them in cannot change the answer — only the cost. And that is a gift: if some cell has exactly one legal digit left, writing it there is not a guess at all. Guess where you have nine options, and you multiply your work by nine."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Fill the blanks left to right, validate at the end

Effectively 9^(number of blanks) boards, each validated in O(81)

Walk the empty cells in reading order, try 1 through 9 in each, and once the board is full check whether all 27 groups are valid. Backtrack if not.

WHERE THE WORK IS WASTED — The validation is at the bottom of the tree and the mistake is at the top. Put an illegal 5 in the very first blank and you will not learn about it until you have filled and permuted every other blank underneath it — nine to the power of everything, all of it dead the moment that 5 was written. Even the smarter 'check as you place' version has a smaller version of the same disease: it rescans an entire row, an entire column and an entire box, 27 cells, for every one of the 9 candidates in every cell, re-deriving facts that could have been three bit tests.

!
KEY OBSERVATION — THE UNLOCKlink

A conflict is permanent, and legality is three bit tests.

Two facts, and each one converts a slow check into a fast one. First, monotonicity. Filling cells never removes a conflict — a duplicate digit in a row stays a duplicate no matter what you write elsewhere. So the moment a partial board is illegal, every completion of it is illegal too. That is what makes checking at PLACEMENT time not merely an optimisation but a sound one: the branch you cut was provably empty, so you lose nothing by refusing to enter it. Second, the three constraints are equivalence classes, and each has an index. Cell (r, c) belongs to row r, column c, and box (r/3)*3 + (c/3). Keep one 9-bit mask for each row, each column and each box — 27 masks in total — and a digit is legal in a cell exactly when its bit is clear in all three. That is three AND operations. Placing the digit sets three bits; removing it clears three bits. The 27-cell scan is gone, replaced by arithmetic that does not depend on the size of the board at all.

!
KEY OBSERVATION — THE UNLOCKlink

Choose which cell to branch on: the most trapped one.

Here is the insight that separates a solver that finishes instantly from one that grinds: the recursion is under no obligation to take the blanks in reading order. A valid solution must fill ALL of them, so the order in which you decide them cannot affect correctness — only how big the tree is. So make the order a decision, and pick the most constrained cell: the blank with the fewest legal digits remaining. Read the two extreme cases, because they are what the heuristic is actually for. If some cell has exactly one candidate, branching on it has a branching factor of ONE — that is not searching, that is deduction, and it costs nothing while shrinking the problem. Take those first and they cascade: filling one forced cell often forces the next. If some cell has ZERO candidates, the board is already dead, and branching on it discovers the contradiction immediately instead of after nine wrong guesses somewhere else. Failing fast IS the point. Compare that to reading order, which will happily branch nine ways on a wide-open cell in the top-left corner while a cell in the bottom-right sits there with one obvious answer, silently multiplying everything below it by nine.

Masks, then most-constrained-cell backtracking

Exponential in the worst case, but on real puzzles the branching factor collapses toward 1

Build the 27 masks from the given board. Recurse: if no blanks remain, you are done. Otherwise scan the blanks and select the one with the fewest legal digits — bail out immediately if that count is zero. For each of its legal digits: set the three bits, write the digit, recurse, and on failure clear the bits and erase. Return whether any digit worked.

WHAT YOU TRADED — The masks cost 27 integers and turn every legality question into three bit tests. The most-constrained-cell rule costs a scan of the blanks at every node — real work, and pure overhead on a puzzle that was easy anyway — and buys an enormous cut in branching factor on the puzzles that are not. The transferable lesson: when a search lets you choose which decision to make next, the correct choice is almost always the most constrained one, because it either deduces (branching factor 1) or refutes (branching factor 0), and both are better than guessing.
WATCH THE IDEA RUN
·
3
·
6
7
8
9
1
2
6
7
2
1
9
5
3
4
8
1
9
8
3
4
·
5
6
7
8
5
9
7
6
1
4
2
3
4
2
6
8
·
3
7
9
1
7
1
3
9
2
4
8
5
6
9
6
1
5
3
7
2
8
4
2
8
7
4
1
9
6
3
5
3
4
5
2
8
6
1
7
·
candidates at the chosen cell —
legality 3 set lookups
backtracks 0
Scanning left-to-right, top-to-bottom and guessing at the first blank is the reflex. But YOU get to choose which cell to branch on — and that choice decides how big the search tree is.
step 1 / 12
THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Fail Fast, Guess Last

YOU'LL SEE IT AGAIN WHEN

  • You get to choose which decision to make next, because the solution must satisfy all of them and the order cannot change correctness — only cost.
  • Constraints are monotone: once a partial solution is violated, no continuation can repair it, so early checking is provably safe.
  • Membership tests live over small fixed domains (digits 1-9, colours, letters), which means they can be compressed into bitmasks and answered in O(1).

SAME BLUEPRINT, DIFFERENT PROBLEM

N-QueensWord SearchM-Coloring ProblemCombination Sum III
The bar isn't "solved it once." It's "could rebuild it from the observation."